Backtracking and Constraint Search

1Try, fail, undo

Build a candidate solution one decision at a time. The moment it cannot possibly work, abandon it and take the last decision back.

Backtracking is depth-first search over the tree of partial solutions. The tree is never built — it exists only as the shape of the recursion — and each node is a partial answer that may or may not extend to a real one.

def backtrack(state, choices):
    if is_complete(state):
        record(state)
        return

    for choice in choices:
        if not is_valid(state, choice):
            continue                 # PRUNE: skip this whole subtree

        make(state, choice)          # CHOOSE
        backtrack(state, choices)    # EXPLORE
        undo(state, choice)          # UN-CHOOSE  <-- the line people forget

2Subsets, permutations, combinations

Three shapes that between them cover most enumeration problems. The differences are two lines each.

Subsets. Each element is in or out, so the tree is binary and has 2ⁿ leaves. The idiom is to loop from a start index, which prevents you from producing the same subset in two different orders:

def subsets(nums):
    out, path = [], []

    def go(start):
        out.append(path[:])              # every node is an answer, not just the leaves
        for i in range(start, len(nums)):
            path.append(nums[i])         # choose
            go(i + 1)                    # explore — i+1, so no element repeats
            path.pop()                   # un-choose

    go(0)
    return out

Permutations. Order matters, so every unused element is a candidate at every position. n! results:

def permutations(nums):
    out, path = [], []
    used = [False] * len(nums)

    def go():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            go()
            path.pop()                   # un-choose, both halves of it
            used[i] = False

    go()
    return out

nums.sort()
...
    if i > start and nums[i] == nums[i - 1]:
        continue        # this value was already tried at this position

That third row is worth pausing on: recursing with i instead of i + 1 allows the same element to be chosen again, which is the entire difference between “combinations” and “combinations with repetition”. It is the same one-character distinction as forwards-versus-backwards in knapsack.

3Pruning is the algorithm

Without pruning, backtracking is brute force with extra steps. With it, searches that should take a century take a millisecond.

N-Queens: place n queens on an n × n board so that none attacks another. Placing one queen per row cuts the space from C(n², n) to nⁿ before any real work — and then pruning does the rest.

def n_queens(n):
    cols = set()
    diag = set()          # r - c is constant along one diagonal
    anti = set()          # r + c is constant along the other
    count = 0

    def place(row):
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue                       # PRUNE
            cols.add(col); diag.add(row - col); anti.add(row + col)
            place(row + 1)
            cols.discard(col); diag.discard(row - col); anti.discard(row + col)

    place(0)
    return count

Three kinds of pruning are worth naming, because you will reach for each of them in different problems:

• Constraint pruning — the partial solution already breaks a rule, so no extension can work. N-Queens above.
• Bound pruning (branch and bound) — the best possible completion of this branch is still worse than a solution you already have. Requires an optimistic estimate of what remains, which is the same idea as A*'s heuristic in Chapter 22.
• Symmetry pruning — this branch is a rotation, reflection or relabelling of one already explored. In N-Queens, fixing the first queen to the left half of the first row halves the work immediately.

4Constraint search: Sudoku

The same skeleton, plus one heuristic that changes everything: do not fill in the next cell — fill in the hardest one.

A naive Sudoku solver walks the grid left-to-right, top-to-bottom, trying 1–9 in each empty cell. It works, and on a hard puzzle it can take minutes, because it spends its time on cells with nine possibilities while a cell with exactly one sits untouched.

def solve(board):
    """board: 9x9 list of lists, 0 for empty. Solves in place, returns True on success."""
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empties = []

    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v:
                rows[r].add(v); cols[c].add(v); boxes[(r // 3) * 3 + c // 3].add(v)
            else:
                empties.append((r, c))

    def candidates(r, c):
        return [v for v in range(1, 10)
                if v not in rows[r] and v not in cols[c]
                and v not in boxes[(r // 3) * 3 + c // 3]]

    def go():
        if not empties:
            return True
        # MRV: pick the empty cell with the fewest options
        best_i, best = None, None
        for i, (r, c) in enumerate(empties):
            opts = candidates(r, c)
            if not opts:
                return False                  # contradiction: prune the whole branch
            if best is None or len(opts) < len(best):
                best_i, best = i, opts
                if len(opts) == 1:
                    break                     # cannot do better than forced
        r, c = empties.pop(best_i)
        b = (r // 3) * 3 + c // 3
        for v in best:
            board[r][c] = v
            rows[r].add(v); cols[c].add(v); boxes[b].add(v)
            if go():
                return True
            rows[r].discard(v); cols[c].discard(v); boxes[b].discard(v)
            board[r][c] = 0
        empties.insert(best_i, (r, c))        # un-choose the cell itself
        return False

    return go()

5When to backtrack, and when not to

Backtracking is what you use when the state space is too large to tabulate and no local rule is safe.

The signals in a problem statement are fairly reliable:

• “Find all…” — backtracking. DP counts and optimises; it does not enumerate.
• “Is there any assignment satisfying…” — constraint search.
• A permutation, arrangement or board position is the answer — backtracking.
• “How many ways” or “the minimum cost” — DP first; fall back to search only if the state space explodes.

Branch and bound is backtracking plus an optimistic estimate. Keep the best complete solution found so far; at each node, compute an upper bound on what this branch could possibly achieve; if the bound is no better than the incumbent, prune. It is how exact solvers for 0/1 knapsack, TSP and integer programming actually work in practice, and it is why they can handle instances whose brute-force size is astronomically large.

>_Playground

The three generators, N-Queens with and without pruning, and a Sudoku solver with and without MRV.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.