Backtracking

overview

Summary

Backtracking is a general algorithmic technique for exploring a search space by building solutions incrementally and abandoning partial candidates as soon as they violate constraints. It is often implemented with recursion and a depth-first search strategy, and it is used for solving constraint satisfaction problems, generating permutations and combinations, pathfinding in grids, and many NP-complete problems. Performance relies on effective pruning, variable/value ordering, and careful state management.