Backtracking is a general methodology for devising algorithms to solve open-ended constraint-based problems. The method builds potential solutions incrementally while abandoning candidates as soon as it can be determined that they fail to satisfy constraints. Real-life applications of backtracking involve solving constraint-satisfaction problems like Sudoku. Brute-force solutions for such problems are computationally infeasible.
Backtracking works by representing each increment in the solution as a new layer of nodes in a tree data structure, where the root node is the starting state of the problem. The algorithm traverses the tree depth-first, generating layers on demand. At each node, the algorithm —
This process of tree-pruning and early exit prevents the algorithm from generating and traversing the entire solution tree. Generating the children nodes only for nodes that do not fail the checks and are not themselves solutions also prevents storage consumption from increasing.