Solve the 8 Puzzle

Question

The 8 Puzzle is the smaller variant of the 15Puzzle (or the Sliding puzzle). You have a 3x3 grid which is filled with numbers from 0-8 (0 denotes the blank tile) arranged in a random order. Your task is to input a 3x3 grid and show the shortest solution (minimum moves) to get to the goal state. Display each boardstate including the first state in the output.

There may be multiple optimal solutions, you just need to print one.

Input: (small example)

1 2 0
4 5 3
7 8 6

Output:

2 <- denotes minimum number of moves required
1 2 0
4 5 3
7 8 6

1 2 3
4 5 0
7 8 6

1 2 3
4 5 6
7 8 0 <- goal state

If the puzzle can't be solved, print just -1 (denoting unsolvable)

Edit: Time limit : < 30seconds.

Answer 1

Python, 418 characters

The code exhaustively enumerates all positions and makes maps of their depth (D), and a position one closer to solved (E). Then it looks up the goal state to get the output.

D={(1,2,3,4,5,6,7,8,0):0}
E=D.copy()
def Z(a,d):
 b=list(a);b[i],b[i+d]=b[i+d],0;b=tuple(b)
 if b not in E:E[b]=a;D[b]=D[a]+1
for x in' '*32:
 for a in E.copy():
  i=list(a).index(0)
  if i>2:Z(a,-3)
  if i%3:Z(a,-1)
  if i%3<2:Z(a,1)
  if i<6:Z(a,3)
g=[]
for x in' '*3:g+=map(int,raw_input().split())
g=tuple(g)
if g in E:
 print D[g]
 while g:
  for i in(0,3,6):print'%d %d %d'%g[i:i+3]
  g=E[g];print
else:print -1