Backtracking: Pruned Depth-First Search

From building whole candidates to building them one choice at a time

The previous guides left us with an uncomfortable bill. Generate-and-test is correct and dead simple, but it manufactures every candidate in full before checking it, and the search space it must walk is enormous — 2^n subsets, n! permutations. The waste is not just the size; it is the timing. To place eight queens, generate-and-test will happily build a complete board with queens 1 and 2 already attacking each other, then go on to fill in queens 3 through 8 in every possible way before finally testing and rejecting all of them. Millions of full boards die for a clash that was already visible after the second move.

The fix is a change of stance. Instead of producing finished candidates and judging them, build a candidate incrementally — one decision at a time — and judge each partial candidate as it grows. A partial candidate is just a prefix of the choices: "queen 1 in column 3, queen 2 in column 6, and nothing decided yet for the rest." If even that prefix already violates a rule, no completion of it can ever be valid, so there is no point completing it. We throw the whole prefix away and try a different choice for the most recent position. That single idea — extend, check, retreat — is backtracking.

The state-space tree, and why DFS is the natural walk

Picture all the prefixes laid out as a tree. The root is the empty candidate, nothing decided. Each node is a partial candidate, and its children are the ways to make the very next decision: from "queen 1 placed," the children are the choices for queen 2's column. Leaves at the bottom are complete candidates. This is the state-space tree, and it makes the structure of the search vivid — a path from the root to a node is exactly the sequence of choices that built that partial candidate.

Now, how should we walk this tree? Depth-first. Plunge down one branch, committing to choices as deep as you can go; when you hit a dead end or a leaf, retreat to the most recent node that still has untried children and dive again. This is exactly backtracking as depth-first search over the state-space tree. The retreat is the "back" in backtracking: you undo the last choice and restore the partial candidate to what it was one level up — literally erasing the queen you just placed before trying the next column. Depth-first is the right discipline here because it keeps only one root-to-node path in memory at a time, so the working state is small: O(depth), not O(number of nodes).

solve(partial):
    if partial is complete: report it; return
    for each choice c that extends partial:
        if feasible(partial + c):      # the prune
            solve(partial + c)         # go deeper
        # else: skip c's whole subtree
    # falling off the loop = backtrack to caller

Pruning: where all the savings come from

The one line that turns a brute-force tree walk into something fast is the feasibility check. Before recursing into a child, ask: can this partial candidate still be completed into a valid one? If the answer is provably no, we never enter that child — and that single refusal deletes the entire subtree beneath it, every leaf it would ever have reached. This is feasibility pruning, and it is the whole game. A check that costs O(1) at a node near the top can erase millions of candidates at the bottom. The earlier the contradiction is detectable, the higher up the tree we cut, and the more we save.

Backtracking shines brightest on a constraint-satisfaction problem — a task defined by rules every solution must obey, like "no two queens share a row, column, or diagonal" or "adjacent regions get different colors" in graph coloring. Constraints are exactly what give you something to check on a partial candidate. The richer and earlier-acting the constraints, the more aggressively the tree gets pruned. A problem with almost no constraints gives the pruner nothing to bite on, and backtracking degrades back toward plain enumeration.

Two classic templates: N-queens and subset-sum

The N-queens problem is the textbook picture of backtracking. Decide one queen per row, top to bottom; the choice at each level is which column. After tentatively placing a queen, check it against the queens already placed above — same column? same diagonal? If it clashes, that column is infeasible and its whole subtree is skipped without ever touching the rows below. Only when a row's queen survives the check do we descend to the next row. Reaching past the last row means all n queens coexist peacefully: a solution. Crucially the conflict check looks only at the partial board so far, so a bad second-row choice is caught immediately, killing all the deeper arrangements generate-and-test would have wastefully built.

Subset-sum shows a second, equally common shape. Given numbers and a target T, is there a subset summing to T? Decide the numbers one by one; at each level the two children are "include this number" or "exclude it" — a binary tree of depth n with 2^n leaves. Backtracking on subset-sum prunes with two cheap bounds carried along the path: if the running sum already exceeds T (and the numbers are non-negative), no further inclusion can fix it, so stop; and if the running sum plus the sum of all remaining numbers still falls short of T, no future choice can reach the target, so stop. Each bound lops off a subtree. Sorting the numbers first makes these bounds bite sooner — a tiny preprocessing step that sharpens every prune below.

Notice the shared skeleton under both. There is an ordering of decisions (rows; numbers), a small set of choices per decision (columns; in/out), a cheap test on the partial candidate, and an undo on the way back up. Fill those four slots and you have a backtracker for almost anything — permutations, combinations, puzzle solvers. The art is never the recursion; it is finding feasibility checks that detect doom as early and as cheaply as possible.

Beyond feasibility: bounding, and what comes next

So far the pruner answers a yes/no question: can this prefix still be legal? That is perfect for finding any solution or all solutions. But many tasks want the best solution, and there a second, sharper kind of pruning becomes possible. Suppose we have already found some valid candidate of cost 50. Now we are exploring a partial candidate, and we can compute that even in the most optimistic case its eventual cost cannot drop below 60. Then this whole branch is worthless — it cannot beat 50 — and we prune it even though it breaks no constraint at all. Pruning by an optimistic estimate against the best-so-far is the leap from backtracking to branch and bound, the subject of the next guide.

1. Order the decisions and, at the current partial candidate, list the choices for the next one.
2. For each choice, extend the candidate and run the feasibility check on the new prefix.
3. If feasible, recurse deeper; if not, skip that choice's entire subtree.
4. On returning, undo the choice (restore the previous state) and move to the next choice; a complete candidate that survives is a solution.

One more honest caveat before moving on. The order in which you try choices and the order in which you fix decisions are not cosmetic — they can change the running time by orders of magnitude, because they decide how soon contradictions surface and how early branches die. "Most-constrained variable first" and "least-constraining value first" are well-known heuristics, but they are heuristics: rules of thumb that usually help, not guarantees. The asymptotic worst case stays exponential regardless. Backtracking buys you a tree pruned of provable dead ends; it does not buy you a polynomial-time algorithm for a problem that has none.