Backtracking — state-space tree, pruning: Exercises

Intuition How to use this page

These 12 problems climb a ladder: Recognition → Application → Analysis → Synthesis → Mastery. Each is stated cleanly, then hides its full worked solution inside a collapsible [!recall]- callout — so you can try first, then reveal. This is your self-test for Backtracking. Everything here reuses only the vocabulary the parent note built: state-space tree, candidate, promising node, pruning, backtrack (undo).

Before we start, one refresher in plain words so no term is unearned:

A decision = one choice you make to grow a partial solution (place a queen, include an item).
The state-space tree = every possible sequence of those decisions, drawn as branches.
Pruning = cutting a branch the instant the partial solution already breaks a rule, because everything below it is doomed too.
Backtrack (undo) = walk one step back up the tree and try the next sibling choice.

Figure — Backtracking — state-space tree, pruning

The picture above is the mental model for the whole page: a tree of decisions, with a red scissor where a rule is violated (prune) and a dashed arrow walking back up (backtrack).

Level 1 — Recognition

Exercise 1.1 — Spot the pruning line

Here is a backtracking skeleton. Which single line performs the pruning, and what would happen if you deleted it?

def backtrack(state):
    if is_complete(state):
        record(state)
        return
    for choice in candidates(state):
        if is_valid(state, choice):   # (A)
            state.add(choice)         # (B)
            backtrack(state)          # (C)
            state.remove(choice)      # (D)

Recall Solution

Line (A) — if is_valid(state, choice) — is the prune. It refuses to enter a branch whose partial solution already violates a constraint.

WHAT deleting it does: without (A), every candidate is expanded, so you generate the entire state-space tree, up to $b^{d}$ nodes ( $b$ = choices per step, $d$ = depth). You would still get correct answers (invalid ones get filtered elsewhere or never recorded), but you would pay full brute-force cost. Pruning is exactly the difference between "smart" and "blind" search.

(Line (B) makes the move, (C) explores, (D) is the undo/backtrack.)

Exercise 1.2 — Tree or not a tree?

True or false: In a state-space tree, two different nodes can share the same child.

Recall Solution

False. A state-space tree has exactly one path from the root to any node — each node has a single parent (the partial solution you had before the last decision). If two parents shared a child it would be a graph (a DAG), which is what Dynamic-Programming exploits via memoization. Backtracking treats the search space as a pure tree of decision sequences.

Level 2 — Application

Exercise 2.1 — Count leaves of a full binary decision tree

You solve subset-sum on [3, 1, 4] by deciding include/exclude each element, with no pruning at all. How many leaves does the state-space tree have, and how many internal nodes?

Recall Solution

Each of the $n = 3$ elements is a binary decision, so branching factor $b = 2$ , depth $d = 3$ .

Leaves = $b^{d} = 2^{3} = 8$ . (Every complete include/exclude assignment.)
Total nodes in a full binary tree of depth 3 = $2^{0} + 2^{1} + 2^{2} + 2^{3} = 1 + 2 + 4 + 8 = 15$ .
Internal nodes = total $-$ leaves = $15 - 8 = 7$ .

This is the unpruned cost — pruning removes some of these but never adds any.

Exercise 2.2 — Trace the subset-sum prune

Find all subsets of [2, 3, 5] summing to 5, deciding include/exclude left-to-right, and prune whenever running_sum > 5. List which branches get pruned.

Recall Solution

Target $= 5$ . Walk the tree (I = include, E = exclude):

I 2 (sum 2)
- I 3 (sum 5) — already at target; still process 5:
  - I 5 → sum 10 > 5 → PRUNED
  - E 5 → sum 5 ✓ → record {2, 3}
- E 3 (sum 2)
  - I 5 → sum 7 > 5 → PRUNED
  - E 5 → sum 2 ✗ (not 5), no record
E 2 (sum 0)
- I 3 (sum 3)
  - I 5 → sum 8 > 5 → PRUNED
  - E 5 → sum 3 ✗
- E 3 (sum 0)
  - I 5 → sum 5 ✓ → record {5}
  - E 5 → sum 0 ✗

Solutions: {2,3} and {5} — exactly 2 subsets. Pruned branches: 3 (the three sum > 5 cuts). Each cut kills the leaf below it before it is generated.

Level 3 — Analysis

Exercise 3.1 — Which validity test prunes earlier?

For N-Queens you can check safety two ways:

(A) place all $n$ queens, then verify the whole board.
(B) when placing row $r$ , check against rows $0 \dots r - 1$ immediately.

At what tree depth does each first detect the conflict [0, 2, 2, ...] (row 0 col 0, row 1 col 2, row 2 col 2 — a column clash between rows 1 and 2)? How many leaves does each approach waste?

Recall Solution

The clash is column 2 repeated at rows 1 and 2 — detectable the moment row 2 is placed.

(B) early check: fires at depth 2 (row index 2), the exact node where col 2 collides with the row-1 queen. It prunes the entire subtree below [0, 2, 2]. For $n = 4$ that subtree has $b^{d - depth} = 4^{4 - 3} = 4^{1} = 4$ leaves saved (rows 3 never explored under this dead node — here 4 candidate placements for row 3).
(A) leaf check: only detects at a leaf (depth $n$ ), after committing all $n$ queens. Every one of those doomed leaves under [0,2,2,*] gets fully generated first.

Conclusion: (B) prunes at the highest node where the constraint is already broken; (A) wastes the whole subtree. Same answers, wildly different work — this is the parent note's "test as early as detectable" principle.

Exercise 3.2 — Does pruning change the Big-O?

An adversary hands you an input on which no partial solution is ever infeasible until the very last decision. What is the time complexity, and what does this say about pruning's effect on worst-case Time-Complexity?

