--- title: Backtracking source: 'https://academia.sh/en/courses/advanced-algorithms/backtracking' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:24+00:00' license: 'CC BY-SA 4.0' --- # Backtracking Pruning is the one shortcut that preserves correctness, and what happens when its criterion breaks: on a seven-queens board, pruned search visits 552 nodes and unpruned search 960,800, but over-pruning, which also cuts the neighboring column, finishes in 82 nodes and loses every solution. Dynamic programming walked and stored the subproblem space in its **entirety**, and it could do this because the space fit into a table. In some problems, the space does not fit into a table: an eight-queens board has 16,777,216 placements, and only 92 of them are solutions. In such a space, the only path is to **prove that most of it contains no solution and cut it**. The approach is called **backtracking**: the solution is built piece by piece, and the moment the piece built so far violates a constraint, that branch is abandoned and the previous decision is returned to. The cutting operation is called **pruning**. Pruning holds a special place among the shortcuts seen in this course — like early exit in the first lesson, it **preserves** correctness, but only if its criterion is correct. This lesson counts that "only." - **DA38.** The measured problem: the **number** of placements of $n$ queens on an $n \times n$ board that do not threaten each other. - **DA39.** A **step** is a node in the search tree; leaves are counted as nodes too. - **DA40.** The **oracle is unpruned search**: it generates every placement and tests validity at the end. Because it cuts no branch, it cannot miss any solution. - **DA41.** The approach's **precondition**: the pruning criterion must cut only branches that are certainly unsolvable. - **DA42.** Three criteria are measured — **correct**, **over-pruning** (also cuts a branch that contains a solution), **under-pruning** (does not cut an unsolvable branch). - **DA43.** Here the **corpus is boards**: on a six-queens board, three squares are forbidden, over 40 boards. - **DA44.** A **diverging input** is a board where the oracle's and the approach's solution counts differ. - **DA45.** The 16,777,216 placements unpruned search would scan on an eight-queens board are **computed, not run**; the step budget from the first lesson requires this. - **DA46.** Every measurement is also run on a second corpus with seed **20260219**. ## The Partial Solution Tree Backtracking sees the solution as a sequence of decisions. Every decision produces a node, and every node's children are the options that follow that decision. This structure is called the **partial solution tree**, and its leaves are candidate complete solutions. Unpruned search walks this whole tree and tests validity only at the leaves. Pruned search tests **at every node**: if the partial solution already violates a constraint, every leaf beneath that node will violate it too, and the branch can be cut. The legitimacy of cutting rests exactly on this inference — **it must be proven that the subtree contains no solution.** When the proof weakens, an error is made in one of two directions. If the criterion cuts **too much**, branches containing solutions go with it and the answer comes out short. If it cuts **too little**, unsolvable branches keep being walked; this alone does not give a wrong answer, but if the test done at the leaf is also weak, invalid placements get counted as solutions. There is no way to tell the two forms of error apart from the output. A short list of placements and a long one both keep returning as a list; the only thing that can say which is correct is the number produced by the oracle that cuts no branches at all. ## The Space Pruning Cuts ```python # Backtracking measurement from the shared definition: the same search, pruned and unpruned. class Counter: def __init__(self): self.steps = 0 def add(self, n=1): self.steps += n def queens(n, prune=True): """The unpruned version tries every placement; the pruned version stops on conflict.""" s = Counter() solutions = [] def visit(row, placement): s.add() if row == n: solutions.append(tuple(placement)) return for column in range(n): if prune and any(column == y or abs(column - y) == row - i for i, y in enumerate(placement)): continue placement.append(column) visit(row + 1, placement) placement.pop() visit(0, []) if not prune: solutions = [c for c in solutions if all(c[i] != c[j] and abs(c[i] - c[j]) != j - i for i in range(n) for j in range(i + 1, n))] return {"nodes": s.steps, "solutions": len(solutions)} for n in (5, 6, 7): pruned, unpruned = queens(n, True), queens(n, False) print(f"n={n} pruned nodes {pruned['nodes']:5d} solutions {pruned['solutions']:3d}" f" | unpruned nodes {unpruned['nodes']:7d} solutions {unpruned['solutions']:3d}" f" | ratio {unpruned['nodes'] / pruned['nodes']:7.1f}") pruned8 = queens(8, True) print(f"n=8 pruned nodes {pruned8['nodes']:5d} solutions {pruned8['solutions']:3d}" f" | unpruned would scan {8 ** 8} placements (ratio {8 ** 8 / pruned8['nodes']:.1f})") ``` ``` n=5 pruned nodes 54 solutions 10 | unpruned nodes 3906 solutions 10 | ratio 72.3 n=6 pruned nodes 153 solutions 4 | unpruned nodes 55987 solutions 4 | ratio 365.9 n=7 pruned nodes 552 solutions 40 | unpruned nodes 960800 solutions 40 | ratio 1740.6 n=8 pruned nodes 2057 solutions 92 | unpruned would scan 16777216 placements (ratio 8156.2) ``` The solutions columns are the same across all three rows: 10, 4, 40. Pruning misses no solution, so the **diverging count is zero**. The nodes columns, however, show the gap: **552 versus 960,800 nodes** on a seven-queens board, a ratio of **1740.6**. On the eight-queens board, pruned search finishes in 2057 nodes; unpruned search would scan 16,777,216 placements, and the ratio would be **8156.2**. The ratio grows with $n$: 72.3, then 365.9, then 1740.6, then 8156.2 — roughly fivefold at every step. **Pruning's gain grows as scale grows.** But a second reading balances this: the pruned node count itself also climbs — 54, 153, 552, 2057 — roughly 3.7 times at every step. **Pruning cuts the exponential space but does not eliminate the exponent.** A board twice as large stays out of reach even with pruned search; pruning defers, it does not solve. ## Which Constraint the Cut Comes From The queens problem has two constraints — same column and same diagonal — and pruning was using both together. The constraints can also be applied separately; because each cuts only branches that are **certainly unsolvable**, all three preserve correctness. ```python # Continuing from the previous block: Counter comes from there. def partial_pruning(n, criterion): """criterion: none | column | diagonal | both. All variants fully validate at the leaf.""" s = Counter() solutions = 0 def visit(row, placement): nonlocal solutions s.add() if row == n: if all(placement[i] != placement[j] and abs(placement[i] - placement[j]) != j - i for i in range(n) for j in range(i + 1, n)): solutions += 1 return for column in range(n): if criterion in ("column", "both") and column in placement: continue if criterion in ("diagonal", "both") and any( abs(column - y) == row - i for i, y in enumerate(placement)): continue placement.append(column) visit(row + 1, placement) placement.pop() visit(0, []) return {"nodes": s.steps, "solutions": solutions} print("n=7 criterion nodes solutions") for criterion in ("none", "column", "diagonal", "both"): r = partial_pruning(7, criterion) print(f" {criterion:9s} {r['nodes']:7d} {r['solutions']:7d}") ``` ``` n=7 criterion nodes solutions none 960800 40 column 13700 40 diagonal 10736 40 both 552 40 ``` The solutions column is **40** in all four rows; all four are correct. The nodes column shows what pruning's power depends on. The column constraint alone brings 960,800 nodes down to 13,700 — 70.1 times. The diagonal constraint alone brings it down to 10,736 — 89.5 times. Both together give **552**, that is, 1740.6 times. Combined cutting gains far more than the sum of the two single cuts; because most of the branches one constraint leaves behind are cut by the other. The design rule that follows is measured: **the earlier a constraint can be proven, the more it cuts.** Testing constraints at the leaf is validation; testing them at the node is pruning; the difference between them is, in this problem, the gap between 960,800 and 552. ## When the Pruning Criterion Is Wrong The same search is run with three different criteria. Two of them break the precondition. ```python # Continuing from the previous block: Counter and queens come from there. def queens_mode(n, mode): """mode: correct | over (also cuts the neighboring column) | under (only the previous row)""" s = Counter() solutions = [] def conflict(column, row, placement): if mode == "under": i = row - 1 return i >= 0 and (column == placement[i] or abs(column - placement[i]) == 1) base = any(column == y or abs(column - y) == row - i for i, y in enumerate(placement)) if mode == "over": # "queens must not be in neighboring columns" return base or any(abs(column - y) == 1 for y in placement) return base def visit(row, placement): s.add() if row == n: solutions.append(tuple(placement)) return for column in range(n): if conflict(column, row, placement): continue placement.append(column) visit(row + 1, placement) placement.pop() visit(0, []) return {"nodes": s.steps, "solutions": len(solutions)} print(" n oracle solutions correct pruning over-pruning under-pruning") diverging = {"correct": 0, "over": 0, "under": 0} for n in (5, 6, 7): oracle = queens(n, False) row = f"{n:2d} {oracle['solutions']:15d}" for mode in ("correct", "over", "under"): r = queens_mode(n, mode) if r["solutions"] != oracle["solutions"]: diverging[mode] += 1 row += f" {r['solutions']:4d} ({r['nodes']:5d})" print(row) print("boards diverging from oracle (out of 3):", diverging) ``` ``` n oracle solutions correct pruning over-pruning under-pruning 5 10 10 ( 54) 0 ( 20) 184 ( 306) 6 4 4 ( 153) 0 ( 39) 2642 ( 3747) 7 40 40 ( 552) 0 ( 82) 45514 (59196) boards diverging from oracle (out of 3): {'correct': 0, 'over': 3, 'under': 3} ``` Three numbers side by side, and this time both are bad. **Correct pruning** gives the oracle's solution count on all three boards: 10, 4, 40. **Over-pruning** finds **zero solutions** on all three — the rule "queens must not sit in neighboring columns" looks reasonable, but because it cuts branches that are not certainly unsolvable, it leaves nothing behind. **Under-pruning** only looks at the previous row, so it cannot see diagonal conflicts in distant rows, and on the seven-queens board it counts **45,514** placements as solutions instead of 40. The nodes columns are a trap here. Over-pruning finishes in **82 nodes** on seven queens; 6.7 times faster than correct pruning's 552 nodes. If a measurement counts only nodes, over-pruning looks like the **best procedure**. Under-pruning, walking 59,196 nodes, is the slowest of all — so **being wrong is not always fast.** Wrongness has two forms, and node count gives away neither of them; the only thing that gives it away is the oracle's solution count. ## A Corpus of Forbidden Squares A single family of boards is not a corpus. The measurement moves to forty separate examples by adding three forbidden squares to a six-queens board, and it is run with two seeds. ```python # Continuing from the previous block: Counter and queens_mode come from there. def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value N = 6 FORBIDDEN_COUNT = 3 def board_corpus(seed, count=40): """Every board has 3 forbidden squares. Forbidden squares come from the seed.""" r = generator(seed) return [{"no": i + 1, "forbidden": {(r(N), r(N)) for _ in range(FORBIDDEN_COUNT)}} for i in range(count)] def forbidden_search(n, forbidden, mode, s): """mode: oracle (unpruned, validate at the end) | correct | over""" solutions = [] def valid(c): if any((i, c[i]) in forbidden for i in range(n)): return False return all(c[i] != c[j] and abs(c[i] - c[j]) != j - i for i in range(n) for j in range(i + 1, n)) def visit(row, placement): s.add() if row == n: if mode != "oracle" or valid(tuple(placement)): solutions.append(tuple(placement)) return for column in range(n): if mode != "oracle": if (row, column) in forbidden: continue if any(column == y or abs(column - y) == row - i for i, y in enumerate(placement)): continue if mode == "over" and any(abs(column - y) == 1 for y in placement): continue placement.append(column) visit(row + 1, placement) placement.pop() visit(0, []) return len(solutions) for label, seed in (("first corpus (20260218)", 20260218), ("second corpus (20260219)", 20260219)): boards = board_corpus(seed) oc, cc, ac = Counter(), Counter(), Counter() div_correct, div_over, lost = 0, 0, 0 for t in boards: h = forbidden_search(N, t["forbidden"], "oracle", oc) d = forbidden_search(N, t["forbidden"], "correct", cc) a = forbidden_search(N, t["forbidden"], "over", ac) div_correct += h != d div_over += h != a lost += h - a print(label) print(" oracle nodes", oc.steps, "| correct pruning nodes", cc.steps, "| ratio", round(oc.steps / cc.steps, 2)) print(" diverging inputs: correct pruning", div_correct, "/ 40 | over-pruning", div_over, "/ 40 | lost solutions", lost) ``` ``` first corpus (20260218) oracle nodes 2239480 | correct pruning nodes 4736 | ratio 472.86 diverging inputs: correct pruning 0 / 40 | over-pruning 40 / 40 | lost solutions 92 second corpus (20260219) oracle nodes 2239480 | correct pruning nodes 4452 | ratio 503.03 diverging inputs: correct pruning 0 / 40 | over-pruning 40 / 40 | lost solutions 90 ``` The oracle's node count is **exactly the same** in both corpora: 2,239,480. This is expected — unpruned search generates every placement without looking at the forbidden squares, so the node count is independent of the board. Correct pruning's node count varies between 4736 and 4452, because forbidden squares cut branches early; the ratio is 472.86 and 503.03. The diverging counts point the same way in both corpora: correct pruning **0/40**, over-pruning **40/40**. The lost solution count is 92 and 90; the two-solution difference between them comes from the placement of the forbidden squares and is below the threshold the measure considers meaningful. The reading does not change in either corpus: **correct pruning matches the oracle on all forty boards, over-pruning differs on all forty as well.** ## Summary - Backtracking cuts a branch when it has been proven that no solution exists beneath it in the partial solution tree; the legitimacy of the cut depends on that proof. - Correct pruning visits 552 nodes on a seven-queens board, unpruned search 960,800 (a ratio of 1740.6), and the solution counts stay the same: 10, 4, 40. - The ratio grows roughly fivefold with $n$ (72.3 · 365.9 · 1740.6 · 8156.2), but the pruned node count also grows 3.7 times: pruning does not eliminate the exponent, it defers it. - Over-pruning finishes in 82 nodes on seven queens and finds zero solutions; in a measurement that counts only nodes, it looks like the best procedure. - Under-pruning walks 59,196 nodes and counts 45,514 placements as solutions instead of 40; being wrong is not always fast. - On forty forbidden-square boards, correct pruning diverges on 0/40, over-pruning on 40/40; the second corpus gives the same result, with 90 lost solutions instead of 92. ## Next Step Every procedure so far has been deterministic: the same input always gave the same steps and the same answer. The final design approach loosens this guarantee and, in exchange, asks for something — sometimes for the step count, sometimes for the answer itself, to be random. The next lesson measures two kinds of randomization on the same corpus and answers a single question: does the number of inputs a random procedure is wrong on change when the seed changes.