Backtracking, in depth: choose, explore, unchoose, and the pruning that makes exponential search usable

The state-space tree

Every backtracking problem has the same skeleton. There is a sequence of decisions: which column the queen in row 3 goes in, whether item 7 is in the subset, which digit fills a Sudoku cell. Each decision has a set of choices. Arrange the partial solutions as a tree: the root is the empty solution, each level is one decision, each edge is one choice, and the leaves are complete candidates. Backtracking is a depth-first walk of that tree which refuses to enter a subtree once it can prove the subtree contains no answer.

Depth-first matters. The walk keeps only the current path in memory, so the space cost is the depth of the tree, not its size, and the tree itself is never built. That is why backtracking can walk trees with billions of nodes on a laptop.

The template: choose, explore, unchoose

Almost every correct backtracking routine is a variation of the following function. The state is mutated in place and restored on the way back, which is cheaper than copying it at every level.

def backtrack(state, out):
    if is_complete(state):
        out.append(snapshot(state))      # copy: state keeps mutating after this
        return
    for choice in candidates(state):     # ordered: most constrained / most promising first
        if not feasible(state, choice):  # prune before recursing, not after
            continue
        apply(state, choice)             # choose
        backtrack(state, out)            # explore
        undo(state, choice)              # unchoose: exactly reverses apply

Three details decide whether the template is correct. First, undo must reverse apply exactly, on every exit path, including early returns and exceptions; a missed restore corrupts every later branch and produces wrong answers rather than crashes. Second, record a copy of the state when you find a solution, because the state keeps changing after you return. Third, check feasibility before recursing. A check at the top of the child call works, but pays a call and an apply/undo pair for every dead child.

If the problem asks for one solution rather than all of them, make the function return a boolean and stop at the first true. If it asks for the best one, keep the best score so far and use it as a bound.

Worked example: N-Queens with bitmasks

Place n queens on an n by n board so that none attack each other. The decision is the column for the queen in each row, so the tree has depth n and branching factor at most n. A queen attacks along its column and both diagonals. Represent the three attacked sets as bitmasks: cols, and two diagonal masks that shift by one column every time you move down a row. The free columns for the next row are then a single expression.

def n_queens(n):
    full = (1 << n) - 1
    solutions, nodes = 0, 0

    def place(cols, diag_l, diag_r):
        nonlocal solutions, nodes
        nodes += 1
        if cols == full:                     # one queen in every column => one per row
            solutions += 1
            return
        free = full & ~(cols | diag_l | diag_r)
        while free:
            bit = free & -free               # lowest free column
            free ^= bit
            place(cols | bit,
                  ((diag_l | bit) << 1) & full,   # attacks shift one column per row
                  (diag_r | bit) >> 1)

    place(0, 0, 0)
    return solutions, nodes

print(n_queens(8))   # (92, 2057)

The numbers below come from running this code and counting every call, including the root, against the tree that places one queen per row and checks validity only when the board is full.

Pruning at every level shrinks the search for n = 8 by a factor of roughly 9,000, and the gap widens with n. The bitmask representation matters too: each feasibility check is three ORs and a mask instead of a loop over earlier rows, so the per-node cost is a handful of machine operations. The general lesson is to make the feasibility check incremental: carry just enough state down the tree that each check is constant time.

Pruning: feasibility, bounds and ordering

There are two kinds of prune. A feasibility prune rejects a partial solution that already violates a constraint: two queens on a diagonal, a running sum above the target, a word that no longer matches the grid. A bound prune rejects a partial solution that is valid but provably cannot beat the best answer found so far. In a knapsack search, if the current value plus an optimistic estimate of what the remaining items could add is no better than the incumbent, the subtree is dead. The optimistic estimate must never underestimate what is achievable, or you will prune the optimum.

Sorting candidates turns many feasibility checks into a single break. In combination sum, where you find every multiset of candidates that adds to a target, sorting means that once one candidate exceeds the remaining amount every later one does too.

def combination_sum(candidates, target):
    candidates = sorted(candidates)
    out, path = [], []

    def go(start, remaining):
        if remaining == 0:
            out.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                break                        # sorted: every later candidate is bigger too
            if i > start and c == candidates[i - 1]:
                continue                     # same value at the same depth => same subtree
            path.append(c)
            go(i, remaining - c)             # i, not i + 1: a value may be reused
            path.pop()

    go(0, target)
    return out

For candidates [2, 3, 6, 7] and target 7, this version makes 10 calls and returns [[2, 2, 3], [7]]. The same search without sorting and break, which only stops when the remainder goes negative, makes 28. Every avoided call also avoids its whole subtree, so the gap grows with the target.

Duplicates and symmetry

