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 una celda vacía y, si surge una contradicción, se retrocede. La celda que se elige cambia el número de ramas: al elegir una celda con menos candidatos restantes, la ramificación de ese paso es menor. Reducir antes los candidatos disminuye las combinaciones que hay que probar.
Diferencia con la resolución humana
Al resolver con lápiz y papel, a veces se dice que se prefiere evitar la búsqueda por tanteo (adivinación) y avanzar solo con pasos lógicamente confirmables. Como razón se señala la carga de recordar y gestionar varios estados hipotéticos a la vez.