Backtracking: Attempt and Reversion

Backtracking explores a decision tree: make a choice, proceed recursively, undo the choice, try the next alternative.

It is trial and error with systematic retreat. Without undo, incorrect partial states remain.

Undo choices: Permutations [1].

Where used

Constraint solvers, Sudoku/planning, feature toggle combinations, regex engines (with cuts), game search. The try and undo pattern is behind many NP-hard exact solvers.

Depth

Backtracking searches a tree of partial decisions. Each node describes a partially constructed candidate, and each edge adds a choice. After an unsuccessful branch, the previous state is restored so that the next branch starts under the same initial conditions.

The central invariant is: upon entering a recursion level, the state contains exactly the decisions of the current path. Feasibility tests can prune branches early. Their quality often determines the runtime more strongly than the actual recursion, although the number of possible paths remains exponential in the worst case.

Difficulty levels

1. Draw a complete decision tree for a few choices.
2. Formulate a feasibility test that does not discard a valid solution.
3. Choose search order and bounds to exclude large subtrees early.

Pitfalls

Often, changes are not fully undone, or global data is shared between sibling branches. An overly aggressive cut is also incorrect: it may seemingly improve runtime but can silently remove solutions.