When the input contains repeated values, a naive enumeration produces the same answer several times, once per way of picking equal elements. The standard fix is visible in the code above: sort, and at any single depth skip a value equal to the one just tried at that depth. Two choices with the same value at the same level lead to identical subtrees, so exploring one is enough. For [1, 2, 2], the subset version of this rule yields exactly six subsets: [], [1], [1, 2], [1, 2, 2], [2], [2, 2].

Symmetry is the same idea at the level of the whole problem. N-Queens solutions come in mirror pairs, so you can restrict the first queen to the left half of the first row and double the count, taking care with the middle column when n is odd. In graph colouring, fix the first vertex to colour 0. Every symmetry you break divides the tree by the size of the symmetry group, and it is usually one line of code. Breaking a symmetry that is not really there silently drops solutions, so test against brute force on small inputs.

Variable ordering and constraint propagation

In N-Queens the decisions have a natural order: row by row. In many problems you choose the order, and it matters enormously. The minimum remaining values heuristic says: decide next the variable with the fewest legal choices. In Sudoku that is the empty cell with the fewest candidate digits. If a cell has one candidate you lose nothing by filling it now; if it has zero you discover the dead end immediately, at the top of a subtree rather than deep inside it.

Constraint propagation goes further. After each choice, remove the chosen value from the candidate sets of every related variable, and if any set becomes a single value, assign it and propagate again. This is called forward checking in its simplest form. On easy Sudoku puzzles propagation alone solves the grid without branching. The price is that propagation modifies many variables per decision, so the undo step must restore all of them. A trail, a stack of changes recorded as they happen and replayed in reverse on backtrack, is the standard way to keep that correct.

Estimating the tree before you run it

Before committing a long job, it helps to know whether a search will take a second or a year. Knuth's estimator does this without running the search. Walk one random path from the root, choosing a child uniformly at each level. If the branching factors along the path are d1, d2, d3, then 1 + d1 + d1 d2 + d1 d2 d3 is an unbiased estimate of the number of nodes in the tree. Average many such probes.

import random

def estimate_tree_size(root, children, probes=10_000, rng=random.Random(1)):
    """Knuth (1975): walk one random root-to-leaf path; the product of branching
    factors seen so far estimates how many nodes exist at that depth."""
    total = 0
    for _ in range(probes):
        node, weight, estimate = root, 1, 1
        while True:
            kids = children(node)
            if not kids:
                break
            weight *= len(kids)
            estimate += weight
            node = rng.choice(kids)
        total += estimate
    return total / probes

Applied to the pruned N-Queens tree with 20,000 probes, the estimate was 2,068 nodes for n = 8 against a true 2,057, and 858,735 for n = 12 against a true 856,189. Variance is high on lopsided trees, so treat the result as an order of magnitude. It is also a good regression test: an estimate that jumps tenfold after a code change usually means a prune stopped firing.

When backtracking is really dynamic programming

Backtracking explores paths; dynamic programming explores states. If two different paths through your tree lead to partial solutions whose futures are identical, the search repeats work, and memoising on that future-determining state collapses the tree into a graph. Target sum is the standard example: assigning a sign to each number is a binary tree of depth n, but the future depends only on the index and the running sum, so the number of distinct states is n times the range of sums. The same shift turns the exponential brute force for the travelling salesman problem into the Held-Karp recurrence over subsets.

The test is to write down what the rest of the search actually depends on. If it is small, such as an index, a remaining capacity, a bitmask of used items, memoise. If it is the whole partial solution, as in N-Queens, where the exact placement of every queen constrains the future, memoisation buys nothing and backtracking with strong pruning is the right tool. See dynamic programming, target sum and the travelling salesman DP for the state-based side, and greedy algorithms for the case where one choice per level is provably enough and no backtracking is needed at all.

Engineering the search

Recursion depth is the first production problem. CPython's default recursion limit is 1,000, so a search whose depth equals the input length fails on long inputs; raise the limit deliberately or convert to an explicit stack of (state, next-choice-index) frames, which also lets you checkpoint and resume. The grid-specific version of that rewrite, with in-place marking, is in word search with backtracking.

Copying is the second. Passing path + [x] into each call allocates a new list per node; mutating one list and popping on return costs O(1). Copy only when you record a solution. Third, bound the work. A search that serves user requests needs a node budget or a deadline checked every few thousand nodes, and a defined answer when the budget runs out, such as the best solution so far or an explicit timeout.

What to do next

1. Write down the decision per level, the choices per decision and the complete condition before coding.
2. Implement the template with in-place apply and undo, and test it against a brute-force count on inputs small enough to enumerate.
3. Move every feasibility check before the recursive call and make it incremental, carrying masks or running totals down the tree.
4. Sort candidates, add the equal-sibling skip, and break any symmetry you can prove.
5. Order decisions by fewest remaining choices, and add propagation with a trail if the problem is a constraint problem.
6. Run Knuth's estimator before any long job, and re-run it after changes as a regression check on pruning.
7. Ask what the future depends on; if it is a small state, memoise and switch to DP.