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.