쭈노의 8퍼즐(8puzzle-경로까지) timer 1초 memory 256MB

대딴마 쭈노와 전교회장 셩빈이 8퍼즐 게임을 하고 있다. 게임 규칙은 섞인 8퍼즐의 숫자를 정해진 시간 안에 최소횟수의 이동으로 원래대로 맞추는 것이다. 둘 다 게임에는 자신이 있어 시간 안에 맞추기는 했는데 이동 횟수가 최소인지는 확실하지 않았다. 모범 답안이 필요한 두 사람은 프로그래머인 당신에게 모범답안을 부탁하고 있다.

8 퍼즐에 대해 잠깐 살펴보자. 8퍼즐의 초기 모습은 아래 그림과 같이 3 * 3 보드판에 1 ~ 8까지의 숫자가 적힌 카드를 

위에서 아래로 왼쪽에서 오른쪽으로 차례로 놓고 한 개의 공간은 비워둔 상태이다.

이동할 수 있는 카드는 빈 공간과 인접한 숫자 카드만 가능하다. 아래 그림 1에서 3번 카드를 아래로 이동하면 그림 2와 같이 되고 

아래 그림 1에서 1번 카드를 오른쪽으로 이동하면 그림 3과 같이 된다.

 

초기 8퍼즐 보드의 숫자카드를 위 규칙에 따라 마구 섞은 상태가 주어진다. 다시 원래 초기 모습으로 맞추는데 최소 이동 횟수와 이동 순서를 구하는 프로그램을 작성하시오.