Hay dos formas de resolver un 15-puzzle. Una es la que acaba descubriendo todo jugador — resolver la fila superior, después la columna izquierda y recursión. La otra es la que usan los ordenadores: una búsqueda heurística por millones de estados, guiada por una cota inferior inteligente del número de movimientos que quedan.
Esta guía cubre ambas, en el orden aproximado en el que la gente las aprende.
El 15-puzzle en un párrafo
Tablero 4×4, quince fichas numeradas, una casilla vacía. Deslizas fichas hacia el hueco hasta que los números estén en orden — 1 a 15, hueco abajo a la derecha. El tablero lo inventó Noyes Chapman en 1874 y se convirtió en una fiebre internacional en los 1880, después de que Sam Loyd ofreciese 1000 dólares por resolver una variante irresoluble. Es, en el fondo, el mismo juego que el 8-puzzle — solo que una fila y una columna más grande.
Resolverlo a mano: el método fila-y-columna
La técnica a la que todo el mundo llega:
- Resuelve la fila 1. Coloca el 1 y el 2. Después el 3 en la esquina superior derecha. La maniobra en L — llevar el 4 a la posición 3, deslizar el 3 debajo y rotar el par hasta la esquina — es el truco que hace posibles las esquinas.
- Resuelve la columna 1. Coloca el 5, después el 9, después el 13 en la esquina inferior izquierda con el mismo truco angular.
- Recursión. Lo que queda es un sub-puzzle 3×3 (con la columna derecha y la fila inferior), que es un 8-puzzle que ya sabes resolver.
Un jugador seguro resuelve un 15-puzzle a mano en 3–5 minutos. Un jugador nuevo puede tardar 20 minutos la primera vez y un tercio de eso a la tercera.
El mismo método escala a 5×5 y 6×6. La recursión siempre acaba en un final 3×3.
Solucionador óptimo: A* con distancia de Manhattan
Un ordenador puede hacerlo mucho mejor que el método fila-y-columna. En concreto: puede encontrar la solución más corta, algo que casi nadie juega.
El hecho matemático: el 15-puzzle medio requiere unos 52 movimientos cuando se resuelve de forma óptima. El peor caso son 80. El método fila-y-columna suele usar 100–150 movimientos en el mismo tablero.
Para encontrar una solución óptima, la búsqueda A* trata cada estado del tablero como un nodo, cada movimiento como una arista, y se pregunta: ¿cuántos movimientos hasta el objetivo, al menos? El mínimo exacto es imposible de calcular sin resolver el puzzle, pero una buena cota inferior hace que A* sea rápido.
La cota clásica es la distancia de Manhattan:
Para cada ficha, suma la distancia en filas más la distancia en columnas desde su posición actual hasta su posición objetivo. (Se ignora el hueco.)
La distancia de Manhattan es admisible — nunca sobrestima la distancia real, porque cada ficha debe recorrer al menos eso. Con A* y Manhattan, el 8-puzzle se resuelve en microsegundos y el 15-puzzle en segundos.
IDA*: el primo amigable con la memoria
A* tiene que recordar cada estado explorado. Para 15-puzzles, eso son cientos de megabytes de RAM en los tableros más duros. Iterative-deepening A (IDA)** intercambia memoria por tiempo haciendo DFS limitada en profundidad con la heurística, subiendo el límite en cada ronda.
IDA* es lo que usa cada solucionador de referencia para el 15-puzzle. El artículo de Richard Korf de 1985 introdujo IDA* precisamente para resolver 15-puzzles de forma óptima con el hardware de principios de los 80.
Más allá de Manhattan: walking distance y bases de patrones
La distancia de Manhattan es rápida pero floja. Asume que las fichas pueden atravesarse libremente. No pueden — dos fichas en la misma fila deben turnarse, lo que cuesta movimientos extra.
Walking distance cuenta esos movimientos extra. Precalcula, para cada par de filas, el número mínimo de «intercambios de fila» necesarios para permutar las fichas a sus filas correctas. Lo mismo para columnas. Súmalo. El resultado es demostrablemente más ajustado que Manhattan — típicamente un 25 % más, lo que significa que A*/IDA* explora un 25 % menos de nodos.
La heurística conocida más fuerte para el 15-puzzle es la base de patrones aditiva disjunta:
- Particiona las fichas en grupos disjuntos (una partición común es 5-5-5 más el hueco).
- Para cada grupo, precalcula, para cada disposición posible de las fichas del grupo en el tablero, el número mínimo de movimientos para llevarlas a sus posiciones objetivo, ignorando las demás.
- En tiempo de búsqueda, suma las consultas de cada grupo.
Una partición 7+8 para el 15-puzzle ocupa unos 1 GB en memoria, pero permite que IDA* resuelva cualquier 15-puzzle en milisegundos. Para el 24-puzzle (5×5), las bases de patrones son esencialmente el único enfoque práctico.
Por qué resolverlo a mano suele ser más rápido (para una partida)
Una comprobación de realidad: escribir un A*, elegir una heurística y esperar a que termine es más largo que coger un 15-puzzle y resolverlo a mano. La matemática es interesante; lo práctico es que una persona que conozca el método fila-y-columna resuelve cualquier tablero en cinco minutos.
La razón por la que los solucionadores importan es el agregado: artículos de investigación que comparan heurísticas en miles de instancias aleatorias, libros de IA que usan el 15-puzzle como banco de pruebas, y apps que necesitan generar puzzles garantizadamente resolubles en aproximadamente N movimientos para calibrar la dificultad.
Orden de lectura sugerido
Si has venido aquí a escribir un solucionador, empieza con A*/Manhattan, mira cómo resuelve unos 8-puzzles, después porta a IDA* para 15-puzzles. Walking distance es luego una adición de 100 líneas que duplica la velocidad. Las bases de patrones son un proyecto de fin de semana que te da otro orden de magnitud.
Si has venido a jugar un 15-puzzle, aprende primero el método fila-y-columna, después lee por qué algunos tableros no tienen solución y vuelve aquí luego para la teoría.