Löse das 8 Puzzle

Das 8-Puzzle ist die kleinere Variante des 15-Puzzles (oder des Schiebepuzzles ). Sie haben ein 3x3Raster, das mit Zahlen von 0 bis 8 gefüllt ist (0 bezeichnet die leere Kachel) und in zufälliger Reihenfolge angeordnet ist. Ihre Aufgabe ist es, ein 3x3-Raster einzugeben und die kürzeste Lösung (minimale Züge) anzuzeigen, um zum Zielzustand zu gelangen. Zeigen Sie jeden Boardstatus einschließlich des ersten Status in der Ausgabe an.

Möglicherweise gibt es mehrere optimale Lösungen. Sie müssen nur eine drucken.

Eingabe: (kleines Beispiel)

1 2 0
4 5 3
7 8 6

Ausgabe:

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

Wenn das Rätsel nicht gelöst werden kann, drucken Sie einfach -1(unlösbar)

Bearbeiten : Zeitlimit: <30 Sekunden.

Python, 418 Zeichen

Der Code listet alle Positionen vollständig auf und erstellt Karten ihrer Tiefe (D) und einer Position, die näher an der gelösten liegt (E). Dann wird der Zielstatus nachgeschlagen, um die Ausgabe zu erhalten.

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