Backtracking
Backtracking systematically explores all candidate solutions, undoing choices (backtracking) when a branch becomes infeasible; it is used for constraint satisfaction problems.
Purpose
To solve combinatorial search and constraint satisfaction problems such as N-queens and Sudoku.
Mechanism
It depth-first searches the solution-space tree, extending one candidate at each step and backtracking when a constraint is violated. Pruning (constraint propagation, bounding) shrinks the search space. Classics: N-queens, graph coloring, subset sum.
Use cases
- Constraint satisfaction
- Combinatorial search
- Puzzle solving