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 puzzles 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 puzzles 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 puzzles 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.
Que es realmente la velocidad del resolutor
Un resolutor de sudoku puede resolver en un instante gracias a una combinacion de una velocidad de prueba incomparable a la de un humano y artificios que eliminan el desperdicio. El backtracking ingenuo por si solo es lo bastante rapido para el tamano fijo 9x9, ya que una computadora puede probar millones de colocaciones de numeros por segundo. Pero anadir propagacion de restricciones y optimizacion del orden de busqueda reduce drasticamente el numero de pruebas en si, resolviendo al instante incluso los rompecabezas mas dificiles. La clave es que la esencia de la velocidad reside no solo en la velocidad de procesamiento, sino en lo habilmente que acotas el rango de busqueda. Un diseno que poda rapido las ramas obviamente inutiles, en vez de probarlo todo a ciegas, determina la eficiencia.
El sudoku como problema de cobertura exacta
Matematicamente, el sudoku puede formularse como una especie de problema de cobertura exacta. El acto de colocar un numero en cada celda se expresa como una seleccion 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 tecnica que acelera el backtracking quitando y restaurando temporalmente elementos de una lista enlazada, usada para la resolucion rapida de rompecabezas en general, no solo del sudoku. Que aparezca una solucion poderosa distinta al cambiar la perspectiva sobre el mismo problema es uno de los placeres de la informatica.
Usos y limites del resolutor
Un resolutor de sudoku no sirve solo para producir respuestas. Lo importante en la practica es mas bien la verificacion de la unicidad en la generacion de rompecabezas y la estimacion de la dificultad. El generador usa el resolutor para confirmar que el rompecabezas que creo tiene de verdad una sola solucion, y juzga que tecnicas hacen falta mediante un resolutor que imita los metodos humanos. Por otro lado, usar el resolutor para mostrar la respuesta puede ser un uso contraproducente que despoja al rompecabezas de su diversion. El resolutor es, al fin y al cabo, una herramienta entre bastidores, y su verdadero valor reside precisamente en la verificacion y el analisis para entregar buenos rompecabezas a quienes juegan.
Que puedes aprender al escribir tu propio resolutor
Intentar escribir un resolutor de sudoku por ti mismo es una excelente practica de programacion. Esto se debe a que conceptos basicos de la informatica - backtracking, recursion, propagacion de restricciones y optimizacion de busqueda - estan condensados dentro de un solo rompecabezas. Primero lo pones en marcha con fuerza bruta ingenua, luego anades propagacion de restricciones para acelerarlo, y ademas ideas el orden de busqueda. En este proceso de mejora incremental, puedes sentir de primera mano como cambia la eficiencia de un algoritmo. El sudoku, familiar y facil de comprobar, es un tema ideal para estudiar, y ensena la alegria de construir, distinta de la alegria de resolver.