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
Elegir la celda con menos candidatos
Si se empieza por una celda con solo dos candidatos, al fallar el primer intento queda una única rama por probar. Esta elección determina en gran medida cuánto hay que buscar.
Colocar provisionalmente uno de sus candidatos
El número entra como jugada provisional, no como cifra confirmada, y se anota para poder deshacerla después.
Rellenar lo que la propagación de restricciones permita confirmar
Las celdas cuyos candidatos quedan reducidos a uno por esa colocación se rellenan en cadena, de modo que cualquier contradicción aparece pronto.
¿Ha surgido una contradicción?
Sí
Se retrocede el tablero hasta justo antes de la colocación provisional y se prueba otro candidato en la misma celda. Eso es el backtracking.
No
Si quedan celdas vacías, se vuelve al primer paso y se elige la siguiente celda.
Cuando todas las celdas están llenas, la solución está completa
Los pasos 1 a 4 forman un ciclo. Al retroceder solo se deshace la última colocación provisional, así que todo lo confirmado antes se conserva. Cuanto más se intercala la propagación de restricciones entre intentos, antes salen a la luz las contradicciones y menos ramas hay que probar.
Para puzles 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.