Backtracking

Backtracking is a general algorithmic technique for solving constraint satisfaction problems and various combinatorial search tasks. It solves problems by constructing candidates incrementally and abandoning a partial candidate as soon as it becomes clear that it cannot be extended to a valid solution. The search typically proceeds in a depth-first manner, exploring one branch completely before moving to the next.

The method follows a simple pattern: select a variable, assign a value from its domain, and check the problem's constraints. If the assignment violates constraints or there is no feasible continuation from that point, the algorithm undoes the most recent decision (backtracks) and tries an alternative value or backtracks further. This continues until a solution is found or all possibilities are exhausted.

Backtracking is exponential in the worst case, since it may explore all possible assignments. Its practicality comes from problem structure and strong pruning, often aided by heuristics and constraint propagation, which eliminate impossible branches early.

Common applications include puzzle solving and CSPs such as the N-Queens problem, Sudoku, graph coloring, Hamiltonian paths, and subset-sum variants. It is also used in programming to search configuration spaces, generate test cases, and implement parsers or search-based algorithms.

Enhancements to backtracking include forward checking, arc consistency, and other forms of constraint propagation, as well as variable- and value-ordering heuristics (for example, selecting the most constrained variable or trying values in increasing order). Some systems combine backtracking with learning or backjumping to skip fruitless branches.

---