Recall Solution

If nothing prunes until the last decision, the search visits the full tree: up to $b^{d}$ nodes → $O (b^{d})$ , identical to blind brute force.

Therefore pruning does NOT improve the worst-case asymptotic bound. It slashes the average/typical runtime (real inputs prune tons of branches), but Big-O measures the adversarial worst case, which pruning cannot touch. This is why we call backtracking "brute force that gives up early" — the early is a constant-and-average-case win, not an asymptotic one.

Level 4 — Synthesis

Exercise 4.1 — Permutations without repeats

Write the is_valid and candidates for generating all permutations of [1, 2, 3], and count how many nodes the pruned tree has versus the unpruned "pick any of 3 at each of 3 slots" tree.

Recall Solution

State = the permutation built so far, plus a used[] flag per element.

candidates(state) = all elements x.
is_valid(state, x) = not used[x] — never reuse an element already placed.

Unpruned (pick any of 3 each slot): $b = 3$ , $d = 3$ → $3^{3} = 27$ leaves. Pruned (respecting used): first slot 3 choices, second 2, third 1 → $3 \times 2 \times 1 = 3! = 6$ leaves.

Node counts for the pruned tree (a tree where level $k$ has $\frac{3 !}{( 3 - k )!}$ nodes):

depth 0: 1
depth 1: 3
depth 2: $3 \times 2 = 6$
depth 3: $3 \times 2 \times 1 = 6$
Total = $1 + 3 + 6 + 6 = 16$ nodes.

The used[] flag is the pruning that turns 27 blind leaves into just 6 valid permutations.

Exercise 4.2 — Graph 3-coloring skeleton

You must color a triangle graph (3 mutually-connected vertices $V_{0}, V_{1}, V_{2}$ ) with 3 colors so no edge joins same-colored vertices. Decide one vertex's color per level. How many complete valid colorings exist, and how many leaves does pruning save versus $3^{3}$ ?

Recall Solution

is_valid(v, color) = no already-colored neighbor of v has color.

Because all three vertices are mutually adjacent, they must all differ → this is counting ways to assign 3 distinct colors to 3 vertices:

$V_{0}$ : 3 choices.
$V_{1}$ : must differ from $V_{0}$ → 2 choices.
$V_{2}$ : must differ from $V_{0}$ and $V_{1}$ → 1 choice.

Valid colorings = $3 \times 2 \times 1 = 6$ . Unpruned leaves $= 3^{3} = 27$ . Pruning saves $27 - 6 = 21$ dead leaves.

Level 5 — Mastery

Exercise 5.1 — N-Queens exact solution counts

Using the one-queen-per-row model, how many distinct solutions exist for $n = 4$ , $n = 5$ , and $n = 6$ ? (These are the classic small counts.) State the validity test you rely on.

Recall Solution

Validity (parent note): placing queen at row $r$ , column $c$ , it is safe iff for every earlier row $i < r$ : $c \neq = col [i]$ (no shared column) and $∣ r - i ∣ \neq = ∣ c - col [i] ∣$ (no shared diagonal).

Running backtracking with this prune, the number of full solutions is:

$n = 4$ : 2 solutions — namely [1,3,0,2] and [2,0,3,1].
$n = 5$ : 10 solutions.
$n = 6$ : 4 solutions.

These match the known N-Queens sequence $1, 0, 0, 2, 10, 4, 40, 92, \dots$ for $n = 1, 2, 3, 4, 5, 6, 7, 8$ . The dramatic dip at $n = 6$ (only 4, fewer than $n = 5$ ) is a nice reminder that solution counts are not monotonic — pruning finds exactly the valid ones regardless.

Exercise 5.2 — Design a prune for a hardest-case Sudoku cell

In a Sudoku-Solver, you fill empty cells left-to-right, top-to-bottom, each with a digit 1–9. Naively, branching factor is 9. Describe a pruning/ordering strategy that makes the effective branching factor drop, and explain why it attacks the exponential base $b$ rather than the depth $d$ .

Recall Solution

Strategy — Minimum Remaining Values (MRV): instead of filling cells in fixed order, always expand the empty cell with the fewest legal candidates (fewest digits not already used in its row, column, or $3 \times 3$ box).

WHY it attacks $b$ , not $d$ : the depth $d$ is fixed — it equals the number of empty cells, and every solution must fill all of them, so you cannot shorten $d$ . But the branching factor $b$ is the number of choices you branch on at each node. Cost scales like $b^{d}$ ; because $d$ is locked, the only lever is shrinking $b$ . MRV picks the most-constrained cell (often with $b = 1$ , a forced move — no branching at all!), driving the effective base far below 9. A single forced cell collapses that whole level from a fan-out into a straight line.

Combined with the standard row/column/box is_valid prune, MRV is why real solvers finish instantly despite Sudoku's exponential worst case.

Recall One-line summary of the whole ladder

L1 recognize the prune + undo lines · L2 apply the include/exclude and sum-bound prune · L3 analyze early-vs-late checking and why Big-O stays $O (b^{d})$ · L4 synthesize used[] and neighbor-color prunes · L5 master solution-counting and branching-factor-reducing heuristics.

Connections

Parent: Backtracking — this page drills its exercises.
Recursion — the machinery every solution here runs on.
Depth-First-Search — the traversal order of every state-space tree above.
N-Queens, Sudoku-Solver — the L3/L5 case studies.
Permutations-and-Combinations — L4.1's counting.
Time-Complexity — the $O (b^{d})$ analysis in L3.2.
Branch-and-Bound, Dynamic-Programming — when to graduate beyond plain backtracking.