El 15-puzzle lleva siendo banco de pruebas de algoritmos de búsqueda IA desde los 60. Cada generación se inventó para romper el muro contra el que chocó la anterior. Este artículo los recorre en orden de invención, con para qué sirvió cada uno y qué hizo necesario al siguiente.
Años 60 — Búsqueda en anchura (BFS)
El algoritmo correcto más simple. Explora estados nivel a nivel: profundidad 1 tiene 4 estados, profundidad 2 tiene 16, profundidad 3 tiene 64, etc.
Para el 8-puzzle, BFS termina rápido — el peor caso es profundidad 31, así que 4³¹ estados como máximo (mucho menos en la práctica por revisitas). Para el 15-puzzle, la peor profundidad es 80, así que 4⁸⁰ estados. Más estados que átomos en el universo observable. BFS no termina.
El muro: explosión exponencial. Resolver con búsqueda no informada es desesperanzado más allá del 3×3.
1968 — Búsqueda A*
Hart, Nilsson y Raphael publican A Formal Basis for the Heuristic Determination of Minimum Cost Paths. La idea: en vez de explorar estados por distancia al inicio, explorar por f = g + h, donde h es una estimación de cota inferior de la distancia que queda.
Para el 15-puzzle, h es la distancia de Manhattan — suma de distancias en filas+columnas de cada ficha a su objetivo. Manhattan es admisible (nunca sobrestima) y consistente (cumple la desigualdad triangular). Con esas propiedades, A* encuentra la solución óptima.
Rendimiento en el 15-puzzle: resuelve cualquier tablero, pero en las instancias más duras explora millones de estados y consume cientos de MB. El muro: memoria.
1985 — IDA*
Depth-first iterative-deepening: An optimal admissible tree search de Richard Korf. La intuición: en vez de la cola de prioridad de A* (que guarda todos los estados), DFS con profundidad iterativa donde el límite de profundidad es el f-coste y no la profundidad.
IDA* explora los mismos estados que A*, en aproximadamente el mismo orden, pero sin recordarlos entre iteraciones. Cada «barrido» usa O(profundidad) de memoria en vez de O(estados explorados).
Rendimiento: resuelve cualquier 15-puzzle en segundos en hardware de 1985, cabe en kilobytes. El muro: la heurística sigue siendo Manhattan. Acelerar exige una heurística más ajustada.
Años 90 — Conflicto lineal
Hansson, Mayer y Yung — Criticizing solutions to relaxed models yields powerful admissible heuristics. Manhattan supone que las fichas se atraviesan. No.
Conflicto lineal añade 2 movimientos por cada par de fichas en la misma fila, ambas pertenecientes a esa fila, pero en orden incorrecto — una tendrá que salir de la fila para dejar pasar a la otra. Igual para columnas.
Efecto: 5–15 % menos nodos expandidos en 15-puzzles duros. Mejora estricta sobre Manhattan; sin desventajas reales.
1996 — Walking distance
Una heurística que captura más la estructura. Para cada disposición de fichas proyectada solo a filas (ignorando posición dentro de la fila), precalcula el mínimo número de operaciones de «intercambio de fila» para poner cada ficha en su fila correcta. Lo mismo para columnas.
Walking distance es admisible y mucho más ajustada que Manhattan + conflicto lineal — típicamente 1,5–2× el valor de Manhattan, lo que significa que IDA* expande muchos menos nodos.
Coste: una pequeña tabla precalculada (~500 KB para 4×4). El punto dulce del 15-puzzle.
2002 — Bases aditivas disjuntas de patrones
Korf y Felner — Disjoint pattern database heuristics. La heurística más fuerte conocida para deslizantes.
Idea: partición disjunta de fichas (una 7+8 para 15-puzzle es estándar). Para cada grupo, precalcula el coste óptimo de mover solo sus fichas a sus posiciones objetivo, ignorando las demás. Tabula cada disposición posible del grupo.
En tiempo de búsqueda, suma la contribución de cada grupo. Por disjunción y por un argumento cuidadoso de que los movimientos necesarios no chocan, la suma es admisible.
Coste de memoria: ~1 GB para el 15-puzzle. Rendimiento: resuelve el 15-puzzle más duro en unos pocos miles de expansiones de nodos — milisegundos.
2005+ — bases más grandes para puzzles mayores
La misma técnica escala al 24-puzzle y más allá. Una partición 5+5+5+9 para el 24-puzzle ocupa ~4 GB. Con ella, cualquier 24-puzzle aleatorio se resuelve en segundos.
El 35-puzzle (6×6) está en el filo. Las instancias más duras siguen abiertas en investigación a 2026.
2010+ — heurísticas con redes neuronales
Redes entrenadas para predecir la magnitud tipo Manhattan, a veces produciendo heurísticas más ajustadas que las hechas a mano. La pega: las NN suelen no ser demostrablemente admisibles, así que los solucionadores sobre ellas dan respuestas probablemente óptimas, no garantizadas.
Para artículos, interesante. Para software de producción donde importa la optimalidad (calibración en juegos), las bases clásicas siguen siendo la herramienta.
Por qué importa esta historia
Cada ola de investigación en deslizantes vino del mismo apretón: el puzzle es lo bastante pequeño para hacer benchmarks, lo bastante grande para que los algoritmos malos se cuelguen. El 15-puzzle ha sido el banco de pruebas para avances generales en búsqueda heurística — A*, IDA*, bases de patrones — que ahora alimentan planificación de rutas, demostración de teoremas y muchos otros dominios.
Cuando resuelves un 15-puzzle en una app con un botón de pista, estás usando algoritmos desarrollados para este juego y luego generalizados a todo lo demás.
Tabla resumen
| Año | Algoritmo | Tiempo en 15-puzzle duro | Memoria | Qué habilitó |
|---|---|---|---|---|
| 60 | BFS | No termina | Enorme | — |
| 1968 | A* + Manhattan | Minutos | Cientos de MB | Búsqueda heurística |
| 1985 | IDA* + Manhattan | Segundos | KB | Profundización iterativa |
| 1996 | IDA* + walking distance | < 1 s | + 500 KB precalc | Heurística mejor |
| 2002 | IDA* + bases 7+8 | Milisegundos | + 1 GB precalc | Enumeración por subconjuntos |
Cada fila es un salto cualitativo, no marginal. La historia de resolver el 15-puzzle es también la historia de la búsqueda heurística moderna.