Skip to main content

Backtracking Is Pruned Enumeration

What This Concept Is​

Backtracking builds a solution one choice at a time, represented as a path down a search tree. At each node:

  1. Extend. Add one more choice to the partial solution.
  2. Check feasibility against problem constraints.
  3. Prune and back up if the partial is infeasible or provably cannot reach a solution.
  4. Record complete valid solutions.
  5. Recurse into children otherwise, and undo the last choice on return.

The skeleton is systematic enumeration (concept 8). The pruning is what makes it tractable on problems where the naive candidate space is $n!$ or $2^n$. A well-pruned backtracking routine can visit only a tiny fraction of the tree; a poorly-pruned one degrades to brute force.

Branch-and-bound extends backtracking for optimization problems with a running best and a per-node lower (or upper) bound: prune any branch whose best possible completion cannot beat the current best.

Why It Matters Here​

Backtracking handles combinatorial problems with constraints: $N$-queens, sudoku, subset sum (decision), graph coloring, constraint satisfaction, Hamiltonian path, crossword filling, permutation enumeration with restrictions, and SAT-like problems. When there is no known polynomial algorithm (often because the problem is NP-hard), well-pruned backtracking is the realistic alternative, and it blends naturally with branch-and-bound, beam search, and heuristic methods like constraint propagation and conflict-driven learning (modern SAT solvers).

In practical engineering, backtracking is the engine of parsers (recursive descent with backtracking on ambiguity), regex engines (classic backtracking is why catastrophic regexes exist), and planners. Recognizing the pattern - and its complexity ceiling - is a transferable skill.

Concrete Example​

Example 1 ($N$-queens). Place $N$ queens on an $N \times N$ board so no two attack each other.

def solve(n):
    solutions = []
    cols = [-1] * n

    def attacks(r, c):
        for r2 in range(r):
            c2 = cols[r2]
            if c2 == c or abs(c2 - c) == abs(r2 - r):
                return True
        return False

    def place(r):
        if r == n:
            solutions.append(cols.copy())
            return
        for c in range(n):
            if not attacks(r, c):
                cols[r] = c
                place(r + 1)
                cols[r] = -1

    place(0)
    return solutions
  • Partial solution: a prefix of column choices for rows $0, \ldots, r-1$.
  • Extend: try each column in row $r$.
  • Prune: if the new queen attacks any earlier queen, skip that branch entirely.
  • Complete: all $n$ rows placed.

The unpruned search space has $n^n$ partials (in the general "place $n$ queens anywhere" model). Even modest column-attack pruning collapses it dramatically; for $n = 12$, backtracking runs in well under a second.

Further prunes that tighten the tree:

  • Track attacked columns and diagonals in sets -> $O(1)$ feasibility check per extension instead of $O(r)$.
  • Row-level symmetry: any solution's mirror is also a solution; compute only half the root-level choices and double.
  • Column-level ordering: process the row with the fewest legal columns first (a constraint-propagation heuristic).

Example 2 (subset sum via backtracking + bound). Target sum $T$; items $a_1, \ldots, a_n$. At each step, decide include or exclude. Prune branches where:

  • current_sum > T (overshoot).
  • current_sum + sum_of_remaining < T (undershoot).

Without pruning: $2^n$. With both bounds on near-target inputs: often polynomial in practice even when $n = 40$.

Common Confusion / Misconceptions​

  • "Backtracking is just try everything." Without feasibility pruning it is brute force (concept 8). The entire advantage comes from detecting that a partial solution is already doomed and skipping its subtree. Pruning is the whole point.
  • "Losing the partial state." Backtracking modifies a shared state on the way down (the cols array here, or a bitmask of attacked squares) and must undo that modification on the way up. Miss the undo and branches contaminate each other. Common idiom: snapshot before recurse, restore after.
  • "Exponential means useless." A worst-case exponential algorithm with aggressive pruning can solve practical instances in milliseconds. Sudoku solvers, Scheduler CSPs, SAT solvers are all exponential-in-the-worst-case but extremely fast in practice.
  • "Backtracking cannot be memoized." It can - the result is DP with explicit state (concept 13). If you notice that two branches have identical remaining subproblems, cache the result on the state and you've upgraded backtracking to memoized recursion.
  • "Deeper pruning is always better." A pruning predicate that costs more to evaluate than it saves is a loss. Measure; do not assume.

