Backtracking

Backtracking

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 —

• checks if the node fails any constraint. If yes, this sub-tree gets pruned. The algorithm backtracks one step up and then steps down to a sibling node.
• checks if the node is a solution to the problem. If yes, the algorithm records the node as a valid solution. The algorithm may stop the search or carry on, as configured.
• generates a new layer of child nodes and recursively repeats this process.

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.