Backtracking (Quay lui)Backtracking

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

Backtracking is the technique for problems where a solution is a sequence of decisions that must jointly satisfy some constraints. You build the solution one decision at a time; whenever the partial solution can no longer be completed into a valid one, you undo the most recent decision and try the next alternative. That undo — the “backtrack” — is what gives the technique its name.

Structurally, backtracking is a depth-first search over an implicit decision tree. The tree is never materialised in memory; it exists only as the sequence of recursive calls. Each node is a partial solution, each edge is one decision, and each leaf is either a complete solution or a dead end. What separates backtracking from plain brute force is the word implicit: brute force enumerates all kⁿ leaves, while backtracking abandons an entire subtree the instant its root is known to be infeasible. On the 8-queens puzzle, brute force over all placements of 8 queens on 64 squares is 4.4 billion candidates; backtracking with the row/column/diagonal constraints visits about 2 000 nodes.

That pruning is the whole value proposition, and it is also the honest limitation. Backtracking is still exponential in the worst case — if the constraints never fire, you enumerate the full tree. It is the right technique when the constraints are strong enough to cut most of the space early, and the wrong one when they are not (in which case you want dynamic programming, if the subproblems overlap, or an approximation, if they do not).

The payoff for learning it is that a very large family of problems collapses into a single ten-line template. Subsets, permutations, combinations, N-queens, Sudoku, graph colouring, word search, crossword filling, regex matching, SAT solving, and constraint programming are all the same code with a different is_valid predicate.

Fundamentals

Backtracking as DFS over a decision tree

Consider generating all subsets of [1, 2, 3]. The decision at each level is “do I include element i?” — two branches per level, three levels, 2³ = 8 leaves:

                          []                          <- level 0: decide about 1
                    /            \
              include 1        exclude 1
                 /                    \
              [1]                     []              <- level 1: decide about 2
            /      \               /      \
       [1,2]       [1]         [2]        []          <- level 2: decide about 3
       /   \       /   \       /   \      /   \
  [1,2,3] [1,2] [1,3] [1]  [2,3]  [2]  [3]   []       <- 8 leaves = 8 subsets

The recursion walks this tree depth-first. path is the current root-to-node prefix, and it is mutated on the way down and restored on the way up — which is precisely why the same list object can serve every node without copying it at each step.

The critical mental model: the call stack holds the path from the root to the current node. At depth d, there are exactly d frames alive, each remembering which branch it is currently exploring. Un-choosing on the way back up restores the state so that the sibling branch sees the same world the current branch saw when it started. Get that restoration wrong — forget one line of undo — and the bug manifests as extra elements appearing in unrelated results, which is maddening to debug.

The general template: choose / explore / un-choose

Every backtracking solution is this shape:

def backtrack(state, path, results):
    if is_solution(state, path):
        results.append(path[:])        # COPY — path keeps mutating after this
        return                         # (or don't return, if longer solutions also count)

    for choice in candidates(state, path):
        if not is_valid(state, path, choice):
            continue                   # PRUNE — skip this entire subtree

        make(state, path, choice)      # 1. CHOOSE   — apply the decision
        backtrack(state, path, results)  # 2. EXPLORE — recurse one level deeper
        undo(state, path, choice)      # 3. UN-CHOOSE — restore exactly what CHOOSE changed

Five decisions define any concrete instance:

Three rules that prevent almost all backtracking bugs:

1. undo must be the exact inverse of make. Every mutation in make needs a line in undo. If make adds to three sets, undo removes from three sets. Writing the two lines adjacently and reading them as a pair is the discipline.
2. Copy the path when you record a solution. results.append(path) appends a reference; the list keeps mutating and you end up with n identical empty lists. path[:] (or list(path), or tuple(path)) is mandatory.
3. Prune before you recurse, not after. Checking validity at the top of the child call also works, but checking it in the parent’s loop avoids a function call per dead branch — and, more importantly, it is where a domain-specific pruning rule naturally belongs.

