Exemple în care backtracking-ul poate fi folosit pentru a rezolva puzzle-uri sau probleme include:
- Puzzle-uri precum puzzle-ul celor două regine, cuvinte încrucișate, aritmetică verbală, Sudoku [nb 1]și Peg Solitaire.
- Probleme de optimizare combinatorie, cum ar fi analiza și problema rucsacului.
- Limbaje de programare logice precum Icon, Planner și Prolog, care utilizează backtracking-ul intern pentru a genera răspunsuri.
Table of Contents
Exemplu de problemă (The Knight’s tour problem)
Cavalerul este așezat pe primul bloc al unei scânduri goale și, deplasându-se conform regulilor șahului, trebuie să viziteze fiecare pătrat exact o dată.
Calea urmată de Knight pentru a acoperi toate celulele
Urmează tabla de șah cu 8 x 8 celule. Numerele din celule indică numărul de mutare al Cavalerului.
Algoritm naiv pentru turneul lui Knight
Algoritmul Naiv este de a genera toate tururile unul câte unul și de a verifica dacă turul generat îndeplinește constrângerile.
while there are untried tours
{
generate the next tour
if this tour covers all squares
{
print this path;
}
}
Algoritm de backtracking pentru turneul lui Knight
Urmează algoritmul Backtracking pentru problema turneului lui 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" )
