Résolvez le puzzle 8

Le 8 Puzzle est la plus petite variante du 15Puzzle (ou le puzzle coulissant ). Vous avez une 3x3grille qui est remplie de chiffres de 0 à 8 (0 indique la tuile vierge) disposés dans un ordre aléatoire. Votre tâche consiste à saisir une grille 3x3 et à afficher la solution la plus courte (mouvements minimum) pour atteindre l'état de l'objectif. Affichez chaque état de la carte, y compris le premier état dans la sortie.

Il peut y avoir plusieurs solutions optimales, il vous suffit d'en imprimer une.

Entrée: (petit exemple)

1 2 0
4 5 3
7 8 6

Production:

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 le casse-tête ne peut pas être résolu, imprimez simplement -1(indiquant insoluble)

Modifier : délai: <30 secondes.

Python, 418 caractères

Le code énumère exhaustivement toutes les positions et fait des cartes de leur profondeur (D), et une position plus proche de résolue (E). Ensuite, il recherche l'état de l'objectif pour obtenir la sortie.

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