Solucionador del 8-puzzle — A* con distancia de Manhattan en una página

El 8-puzzle es lo que escribes el día que aprendes sobre búsqueda heurística. Es lo bastante pequeño para que casi cualquier enfoque funcione, lo bastante grande para que los malos enfoques sean visiblemente peores. Este artículo recorre la solución estándar de arriba abajo.

El estado

Representa el tablero como un array de nueve enteros, indexados 0..8 en orden de filas:

posiciones:   índices:
 1 2 3        0 1 2
 4 5 6   ↔    3 4 5
 7 8 _        6 7 8

La casilla vacía es un valor centinela — habitualmente el 0. El estado objetivo es [1, 2, 3, 4, 5, 6, 7, 8, 0].

Los movimientos

Desde una posición con el hueco en el índice e, puedes intercambiar el hueco con sus vecinos ortogonales: e-3 (arriba), si no está en la fila superior; e+3 (abajo), si no está en la inferior; e-1 (izquierda), si no está en la columna izquierda; e+1 (derecha), si no en la derecha.

Una función neighbors(state) devuelve los hasta cuatro estados alcanzables en un movimiento.

La heurística: distancia de Manhattan

Para cada ficha (ignorando el hueco), calcula la distancia en filas más la distancia en columnas desde su posición actual hasta su objetivo. Suma sobre las fichas. Esa suma es una cota inferior del número de movimientos restantes — cada ficha debe recorrer al menos esa distancia.

En pseudocódigo:

h(state) = suma sobre fichas t:
  abs(row(actual) - row(objetivo)) + abs(col(actual) - col(objetivo))

La distancia de Manhattan es admisible (nunca sobrestima) y consistente (cumple la desigualdad triangular). Ambas propiedades importan para A*.

A* en doce líneas

A* mantiene una cola de prioridad de estados, ordenada por f = g + h, donde g es la profundidad (movimientos hasta ahora) y h la estimación heurística de los restantes. En cada iteración: saca el estado con f menor, expándelo, mete sus vecinos con f actualizada.

open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}

while open is not empty:
  state = open.pop()
  if state == goal: return reconstruct_path(came_from, state)
  for n in neighbors(state):
    tentative_g = g[state] + 1
    if n not in g or tentative_g < g[n]:
      g[n] = tentative_g
      came_from[n] = state
      open.push(n, f=tentative_g + h(n))

Ese es todo el solucionador. Implementa h, implementa neighbors y puedes resolver cualquier 8-puzzle.

Rendimiento

A* con distancia de Manhattan resuelve cualquier 8-puzzle en unos cientos de microsegundos, expandiendo de unos cientos a unos pocos miles de estados en las instancias más duras. El espacio de estados es lo bastante pequeño para que A* domine a IDA* a este tamaño — A* es la elección correcta para 3×3, IDA* toma el relevo en 4×4 y arriba.

Errores típicos

Tres cosas que harás mal a la primera:

Hashing del estado. Las tuplas de Python hashean bien; los arrays de int de Java no. Sea cual sea el lenguaje, el estado debe ser hashable para que los conjuntos abierto/cerrado funcionen. Un truco habitual es codificar el estado de 9 fichas en un único entero de 32 bits (4 bits por celda, ya que las celdas van de 0 a 8).

Olvidarse de comprobar la paridad de inversiones. Si generas un 8-puzzle aleatorio mezclando, la mitad de las veces no tiene solución, y A* explorará todo el medio espacio de 181 440 estados buscando un camino inexistente. Añade una comprobación de paridad antes de A*, o genera caminando hacia atrás desde el objetivo.

Tratar el hueco como una ficha en la heurística. La distancia de Manhattan se suma solo sobre las fichas reales. Incluir el hueco infla la heurística y rompe la admisibilidad (puedes «arreglar» el hueco gratis con un movimiento).

Más allá de Manhattan

Puedes hacerlo mejor que Manhattan en el 8-puzzle, pero poco:

• Conflicto lineal — si dos fichas de la misma fila están ambas en su fila objetivo pero en orden incorrecto, harán falta al menos dos movimientos extra para que se crucen. Suma 2 por conflicto. Mejora Manhattan en un 5–15 %.
• Bases de patrones — precalcular el coste óptimo sobre subconjuntos de fichas. Coste de memoria enorme para una mejora minúscula en el 8-puzzle. Vale la pena en los solucionadores del 15-puzzle, no aquí.

Para 8-puzzles, Manhattan + conflicto lineal es el punto dulce práctico.

Qué construir después

Si escribiste un solucionador de 8-puzzle, las extensiones naturales son:

1. Solucionador del 15-puzzle con IDA* + walking distance. Mismas ideas, búsqueda más profunda. (Guía aquí.)
2. Solucionador general del N-puzzle con bases de patrones. Proyecto de fin de semana.
3. Test de solubilidad — una función de 30 líneas que devuelve true si un tablero es alcanzable desde el objetivo. Útil para apps. (Basado en el teorema de paridad.)

El 8-puzzle es pequeño. Las técnicas que aprendes resolviéndolo escalan hasta arriba.