Foundations — Backtracking — state-space tree, pruning

This page assumes nothing. Before you can read the parent note (topic), you must own every word and symbol it throws at you. We build each one from a picture, in the order that lets each idea rest on the previous.

1. A "decision" and a "partial solution"

Before any tree or recursion, the atom is this: a decision.

Look at the first figure. On the left is an empty tray (partial solution = nothing chosen). Each arrow you follow adds one item to the tray. A complete solution is a full tray; a dead end is a tray you cannot legally add to.

Why the topic needs this: the whole method is "grow a partial solution decision by decision". If you cannot picture a half-built answer, nothing above makes sense.

2. The tree — root, node, edge, leaf, branch, subtree

Every sequence of decisions can be drawn as a branching diagram. Mathematicians call it a tree (drawn upside-down: root on top).

Why the topic needs this — the payoff sentence: a bad partial choice sits at some node, and every leaf in its subtree inherits that mistake. So if you can prove a node is hopeless, you delete its whole subtree in one stroke. That single fact is why backtracking is fast. Look at the red X in the figure: cutting one edge there erased four leaves at once.

3. Recursion — the tool that walks the tree

For us the base case is "the partial solution is complete → record it and return". Every non-base node says "for each valid child, call myself on that child". See Recursion for the deeper mechanics; here you only need: a self-call means 'go one node deeper', and returning means 'come back up'.

Why the topic needs this: the parent's generic template is a recursive function. Without recursion the "go deeper / come back" motion has no clean form.

4. DFS — the order recursion visits nodes

Recursion gives us a natural visiting order, and it has a name.

Follow the numbered arrows in the figure: 1 → 2 → 3 (hit a leaf) → back up → 4 (next sibling) → deeper again. This is exactly what recursion does automatically: the self-call dives, the return climbs. See Depth-First-Search.

Why the topic needs this: the parent says "explored in Depth-First order". Depth-first is the reason a partial solution is finished (or failed) before its siblings are even touched — which is when we get the chance to prune.

5. The feasibility test — is_valid and "promising"

Why the topic needs this: pruning is nothing but "run is_valid at each node and refuse to expand the failures". No feasibility test → no pruning → plain brute force.

6. Pruning and backtracking — the two named actions

7. The symbols in the parent's formula

The parent's boxed recursion uses compact notation. Here is every piece:

8. Branching factor $b$, depth $d$, and $b^d$

The parent's complexity uses $b$, $d$, and $b^d$. Build them from the tree picture.

Why $b^d$ leaves? Level 0 has 1 node. Each node makes $b$ children, so level 1 has $b$, level 2 has $b\cdot b=b^2$, … level $d$ has $b^d$. The little superscript $d$ means "$b$ multiplied by itself $d$ times".

Why the topic needs this: $b^d$ is the size of the un-pruned tree. It grows explosively (that superscript is why 4 queens has $4^4=256$ leaves). Pruning fights this growth. See Time-Complexity and, for the worst-case Big-O talk, Branch-and-Bound.

Prerequisite map

Read it top-down: the atom (decision) feeds both the tree and recursion; recursion + tree give DFS; the feasibility test plus DFS give pruning; pruning plus the undo give full backtracking; the tree's shape gives $b$, $d$, and the $b^d$ cost. All arrows converge on the topic.

Equipment checklist

Test yourself — reveal only after answering aloud.

Connections

• Recursion — the self-calling mechanism DFS rides on.
• Depth-First-Search — the exact visiting order.
• Time-Complexity — where $b^d$ and Big-O come from.
• Branch-and-Bound — pruning with numeric bounds, the next step up.
• N-Queens, Sudoku-Solver, Permutations-and-Combinations — first problems that use all of the above.
• Backtracking (parent topic)