In most recursion algorithms, the next recursive call is known. factorial(8) = 8 * factorial(7). In backtracking, the correct next recursive call is unknown. Each call is tentative. If the tentative call leads to a solution, great. If not, the call is undone (backtracked), the argument updated, and another tentative recursive call is done.
The ability of backtracking algorithms to try solutions that ultimately fail and continue on to the next solution makes them ideal for puzzle solving. They tend to be extremely efficient because each dead end prevents later recursive calls from being computed.
- Sudoku
- Knights Tour
- N Queens
- Pizza Hut pi day challenge
- 'numpy'