Backtracking versus brute force versus DFS

The visited-set distinction is worth dwelling on, because it is the most common conceptual confusion. In graph DFS you mark a node visited permanently — you never want to enter it again, from any path. In backtracking you mark state as used and then un-mark it on the way back, because a different prefix may legitimately need it. The word-search example below shows both behaviours in one function: a cell is marked while it is on the current path (so the path cannot self-intersect) and unmarked afterwards (so another path may use it).

Key Concepts

Subsets — the power set

def subsets(nums):
    """All 2^n subsets. Theta(n · 2^n) time (2^n subsets, O(n) to copy each),
       Theta(n) auxiliary space for the recursion + path."""
    results, path = [], []

    def backtrack(start):
        results.append(path[:])            # EVERY node is a valid subset, not just leaves
        for i in range(start, len(nums)):
            path.append(nums[i])           # choose
            backtrack(i + 1)               # explore — i+1 forbids reuse and enforces order
            path.pop()                     # un-choose

    backtrack(0)
    return results

print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

The start parameter is the whole trick for combination-style problems: by only considering indices ≥ start, each subset is generated exactly once in increasing index order, so [1, 3] and [3, 1] never both appear. Removing it would generate all n!-ish orderings instead.

Handling duplicates requires one more line. Sort first, then skip a candidate that equals its predecessor at the same tree level:

def subsets_with_dups(nums):
    """Distinct subsets when nums may repeat. Still Theta(n · 2^n) worst case."""
    results, path = [], []
    nums = sorted(nums)                    # duplicates must be adjacent for the skip to work

    def backtrack(start):
        results.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                   # same value already tried at THIS level -> prune
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return results

print(subsets_with_dups([1, 2, 2]))        # [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

i > start is the load-bearing condition: it skips duplicates among siblings (which produce identical subtrees) while still allowing a duplicate to be used deeper in the path ([2, 2] is a legitimate subset). This is the first real example of pruning by symmetry — two branches that generate the same subtree, so only one needs exploring.

Permutations

def permutations(nums):
    """All n! orderings. Theta(n · n!) time, Theta(n) auxiliary space."""
    results, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):         # is_solution: every element placed
            results.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue                   # prune: already in the current path
            used[i] = True                 # choose
            path.append(nums[i])
            backtrack()                    # explore
            path.pop()                     # un-choose (both halves!)
            used[i] = False

    backtrack()
    return results

print(len(permutations([1, 2, 3, 4])))     # 24

Note the difference from subsets: permutations scan all indices every time (order matters, so [1, 2] and [2, 1] are both wanted) and use a used array instead of a start index. That is the general distinction — start for combinations, used for permutations.

The Θ(n · n!) bound is tight and brutal: n = 11 is already 40 million permutations, n = 13 is 6 billion. Any problem whose only formulation is “try every permutation” is unsolvable past about n = 12, which is why the travelling salesperson problem needs either DP (Θ(2ⁿ · n²) Held–Karp, usable to n ≈ 20) or a heuristic.

N-queens — pruning that changes the exponent

Place n queens on an n × n board so no two attack each other. The naive candidate space — choose n squares out of n² — is C(64, 8) ≈ 4.4 × 10⁹ for n = 8. Two observations shrink it enormously:

