Algoritmos de Sudoku - Cómo funciona un solver y su implementación
Implementar un solver de Sudoku es un excelente ejercicio de programación. Este artículo explica cómo resolver cualquier Sudoku instantáneamente combinando backtracking, propagación de restricciones y heurísticas.
Fundamentos del backtracking
El solver de Sudoku más simple se implementa con backtracking (búsqueda en profundidad). Se encuentra una celda vacía, se prueban los números del 1 al 9 en orden y, si no se viola ninguna restricción, se avanza a la siguiente celda vacía. Si se produce una violación, se retrocede (backtrack) a la celda anterior y se prueba otro número. Este algoritmo siempre encuentra la solución, pero en el peor caso prueba todas las combinaciones, lo que resulta ineficiente. Incluso en puzles de nivel Fácil puede requerir miles de intentos.
Aceleración mediante propagación de restricciones
La propagación de restricciones (Constraint Propagation) mejora drásticamente la eficiencia del backtracking. Cada vez que se coloca un número, se actualizan inmediatamente los candidatos de las celdas afectadas en la misma fila, columna y bloque. Si alguna celda queda sin candidatos, se hace backtrack en ese punto (poda temprana). Si alguna celda queda con un solo candidato, se confirma automáticamente (aplicación automática del Single Desnudo). Esta propagación reduce enormemente el espacio de búsqueda, y la mayoría de puzles se resuelven sin necesidad de backtracking.
Heurística MRV
La optimización del orden de exploración también es importante. La heurística MRV (Minimum Remaining Values) prioriza la exploración de las celdas con menos candidatos. Una celda con 2 candidatos se confirma en máximo 2 intentos, mientras que una con 8 candidatos puede necesitar hasta 8. Con MRV se minimiza la ramificación del árbol de búsqueda y se reduce drásticamente la frecuencia de backtracking. Combinando propagación de restricciones con MRV, incluso los puzles más difíciles del mundo se resuelven en menos de 1 milisegundo.
Diferencias con la resolución humana
Existe una diferencia fundamental entre un solver informático y la resolución humana. El ordenador gestiona todos los candidatos con precisión y puede hacer backtracking a alta velocidad, por lo que el enfoque de probar y retroceder es efectivo. En cambio, los humanos prefieren evitar las conjeturas y resolver solo mediante pasos lógicamente confirmables. Esto se debe a las limitaciones de la memoria de trabajo humana: el backtracking requiere recordar múltiples estados, algo difícil para las personas. El diseño de dificultad del Sudoku se basa precisamente en si un humano puede resolverlo sin necesidad de adivinar.
Qué es realmente la velocidad del resolutor
Un resolutor de sudoku puede resolver en un instante gracias a una combinación de una velocidad de prueba incomparable a la de un humano y artificios que eliminan el desperdicio. El backtracking ingenuo por sí solo es lo bastante rápido para el tamaño fijo 9x9, ya que una computadora puede probar millones de colocaciones de números por segundo. Pero añadir propagación de restricciones y optimización del orden de búsqueda reduce drásticamente el número de pruebas en sí, resolviendo al instante incluso los rompecabezas más difíciles. La clave es que la esencia de la velocidad reside no solo en la velocidad de procesamiento, sino en lo hábilmente que acotas el rango de búsqueda. Un diseño que poda rápido las ramas obviamente inútiles, en vez de probarlo todo a ciegas, determina la eficiencia.
El sudoku como problema de cobertura exacta
Matemáticamente, el sudoku puede formularse como una especie de problema de cobertura exacta. El acto de colocar un número en cada celda se expresa como una selección que cubre exactamente una vez cada uno el conjunto de restricciones a satisfacer. Desde este punto de vista, el algoritmo llamado Dancing Links (DLX), propuesto por Donald Knuth, puede aplicarse de forma extremadamente eficiente. DLX es una técnica que acelera el backtracking quitando y restaurando temporalmente elementos de una lista enlazada, usada para la resolución rápida de rompecabezas en general, no solo del sudoku. Que aparezca una solución poderosa distinta al cambiar la perspectiva sobre el mismo problema es uno de los placeres de la informática.
Usos y límites del resolutor
Un resolutor de sudoku no sirve solo para producir respuestas. Lo importante en la práctica es más bien la verificación de la unicidad en la generación de rompecabezas y la estimación de la dificultad. El generador usa el resolutor para confirmar que el rompecabezas que creó tiene de verdad una sola solución, y juzga qué técnicas hacen falta mediante un resolutor que imita los métodos humanos. Por otro lado, usar el resolutor para mostrar la respuesta puede ser un uso contraproducente que despoja al rompecabezas de su diversión. El resolutor es, al fin y al cabo, una herramienta entre bastidores, y su verdadero valor reside precisamente en la verificación y el análisis para entregar buenos rompecabezas a quienes juegan.
Qué puedes aprender al escribir tu propio resolutor
Intentar escribir un resolutor de sudoku por ti mismo es una excelente práctica de programación. Esto se debe a que conceptos básicos de la informática - backtracking, recursión, propagación de restricciones y optimización de búsqueda - están condensados dentro de un solo rompecabezas. Primero lo pones en marcha con fuerza bruta ingenua, luego añades propagación de restricciones para acelerarlo, y además ideas el orden de búsqueda. En este proceso de mejora incremental, puedes sentir de primera mano cómo cambia la eficiencia de un algoritmo. El sudoku, familiar y fácil de comprobar, es un tema ideal para estudiar, y enseña la alegría de construir, distinta de la alegría de resolver.