Visual walkthrough — Backtracking — state-space tree, pruning

This is a picture-first companion to the parent topic. If a word feels heavy, look at the figure next to it — the geometry carries the idea.

Step 1 — A decision is a fork in a road

WHAT. Before any tree, there is just one choice. Suppose we are placing something and we have exactly two options: take it or skip it. That single choice is a fork — two roads leaving one point.

WHY start here. Backtracking is nothing but choices stacked on choices. If we do not understand one fork perfectly, a tree of thousands of forks is hopeless. So we earn the atom first.

PICTURE. Look at the figure: the single filled dot on the left is the current state — everything we have decided so far. Two arrows leave it. The label on each arrow is the decision we make. The two dots on the right are the new states we land in after deciding.

Step 2 — Stack the forks: the state-space tree appears

WHAT. Now make a second decision after the first, and a third after that. Each new fork sprouts from wherever the previous one left us. Drawing all of them at once gives the shape in the figure — a tree.

WHY a tree and not a list. Because a later choice depends on the path that reached it. "Skip, then take" lands somewhere different from "take, then take". A tree is exactly the picture of "every path of decisions".

PICTURE. Count the layers from top to bottom. Layer $0$ (the top dot) is the root — the empty state, no decisions yet. Each downward level = one more decision made. The very bottom row of dots are leaves — states where nothing is left to decide.

If every node has $b$ arrows leaving it (the branching factor) and the tree is $d$ levels deep, the number of leaves is:

$\underset{\text{choices per node}}{\underbrace{b}}\times b\times \cdots \times b=b^d$

• $b$ — how many decisions fork out of one node (here $b=2$: take / skip).
• $d$ — how deep we go, i.e. how many decisions a full solution needs.
• $b^d$ — total leaves, i.e. the brute-force count. This grows terrifyingly fast; that is the enemy.

Step 3 — Walk it depth-first (one finger, all the way down)

WHAT. We do not look at the whole tree at once. We explore it like a maze: go as deep as possible down one path, and only when we can go no deeper do we step back up and try the next arrow. That order is called depth-first.

WHY depth-first. Because we build a solution incrementally. Going deep = adding one more decision to the current partial solution. It also lets us reuse a single state object (see Step 6) instead of storing every node.

PICTURE. The numbered arrows in the figure show the exact order our "finger" visits nodes: down-down-down, hit bottom, back up one, try the sibling, and so on. This is precisely a depth-first search — but over a tree we are generating on the fly, not a tree stored in memory.

Step 4 — The isValid test: a gate at every arrow

WHAT. Before we walk down an arrow, we run a quick check called ==isValid== on the state that arrow would lead to. If the partial solution already breaks a rule, the gate is closed — we do not step through.

WHY here and not at the bottom. A broken partial solution can never become a valid full solution — adding more decisions cannot un-break a rule already violated. So checking at the leaf is pure waste: we would generate an entire subtree only to reject all of it.

PICTURE. In the figure, the red ✗ sits on an arrow. Notice everything below that arrow — the greyed-out subtree — is a set of states we would have visited but now never generate at all.

Step 5 — Pruning = deleting a subtree, and why it pays off exponentially

WHAT. Closing a gate high in the tree is called pruning. Because a closed gate removes not one node but the entire subtree hanging under it, one cheap test can erase thousands of dead-ends.

WHY it is exponential leverage. If we prune an arrow at depth $k$ (counting the root as depth $0$), the subtree we delete had depth $d-k$ left to grow. The leaves killed by that one cut number:

$\text{leaves removed}=b^{d-k}$

• $d-k$ — how many decision-levels remained below the cut.
• $b^{d-k}$ — leaves that hung under the pruned arrow, all gone from one test.
• Read the message: prune high (small $k$) → the exponent $d-k$ is large → a colossal cut.

PICTURE. Two cuts are shown. The high cut (near the root) removes a fat subtree; the low cut (near a leaf) removes almost nothing. This is why the parent note says "cutting the root of a bad subtree kills exponentially many dead-ends".

Step 6 — The make / explore / undo rhythm (why the drawing stays honest)

WHAT. We reuse one mutable state for the whole tree. Going down an arrow we add the decision; coming back up we remove it — exactly restoring the parent's state.

WHY the undo is mandatory. After exploring one child, we must try the sibling from the parent's exact state. If we forgot to remove our decision, the sibling would inherit a corrupted state — as if we drew an extra arrow that was never really there.

PICTURE. Follow the two coloured half-arrows on one edge: the down half is add(x) (make the move), the up half is remove(x) (undo). They must come in pairs, bracketing the recursion, like matching parentheses.

def backtrack(state):
    if is_complete(state):
        record(state); return
    for choice in candidates(state):
        if is_valid(state, choice):   # Step 4 gate
            state.add(choice)         # DOWN  = make
            backtrack(state)          # deeper
            state.remove(choice)      # UP    = undo  <-- never skip

This mutate-and-restore discipline is what separates true backtracking from plain Recursion or a stored-tree DFS.

Step 7 — Edge & degenerate cases (the ones people forget)

WHAT. A derivation is only trustworthy if it survives the extremes. Four corner cases, each drawn:

1. Root is already complete ($d=0$). No decisions needed — the empty state is the answer. The tree is a single dot; we record and stop.
2. Every gate closes at depth 1. No valid solution exists. We prune all top arrows and return the empty set — correctly reporting "impossible".
3. No gate ever closes (adversarial input). Nothing is prunable; we visit all $b^d$ leaves. Pruning gave us nothing here.
4. Branching factor shrinks per level. In permutations, choices left drop $n,n-1,\dots ,1$, so the count is $n!$, not $b^d$ — the tree narrows as we descend.

WHY case 3 matters most. It proves the honest complexity claim:

PICTURE. Four mini-trees side by side: the single-dot root, the all-pruned-at-top tree, the fully-grown unprunable tree, and the narrowing permutation tree.

The one-picture summary

WHAT. Everything at once: a full state-space tree, a depth-first finger-path numbered, two gates shut with ✗, the two subtrees they delete shaded out, and one edge showing the down-add / up-remove pair. If you understand this single frame, you understand the page.

Connections

• Parent topic — the full method and code.
• Depth-First-Search — the exploration order our finger follows.
• Recursion — the mechanism that stacks and unstacks decisions.
• N-Queens, Sudoku-Solver, Permutations-and-Combinations — trees this exact picture describes.
• Branch-and-Bound — pruning with a numeric bound instead of a boolean gate.
• Dynamic-Programming — a different escape from $b^d$: reuse overlapping subproblems.
• Time-Complexity — why $O(b^d)$ survives pruning in the worst case.