1. Exactly one queen per row. So the decision at depth r is only “which column in row r”, reducing the space to nⁿ, and with the column constraint to n! = 40 320.
2. Diagonals have a constant-index identity. For a \ diagonal, row − col is constant; for a / diagonal, row + col is constant. So checking a diagonal conflict is an O(1) set lookup rather than an O(n) scan back through the board.

     row - col  (the "\" diagonals)        row + col  (the "/" diagonals)

       c0  c1  c2  c3                        c0  c1  c2  c3
  r0 [  0   -1  -2  -3 ]                r0 [  0    1   2   3 ]
  r1 [  1    0  -1  -2 ]                r1 [  1    2   3   4 ]
  r2 [  2    1   0  -1 ]                r2 [  2    3   4   5 ]
  r3 [  3    2   1   0 ]                r3 [  3    4   5   6 ]

  every "\" diagonal shares one value    every "/" diagonal shares one value

def solve_n_queens(n):
    """All solutions to the n-queens puzzle. Three O(1) sets make each check constant time."""
    solutions = []
    placement = []                         # placement[r] = column of the queen in row r
    cols = set()                           # occupied columns
    diag = set()                           # occupied "\" diagonals, keyed by row - col
    anti = set()                           # occupied "/" diagonals, keyed by row + col

    def backtrack(row):
        if row == n:                       # is_solution: all rows filled
            solutions.append(placement[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue                   # PRUNE: this square is attacked
            cols.add(col)                  # choose — three mutations
            diag.add(row - col)
            anti.add(row + col)
            placement.append(col)

            backtrack(row + 1)             # explore

            placement.pop()                # un-choose — exactly three inverses
            cols.remove(col)
            diag.remove(row - col)
            anti.remove(row + col)

    backtrack(0)
    return solutions

def render(placement):
    n = len(placement)
    return "\n".join("".join("Q" if c == placement[r] else "." for c in range(n))
                     for r in range(n))

sols = solve_n_queens(8)
print(len(sols))                           # 92
print(render(sols[0]))

Backtracking explores roughly 2 % of the n! space at n = 12. That is a large constant-factor saving but not a change in asymptotic class — the growth is still super-exponential, which is why n = 20 (39 billion solutions) is out of reach. Pruning buys you a handful of extra n, not an unbounded amount. Knowing that distinction is what stops you from promising a stakeholder that “we’ll just add more pruning.”

A further optimization worth mentioning: symmetry breaking. The board has 8-fold symmetry (4 rotations × reflection), so restricting the first queen to the left half of row 0 and multiplying the count works, roughly halving the search. Symmetry breaking is one of the highest-leverage pruning techniques in constraint problems generally.

Sudoku — backtracking plus constraint propagation

Naive Sudoku backtracking — walk cells in reading order, try 1–9 in each empty cell — solves easy puzzles instantly and chokes on hard ones. The fix is constraint propagation: instead of picking the next cell arbitrarily, compute each empty cell’s candidate set and choose the cell with the fewest candidates. This is the MRV (minimum remaining values) heuristic, and it is the single most effective addition to a backtracking solver.

def solve_sudoku(board):
    """Solve a 9x9 Sudoku in place. board uses 0 for empty. Returns True if solvable.

    Two ideas beyond plain backtracking:
      - candidates(): constraint propagation, computing the legal digits for a cell
      - MRV: always branch on the most constrained cell, so the tree is narrowest at the top
    """
    def candidates(r, c):
        used = set(board[r])                               # row constraint
        used |= {board[i][c] for i in range(9)}            # column constraint
        br, bc = 3 * (r // 3), 3 * (c // 3)                # 3x3 box constraint
        used |= {board[br + i][bc + j] for i in range(3) for j in range(3)}
        return [d for d in range(1, 10) if d not in used]

    # MRV: find the empty cell with the fewest legal digits
    target, best = None, None
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                cands = candidates(r, c)
                if not cands:
                    return False                           # dead end — prune the whole branch
                if best is None or len(cands) < len(best):
                    target, best = (r, c), cands
                    if len(cands) == 1:
                        break                              # forced move — stop scanning this row
    if target is None:
        return True                                        # no empty cells: solved

    r, c = target
    for digit in best:
        board[r][c] = digit                                # choose
        if solve_sudoku(board):                            # explore
            return True
        board[r][c] = 0                                    # un-choose
    return False

puzzle = [
    [5,3,0, 0,7,0, 0,0,0], [6,0,0, 1,9,5, 0,0,0], [0,9,8, 0,0,0, 0,6,0],
    [8,0,0, 0,6,0, 0,0,3], [4,0,0, 8,0,3, 0,0,1], [7,0,0, 0,2,0, 0,0,6],
    [0,6,0, 0,0,0, 2,8,0], [0,0,0, 4,1,9, 0,0,5], [0,0,0, 0,8,0, 0,7,9],
]
print(solve_sudoku(puzzle))                                # True
print(puzzle[0])                                           # [5, 3, 4, 6, 7, 8, 9, 1, 2]

Three things this demonstrates that generalise to every constraint-satisfaction problem:

• Early failure detection. if not cands: return False abandons the branch the moment any cell has no legal value, without waiting to reach that cell. This is called forward checking, and it typically cuts the tree by an order of magnitude.
• Variable ordering (MRV). Branching on a cell with 2 candidates instead of 7 makes the tree narrow at the top, where narrowing matters most. A cell with exactly 1 candidate is a forced move with no branching at all — which is why the break short-circuits the search for a better cell.
• The state is the board itself. make writes a digit, undo writes back 0. No separate bookkeeping structure is needed, but the discipline of pairing the two lines still applies.

The theoretical worst case is Θ(9^m) for m empty cells, but with propagation, a standard 17-clue puzzle solves in milliseconds. This gap between worst case and practice is the defining characteristic of backtracking, and it is why the technique is used in real SAT and constraint solvers despite its terrible worst-case bound. Production solvers extend the same idea with arc consistency (AC-3), which propagates constraints between pairs of cells until nothing more can be deduced, and conflict-driven clause learning (CDCL), which remembers why a branch failed so the same failure is never rediscovered.

Word search on a grid — backtracking on an implicit graph

Given a grid of characters and a word, decide whether the word can be traced through orthogonally adjacent cells without reusing a cell.

def word_search(board, word):
    """Theta(R · C · 3^L) worst case, where L = len(word).
       3, not 4, because after the first step you never revisit the cell you came from.
       Theta(L) space for the recursion; the visited mark is stored IN the board."""
    if not word:
        return True
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, i):
        if i == len(word):
            return True                    # is_solution: whole word matched
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False                   # prune: off the grid
        if board[r][c] != word[i]:
            return False                   # prune: character mismatch

        saved = board[r][c]
        board[r][c] = "#"                  # choose: mark as on the current path
        found = (backtrack(r + 1, c, i + 1) or backtrack(r - 1, c, i + 1) or
                 backtrack(r, c + 1, i + 1) or backtrack(r, c - 1, i + 1))
        board[r][c] = saved                # un-choose: the cell is free for other paths
        return found

    return any(backtrack(r, c, 0) for r in range(rows) for c in range(cols))

grid = [list("ABCE"), list("SFCS"), list("ADEE")]
print(word_search(grid, "ABCCED"))         # True
print(word_search(grid, "ABCB"))           # False — 'B' would need to be reused

The board[r][c] = "#" / board[r][c] = saved pair is the clearest illustration of why backtracking differs from graph DFS. A permanent visited set would be wrong here: cell (0,1) is unusable while it is on the current path, but perfectly usable by a search that starts elsewhere. Marking in place also avoids allocating a visited set per start position, which matters when this is called for thousands of words.

Two useful extensions:

• Character-count pre-check. If the word contains more Es than the grid does, return False before searching at all — an O(RC) check that can skip an exponential search.
• Trie-based multi-word search. Searching for 10 000 words one at a time repeats the same grid walks. Putting the dictionary in a trie and walking the grid once, descending the trie in lockstep, turns Θ(W · R · C · 3^L) into roughly Θ(R · C · 3^L). This is the standard “Word Search II” solution and a good example of choosing the right auxiliary structure to prune.

Complexity analysis of backtracking

The generic bound is (number of nodes in the search tree) × (work per node), where the node count is bounded by the branching factor b raised to the depth d:

nodes  <=  1 + b + b² + ... + b^d  =  O(b^d)

Three caveats about these numbers:

• Space is Θ(d), not Θ(b^d). The tree is never stored; only the current root-to-node path lives on the call stack. This is the great memory advantage of DFS-based search over BFS-based search, and it is why backtracking can explore a 2¹⁰⁰-node tree in 100 stack frames. Watch the recursion depth limit if d can exceed ~1000.
• The output can dominate. Generating all 2ⁿ subsets is Ω(2ⁿ) no matter how clever you are — you have to write them down. When the output is exponential, no algorithm is polynomial, and complaining about the bound is meaningless. This is why these are called output-sensitive problems.
• The worst-case bound is often wildly pessimistic. N-queens’ bound is O(n!) but pruning visits ~2 % of it; Sudoku’s bound is O(9⁵¹) but real puzzles solve in microseconds. Measure, do not extrapolate from the bound. Conversely, never rely on pruning holding up for adversarial input.

Pruning and constraint propagation

Pruning is the difference between a technique and a toy. The catalogue, roughly in order of how much they typically buy:

1. Feasibility pruning (constraint checking). Reject a choice that violates a constraint immediately, before recursing. This is is_valid in the template, and it is mandatory — without it you have brute force with extra steps.
2. Forward checking / early failure detection. After making a choice, check whether any future variable now has an empty domain. If so, this branch is dead even though no constraint is violated yet. Sudoku’s if not cands: return False is exactly this.
3. Variable ordering (MRV / most-constrained-first). Branch on the decision with the fewest options. This narrows the tree where it is widest and is usually worth more than any other single heuristic.
4. Value ordering (least-constraining-value). Among the legal values for the chosen variable, try first the one that eliminates the fewest options for the remaining variables. Helps when you only need one solution; irrelevant when you need all of them.
5. Symmetry breaking. If two branches generate isomorphic subtrees, explore one. The i > start and nums[i] == nums[i-1] line in subsets_with_dups and the first-queen-in-the-left-half trick are both instances.
6. Bound pruning (branch and bound). For optimization rather than satisfaction: compute an optimistic bound on the best value any completion of the current partial solution could achieve, and abandon the branch if it cannot beat the best solution found so far. This turns backtracking into branch and bound and is what makes exact TSP solvers practical up to a few hundred cities. See ./20-brute-force-greedy-and-randomised-algorithms.md.
7. Memoization of failed states. If the same state can be reached by different decision orders, cache the fact that it failed. This is the point where backtracking starts turning into dynamic programming.

Constraint propagation is the umbrella term for 2–4: after each decision, deduce as much as possible about the remaining variables before branching again. The extreme version — propagate until a fixed point, using arc consistency — solves many puzzle instances without any search at all. Modern SAT and CP solvers spend most of their engineering effort on propagation, not on the search loop, precisely because a decision avoided is worth an entire subtree.

Relationship to DFS, brute force, and dynamic programming

   brute force              backtracking                dynamic programming
   -----------              ------------                -------------------
   enumerate ALL     +prune->  enumerate,          +memoize->  enumerate each
   candidates                  abandoning                       DISTINCT state once
                               infeasible subtrees
   O(k^n) always              O(k^n) worst case,               polynomial when the
                              usually far less                 state space is polynomial

• Backtracking is brute force plus pruning. Same enumeration, same asymptotic worst case, radically different practical behaviour. If you remove every is_valid check from a backtracking solution, you get the brute force.
• Backtracking is DFS on an implicit tree. Same traversal order, same O(depth) space. The differences are that the tree is generated on the fly rather than stored, and that state is undone on the way back up rather than marked permanently. Graph DFS needs a visited set because graphs have cycles; a decision tree does not.
• Backtracking and DP solve overlapping halves of the same space. They diverge on whether states repeat. If two different decision sequences lead to the same state and the answer depends only on the state, you are recomputing — memoize, and you have dynamic programming. If every path leads to a distinct state (as in permutations, where the path is the answer), there is nothing to memoize and backtracking is the only option.

The subset-sum problem shows the boundary sharply. Backtracking over “include or exclude each element” is O(2ⁿ). But the state that actually matters is only (index, remaining_sum) — many different subsets reach the same remaining sum — so memoizing on that pair gives O(n · target) pseudo-polynomial DP. When you can compress the path into a small state, switch to DP. When you cannot, backtrack and prune hard.

A related technique worth knowing: iterative deepening runs a depth-limited backtracking search with limit 1, then 2, then 3, and so on. It keeps DFS’s O(d) memory while getting BFS’s guarantee of finding the shallowest solution first, at the cost of re-exploring the top of the tree — which is cheap, because a tree’s last level contains most of its nodes. IDA* (iterative deepening with an A* heuristic) is the standard way to solve the 15-puzzle and Rubik’s cube optimally; see ./14-shortest-path-algorithms.md for the A* half of that.

Best Practices

• Write the template first, then fill in the five slots. is_solution, candidates, is_valid, make/undo, and result handling. Every backtracking problem is these five decisions; starting from the template stops you from reinventing the control flow each time.
• Pair every make with its undo on adjacent lines, and read them together. A missing undo is the single most common backtracking bug, and its symptom — state leaking into sibling branches — looks nothing like its cause.
• Copy the path when you record a solution. results.append(path) stores a reference to a list that is still being mutated. Use path[:], list(path), or tuple(path).
• Prune in the parent loop, before recursing. It avoids a call per dead branch and puts the domain-specific rule where it reads naturally.
• Add the most-constrained-first heuristic before micro-optimizing anything else. Choosing which variable to branch on is worth more than any constant-factor improvement to the inner loop. In Sudoku, MRV alone is the difference between seconds and milliseconds.
• Detect dead ends as early as you can compute them. Checking after a choice whether any remaining variable has an empty domain (forward checking) routinely cuts the tree by 10× or more.
• Break symmetry when branches are isomorphic. Sorting the input and skipping equal siblings, or fixing the first decision up to symmetry, prunes duplicate work that no other technique will catch.
• State the complexity in the docstring, with the reason. Theta(n · 2^n) alone is not useful; 2^n subsets, O(n) to copy each is. It tells the next reader what to attack if it is too slow.
• Bound the input size explicitly. Backtracking is exponential, so an endpoint whose input size is user-controlled needs a hard cap and a clear error. “It’s fast in practice” is not a security property.
• Watch the recursion depth. Depth equals the number of decisions. For grid or string problems the depth can approach the input size, and Python’s default 1000-frame limit is real — see ./19-recursion-and-divide-and-conquer.md.
• Check whether states repeat before optimizing the pruning. If two decision paths can reach the same state, memoize and you have DP — a polynomial algorithm beats any amount of pruning on an exponential one.
• Prefer mutating a shared path over passing copies down. backtrack(path + [x]) is easier to read and allocates O(n) per node, turning Θ(2ⁿ) into Θ(n · 2ⁿ) in allocations. Mutate and undo; it is why the template has an un-choose step.
• Test with the brute force. Generate small random inputs, run both the pruned and unpruned versions, and compare results. Pruning bugs produce missing solutions, which no amount of eyeballing will reveal.

References

• roadmap.sh — Data Structures & Algorithms
• Backtracking — Wikipedia
• Eight queens puzzle — Wikipedia
• Sudoku solving algorithms — Wikipedia
• Constraint satisfaction problem — Wikipedia
• Constraint propagation — Wikipedia
• AC-3 algorithm — Wikipedia
• Branch and bound — Wikipedia
• Iterative deepening depth-first search — Wikipedia
• Knuth’s Dancing Links (DLX) — arXiv
• Peter Norvig — Solving Every Sudoku Puzzle
• CLRS — Introduction to Algorithms
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• Python Documentation — itertools
• cp-algorithms — Algorithms index