Resuelve el 8 rompecabezas

12

El 8 Puzzle es la variante más pequeña del 15Puzzle (o el rompecabezas deslizante ). Tiene una 3x3cuadrícula que se llena con números del 0-8 (0 denota el mosaico en blanco) organizados en un orden aleatorio. Su tarea es ingresar una cuadrícula de 3x3 y mostrar la solución más corta (movimientos mínimos) para llegar al estado objetivo. Muestra cada estado de placa, incluido el primer estado en la salida.

Puede haber múltiples soluciones óptimas, solo necesita imprimir una.

Entrada: (pequeño ejemplo)

1 2 0
4 5 3
7 8 6

Salida:

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 el rompecabezas no se puede resolver, imprima solo -1(denotando insoluble)

Editar : Límite de tiempo: <30 segundos.

st0le
fuente
Para aquellos que no están familiarizados con el npuzzle, por favor leer el enlace que aparece ...
st0le
en su pregunta, no debería grid which is filled with numbers from 0-9ser grid which is filled with numbers from 0-8?
Clyde Lobo
@Clyde, ¡Uy! :) Fijo.
st0le
Bastante seguro de que siempre es posible resolverlo, ¿verdad?
Urna de pulpo mágico
@MagicOctopusUrn Si llegaste al estado inicial desde el estado Meta usando las reglas deslizantes, siempre es solucionable. Si pone arbitrariamente en mosaicos, hay estados que no se pueden resolver. Google for Solvability for n puzzle
st0le

Respuestas:

4

Python, 418 caracteres

El código enumera exhaustivamente todas las posiciones y hace mapas de su profundidad (D) y una posición más cercana a la resuelta (E). Luego busca el estado del objetivo para obtener la salida.

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
fuente
como el ' '*3truco
st0le