Resuelve el 8 rompecabezas

El 8 Puzzle es la variante más pequeña del 15Puzzle (o el rompecabezas deslizante ). Tiene una 3x3cuadrícula que se llena con números del 0-8 (0 denota el mosaico en blanco) organizados en un orden aleatorio. Su tarea es ingresar una cuadrícula de 3x3 y mostrar la solución más corta (movimientos mínimos) para llegar al estado objetivo. Muestra cada estado de placa, incluido el primer estado en la salida.

Puede haber múltiples soluciones óptimas, solo necesita imprimir una.

Entrada: (pequeño ejemplo)

1 2 0
4 5 3
7 8 6

Salida:

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

Si el rompecabezas no se puede resolver, imprima solo -1(denotando insoluble)

Editar : Límite de tiempo: <30 segundos.

Python, 418 caracteres

El código enumera exhaustivamente todas las posiciones y hace mapas de su profundidad (D) y una posición más cercana a la resuelta (E). Luego busca el estado del objetivo para obtener la salida.

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