Backtracking

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

# 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.

# 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.

# 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.

# 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.