Los ejemplos en los que se puede usar el retroceso para resolver acertijos o problemas incluyen:
- Rompecabezas como ocho reinas, crucigramas, aritmética verbal, Sudoku [nb 1] y Peg Solitaire.
- Problemas de optimización combinatoria como el análisis sintáctico y el problema de la mochila.
- Lenguajes de programación lógica como Icon, Planner y Prolog, que utilizan el retroceso interno para generar respuestas.
Problema de ejemplo (el problema de la gira del Caballero)
El caballo se coloca en el primer bloque de un tablero vacío y, moviéndose según las reglas del ajedrez, debe visitar cada casilla exactamente una vez.
Camino seguido por Knight para cubrir todas las celdas
A continuación se muestra un tablero de ajedrez con 8 x 8 celdas. Los números en las celdas indican el número de movimiento del Caballero.
Algoritmo ingenuo para la gira de Knight
El algoritmo ingenuo es generar todos los recorridos uno por uno y comprobar si el recorrido generado cumple las restricciones.
while there are untried tours { generate the next tour if this tour covers all squares { print this path; } } Algoritmo de retroceso para la gira de Knight
A continuación se muestra el algoritmo Backtracking para el problema de gira de Knight.
If all squares are visited print the solution Else a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" )