Backtracking
Algoritmo que explora soluciones por ensayo y error. Si llega a un callejón sin salida, retrocede al estado anterior y prueba otra opción.
El Backtracking es un algoritmo de resolución de problemas basado en búsqueda en profundidad. En un solver de Sudoku, se coloca provisionalmente un número en una celda vacía y, si se produce una violación de restricciones, se retrocede al estado anterior y se prueba otro número. Al explorar sistemáticamente todas las combinaciones, siempre encuentra la solución (si existe).
Rol en el solver de Sudoku
Para puzzles que no pueden resolverse solo con propagación de restricciones, el backtracking funciona como último recurso. Se coloca provisionalmente un número en la celda con menos candidatos y, si surge una contradicción, se retrocede. Combinado con la propagación de restricciones, el espacio de búsqueda se reduce drásticamente.
Diferencia con la resolución humana
Los humanos prefieren evitar el backtracking (adivinación) y resolver solo mediante pasos lógicamente confirmables. Esto se debe a las limitaciones de la memoria de trabajo. Recordar y gestionar simultáneamente múltiples estados hipotéticos es difícil para los humanos. El diseño de dificultad del Sudoku se basa en si un humano puede resolverlo sin adivinación.