How To Use It​

Design checklist:

  1. What is a partial solution? (prefix, partial assignment, path-so-far)
  2. What are the extensions? (next choice options, enumerated in some order)
  3. What is the feasibility test after each extension? (constraint propagation)
  4. What is a complete solution? (all variables assigned, all constraints satisfied)
  5. How do you record or emit solutions? (append, print, count)
  6. What is the undo? (reverse every mutation made during extend before returning)

Then strengthen in this order:

  • Feasibility pruning. Current partial is already infeasible - skip children.
  • Bound pruning. Best possible completion of this branch cannot beat known best - skip.
  • Symmetry breaking. Isomorphic branches (mirror, rotation, label permutation) - visit one.
  • Variable ordering. Assign the most-constrained variable next (fewer choices = earlier pruning).
  • Value ordering. Try the least-constraining value first (more future options preserved).

Measure tree size (calls to place) before and after each prune to confirm the prune is worth the evaluation cost.

Transfer / Where This Shows Up Later​

  • S1 M5 (problem solving) taught "search under constraints." Backtracking is the structured version.
  • S4 (systems) uses backtracking in register allocation (coloring interference graphs), type inference with constraint propagation, and parser generators.
  • S5 (OS / scheduling) solves feasibility of real-time schedule sets by constraint-propagation backtracking when no polynomial algorithm exists.
  • S6 (databases) solves query planning as a branch-and-bound search over join trees (CLRS-style cost pruning); constraint solvers in database consistency checks also backtrack.
  • S7 (architecture) uses backtracking for architectural trade-off exploration: enumerate configurations that satisfy constraints, prune those that violate the ADR's stated conditions.
  • S8 (distributed systems) uses backtracking to enumerate possible failure scenarios in chaos-engineering test generation and in model-checking protocols.

Concept 8 is the unpruned baseline; concept 18 tells you when backtracking is the right paradigm.

Common Confusion / Misconceptions (continued)​

  • "Backtracking is DFS." DFS is one traversal order. Backtracking typically uses DFS because it minimizes state (one path at a time), but iterative-deepening search and beam search are variations with different trade-offs between space and completeness.

Check Yourself​

  1. What is the difference between backtracking and brute-force enumeration?
  2. Why must state modifications made on the way down be reversed on the way up?
  3. For $N$-queens, what is a simple symmetry that lets you skip half the root-level choices?
  4. How would you detect that a branch cannot improve on the current best, in a branch-and-bound subset-sum solver?
  5. Why does memoizing a backtracker turn it into a DP algorithm? Give a problem where this is natural.

Mini Drill or Application​

Implement (pseudo)code with explicit extend / check / undo structure for each.

  1. Generating all permutations of $[1 \ldots n]$.
  2. Subset sum: find any subset of $A$ summing to $T$, with over/under-shoot pruning.
  3. Sudoku solver given a partial grid; use constraint propagation to prune (for each empty cell, track the candidate set).
  4. Hamiltonian path in a small graph (prune when current vertex has no unvisited neighbor consistent with reaching all remaining vertices).
  5. Graph coloring with $k$ colors: try colors in order, prune when no color is feasible.
  6. Implementation drill. Implement n_queens_count(n) returning the number of solutions. Derive approximate tree size for $n = 8, 10, 12$ by counting place calls. Compare with and without diagonal-attack bitmasks. Complexity: worst-case $O(n!)$ unpruned; typical $\ll n!$ after pruning. Stress-test against the known OEIS counts.

Read This Only If Stuck​