Exemple în care backtracking-ul poate fi folosit pentru a rezolva puzzle-uri sau probleme include:

  1. Puzzle-uri precum puzzle-ul celor două regine, cuvinte încrucișate, aritmetică verbală, Sudoku [nb 1]și Peg Solitaire.
  2. Probleme de optimizare combinatorie, cum ar fi analiza și problema rucsacului.
  3. Limbaje de programare logice precum Icon, Planner și Prolog, care utilizează backtracking-ul intern pentru a genera răspunsuri.

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.

Soluția turului cavalerului - de Euler

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" )

Iată o explicație video pentru dvs.