Решить головоломку 8

12

8 Puzzle - это меньший вариант 15Puzzle (или Скользящая головоломка ). У вас есть 3x3сетка, которая заполнена числами от 0 до 8 (0 обозначает пустую клетку), расположенными в случайном порядке. Ваша задача - ввести сетку 3х3 и показать кратчайшее решение (минимальное количество ходов), чтобы добраться до состояния цели. Отобразите каждое состояние платы, включая первое состояние на выходе.

Там может быть несколько оптимальных решений, вам просто нужно напечатать одно.

Вход: (маленький пример)

1 2 0
4 5 3
7 8 6

Выход:

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

Если головоломка не может быть решена, напечатайте просто -1(обозначает неразрешимый)

Изменить : ограничение по времени: <30 секунд.

st0le
источник
Для тех, кто не знаком с npuzzle, пожалуйста, прочитайте приведенную ссылку ...
st0le
в твоем вопросе не должно grid which is filled with numbers from 0-9быть grid which is filled with numbers from 0-8?
Клайд Лобо
@ Клайд, ой! :) Исправлена.
st0le
Уверен, это всегда можно решить, верно?
Волшебная Урна Осьминога
@MagicOctopusUrn Если вы пришли в исходное состояние из состояния цели, используя правила скольжения, это всегда разрешимо. Если вы произвольно положили плитки, то есть состояния, которые невозможно решить. Загадка Google for Solvability for n
st0le

Ответы:

4

Python, 418 символов

Код исчерпывающе перечисляет все позиции и составляет карты их глубины (D) и позиции, близкой к решаемой (E). Затем он ищет состояние цели, чтобы получить результат.

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
Кит Рэндалл
источник
как ' '*3трюк
st0le