Backtracking Concepts

Backtracking is a search technique that builds an answer one piece at a time and, as soon as the choices made so far break a rule, steps back to the previous decision and tries something else. Unlike brute force, which generates every complete candidate and only then checks it, backtracking abandons hopeless paths halfway, so it often solves the same problem with a tiny fraction of the work. This chapter introduces the vocabulary, the basic template, and the situations where backtracking is the right tool.

The state-space tree

The easiest way to picture what backtracking explores is a state-space tree. The root is the empty state where nothing has been chosen yet, and each step down the tree adds one more choice. A leaf holds one complete candidate. Here is the tree that generates the permutations of [1, 2, 3]:

                 []
       /         |         \
     [1]        [2]        [3]
    /   \      /   \      /   \
 [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
   |     |     |     |     |     |
[1,2,3] ...                    [3,2,1]

Backtracking walks this tree depth first, but whenever it can tell that a node cannot lead to a valid solution, it skips the entire subtree below that node. This is called pruning.

Vocabulary

• Partial solution: the list of choices made so far, usually carried around as a list such as path.
• Candidates: the values that may be chosen next from the current state.
• Promising: a node is promising if extending it could still reach a solution.
• Pruning: stopping at a node that is not promising and returning to its parent.
• Constraint: a rule every solution must satisfy, such as "no two queens share a column" or "the sum must not exceed the target".

Choose, explore, unchoose

Almost every backtracking routine repeats the same three moves. Choose a candidate and add it to the partial solution, explore recursively from that state, and when the call returns, unchoose by removing what you added. The undo step is what lets every branch share a single path list.

def backtrack(path, choices, result):
    if is_solution(path):
        result.append(path[:])      # store a copy
        return
    for c in candidates(path, choices):
        if not is_valid(path, c):   # prune
            continue
        path.append(c)              # choose
        backtrack(path, choices, result)  # explore
        path.pop()                  # unchoose

If you write result.append(path) without the copy, every stored entry refers to the same list, which is empty by the time the search finishes. It is one of the most common backtracking bugs.