Pecahkan 8 Puzzle

8 Puzzle adalah varian yang lebih kecil dari 15Puzzle (atau teka-teki Sliding ). Anda memiliki 3x3kisi yang diisi dengan angka 0-8 (0 menunjukkan ubin kosong) yang disusun dalam urutan acak. Tugas Anda adalah memasukkan kisi 3x3 dan menunjukkan solusi terpendek (gerakan minimum) untuk mencapai status sasaran. Tampilkan setiap boardstate termasuk status pertama dalam output.

Mungkin ada beberapa solusi optimal, Anda hanya perlu mencetaknya.

Input: (contoh kecil)

1 2 0
4 5 3
7 8 6

Keluaran:

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

Jika puzzle tidak dapat dipecahkan, cetak saja -1(menunjukkan tidak dapat dipecahkan)

Sunting : Batas waktu: <30 detik.

Python, 418 karakter

Kode tersebut secara lengkap menyebutkan semua posisi dan membuat peta kedalamannya (D), dan posisi yang lebih dekat untuk dipecahkan (E). Kemudian mencari status tujuan untuk mendapatkan 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