Si estás implementando un solucionador de deslizante y no estás seguro de qué algoritmo usar, este artículo compara seis conocidos por velocidad, memoria, complejidad de código y tamaño de tablero que manejan cómodamente. Las respuestas para 3×3, 4×4 y 5×5 son distintas.
1. Breadth-first search (BFS)
El algoritmo correcto más simple. Explora estados nivel a nivel hasta encontrar el objetivo.
- Tiempo — exponencial en la profundidad de la solución. Para el 8-puzzle acaba en fracciones de segundo. Para el 15-puzzle no acaba antes de que se quede sin RAM tu ordenador.
- Memoria — guarda todo lo visitado en memoria. Decenas de millones de estados para 15-puzzles duros.
- Complejidad de código — veinte líneas.
- Veredicto — vale para 3×3, inútil más allá.
2. A* con distancia de Manhattan
El primer algoritmo de verdad. Misma estructura que BFS, pero los estados salen de una cola de prioridad ordenada por f = g + h, donde h es la heurística de distancia de Manhattan.
- Tiempo — milisegundos para el 8-puzzle, segundos a minutos para el 15.
- Memoria — sigue guardando todo lo explorado; manejable en el 8, doloroso en el 15.
- Complejidad de código — cincuenta líneas, en su mayoría fontanería de cola de prioridad.
- Veredicto — la herramienta para el 8-puzzle. Justo en el límite para el 15.
3. A* con Manhattan + conflicto lineal
Añade 2 movimientos a la heurística por cada par de fichas en la misma fila que pertenezcan a esa fila pero estén en orden incorrecto (lo mismo para columnas). Tienen que cruzarse, algo que Manhattan no ve.
- Tiempo — típicamente 5–15 % más rápido que A* con Manhattan a secas.
- Memoria — sin cambios.
- Complejidad de código — sesenta líneas.
- Veredicto — estrictamente mejor que A* Manhattan puro. Úsalo siempre.
4. IDA* con Manhattan + conflicto lineal
A* iterativo en profundidad. Hace DFS con cota en f-coste y sube el umbral en cada iteración. Cambia memoria por tiempo a base de re-exploración.
- Tiempo — ligeramente más lento por nodo que A* por las repeticiones, pero la menor presión de memoria suele ganar en 15-puzzles duros.
- Memoria — O(profundidad), no O(estados explorados). Esa es la ganancia.
- Complejidad de código — ochenta líneas (DFS recursiva, gestión de umbral).
- Veredicto — la herramienta para el 4×4. Estándar desde Korf 1985.
5. IDA* con walking distance
Walking distance es una heurística más ajustada. Precalcula, para cada disposición de fichas proyectada solo a filas, el número mínimo de operaciones de «intercambio de filas» necesarias para llevar cada ficha a su fila correcta. Lo mismo para columnas. Suma.
Captura algo que Manhattan se pierde: fichas de la misma fila «peleando» por el mismo hueco.
- Tiempo — típicamente 2× más rápido que Manhattan + conflicto lineal en 15-puzzles duros, porque la heurística más ajustada poda más.
- Memoria — añade una pequeña tabla precalculada (~500 KB en 4×4).
- Complejidad de código — 150 líneas. La precomputación es un BFS sobre un espacio reducido.
- Veredicto — la herramienta para el 4×4 si tienes presupuesto de ingeniería. La primera mejora no trivial.
6. IDA* con bases aditivas disjuntas de patrones
La heurística más fuerte conocida para deslizantes. Particiona las fichas en grupos disjuntos (una partición habitual para 15-puzzle es 7+8 o 5+5+5). Para cada grupo, precalcula el coste de permutar sus fichas a posición objetivo sobre todas las disposiciones de ese grupo. En tiempo de búsqueda, busca la contribución de cada grupo y suma.
- Tiempo — resuelve el 15-puzzle más duro en milisegundos. Resuelve 24-puzzles aleatorios en segundos.
- Memoria — significativa. Una partición 7+8 del 15-puzzle es ~1 GB. Una 5+5+5+9 del 24-puzzle es ~4 GB. La memoria domina la ingeniería.
- Complejidad de código — 300+ líneas. La precomputación usa BFS retrógrado sobre el espacio del grupo y es el grueso del trabajo.
- Veredicto — la herramienta para 5×5 y 6×6. Excesivo para 3×3.
Recomendaciones resumidas
Si escribes un solucionador hoy:
- Para 3×3, A* con Manhattan + conflicto lineal. Todo lo demás es sobreingeniería.
- Para 4×4, IDA* con walking distance. Las bases de patrones dan ganancias marginales a este tamaño; no compensan la complejidad.
- Para 5×5, IDA* con bases aditivas (5+5+5+9 estándar). Sin bases, te quedarás colgado en las instancias más duras.
- Para 6×6 (35-puzzle), los mismos algoritmos resuelven instancias aleatorias, pero los casos más duros siguen siendo preguntas abiertas. La mayoría de apps no lo intentan.
¿Y el machine learning?
Pregunta razonable en 2026. Las heurísticas con redes neuronales se estudian al menos desde 2014 y pueden producir heurísticas rápidas para deslizantes. La pega es que normalmente no son admisibles — pueden sobrestimar, lo que significa que el algoritmo resultante ya no garantiza optimalidad. Para desarrolladores que necesitan soluciones óptimas garantizadas para calibrar dificultad, las bases clásicas siguen siendo la herramienta correcta.
Para interés académico, las bases entrenadas con red neuronal aportan ligeras aceleraciones en las instancias más duras. Útil para artículos, marginal para software de producción.
Lo que va a una app real
Una app móvil de producción que necesite un solucionador para generar pistas casi siempre acaba en:
- IDA* + walking distance para 4×4.
- IDA* + una base de patrones pequeña para 5×5.
- Una sola llamada de un-siguiente-movimiento desde el botón de pista.
- Todo se ejecuta en el dispositivo. El solucionador entero son unos cientos de kilobytes de código más unos megabytes de tablas precalculadas.
Esa es la pila pragmática correcta para un juego de móvil tranquilo. El botón de pista de Slide Puzzle funciona exactamente así.