Resolver o enigma 8

O 8 Puzzle é a variante menor do 15Puzzle (ou o quebra-cabeça deslizante ). Você tem uma 3x3grade que é preenchida com números de 0 a 8 (0 indica o bloco em branco) organizados em uma ordem aleatória. Sua tarefa é inserir uma grade 3x3 e mostrar a solução mais curta (movimentos mínimos) para chegar ao estado do objetivo. Exiba cada estado da placa, incluindo o primeiro estado na saída.

Pode haver várias soluções ideais, você só precisa imprimir uma.

Entrada: (pequeno exemplo)

1 2 0
4 5 3
7 8 6

Resultado:

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

Se o quebra-cabeça não puder ser resolvido, imprima apenas -1(indicando insolúvel)

Editar : limite de tempo: <30segundos.

Python, 418 caracteres

O código enumera exaustivamente todas as posições e faz mapas de sua profundidade (D), e uma posição mais próxima da resolução (E). Em seguida, procura o estado do objetivo para obter a saída.

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