Rozwiąż 8 puzzli

8 Puzzle to mniejszy wariant 15Puzzle (lub przesuwanej układanki ). Masz 3x3siatkę wypełnioną cyframi od 0 do 8 (0 oznacza pustą płytkę) ułożoną w losowej kolejności. Twoim zadaniem jest wprowadzenie siatki 3x3 i pokazanie najkrótszego rozwiązania (minimum ruchów), aby dostać się do stanu celu. Wyświetlaj każdy stan tablicy, w tym pierwszy stan na wyjściu.

Może istnieć wiele optymalnych rozwiązań, wystarczy je wydrukować.

Dane wejściowe: (mały przykład)

1 2 0
4 5 3
7 8 6

Wynik:

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

Jeśli zagadki nie można rozwiązać, po prostu wydrukuj -1(oznaczając nierozwiązywalne)

Edycja : Limit czasu: <30 sekund.

code-golf sliding-puzzle

— st0le
źródło

Dla tych, którzy nie są zaznajomieni z npuzzle, przeczytaj link pod warunkiem ...

— st0le

w twoim pytaniu nie powinno grid which is filled with numbers from 0-9być grid which is filled with numbers from 0-8?

— Clyde Lobo,

@Clyde, Ups! :) Naprawiony.

— st0le,

Jestem pewien, że zawsze da się rozwiązać, prawda?

— Magic Octopus Urn

@MagicOctopusUrn Jeśli osiągnąłeś stan początkowy ze stanu Cel przy użyciu przesuwanych reguł, zawsze można go rozwiązać. Jeśli umieścisz dowolnie płytki, są stany, których nie można rozwiązać. Google for Solvability for n puzzle

— st0le

Python, 418 znaków

Kod wyczerpująco wylicza wszystkie pozycje i czyni mapy ich głębokości (D) oraz pozycji bliżej rozwiązanej (E). Następnie sprawdza stan celu, aby uzyskać wynik.

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

— Keith Randall
źródło

jak ' '*3sztuczka.

— st0le,