Példák, ahol a visszalépés felhasználható rejtvények vagy problémák megoldására:
- Rejtvények, például nyolc királynő puzzle, keresztrejtvények, verbális számtan, Sudoku [nb 1] és Peg Solitaire.
- Kombinatorikus optimalizálási problémák, például elemzés és hátizsák probléma.
- Azok a logikai programozási nyelvek, mint az Icon, a Planner és a Prolog, amelyek belső visszacsatolást használnak a válaszok generálásához.
Példa probléma (A lovag túra problémája)
A lovagot egy üres tábla első blokkjára helyezik, és a sakk szabályai szerint mozogva pontosan egyszer kell meglátogatnia minden négyzetet.
A Knight által követett út az összes cella lefedésére
Következik egy sakktábla 8 x 8 cellával. A cellákban lévő számok a Knight lépésszámát jelzik.
Naiv algoritmus a Knight turnéjához
A Naiv algoritmus az, hogy az összes túrát egyesével generálja, és ellenőrizze, hogy a létrehozott túra megfelel-e a megszorításoknak.
while there are untried tours { generate the next tour if this tour covers all squares { print this path; } } Backtracking algoritmus a Knight turnéjához
Az alábbiakban bemutatjuk a Knight turnéjának visszalépés algoritmusát.
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" )