Foundations — Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets

Before you can read the parent note fluently, you need to own every symbol it throws at you. Below, each idea is built from nothing, tied to a picture, and justified by "why does the topic need this?". They are ordered so each one leans only on the ones above it.

1. What is a "state"? (a partial answer)

Picture a chessboard where you have placed queens in the top 2 rows and the bottom 6 rows are still empty. That half-filled board is a state. Picture a shopping basket that currently holds [apple] while you decide whether to add banana — that basket is a state.

Why the topic needs it: backtracking never checks a whole finished answer first. It grows the state step by step, so we need a name for "the thing being grown."

2. The search tree — where every choice lives

The parent says "the search space is a tree." Here is what that word means with zero jargon.

Look at the figure. The single node at the very top is the empty basket. Each downward blue edge is a decision. As you walk down, the basket fills; the green leaves at the bottom are the finished subsets. Backtracking is nothing but walking this tree.

Why the topic needs it: once you see the problem as a tree, "try all options" becomes "visit all nodes," and "prune" becomes "don't bother going down a dead branch."

3. DFS — the walking order

The parent calls backtracking "DFS over a tree"]. DFS is a way of visiting a tree.

The yellow arrows in the figure number the visiting order: plunge down the leftmost path to a leaf, then climb back up just enough to take the next unexplored branch. This "plunge, hit bottom, climb back one fork" rhythm is exactly how you'd explore a maze by hand.

Why DFS and not the other option? The alternative, breadth-first (visit all level-1 nodes, then all level-2…), would force us to hold thousands of half-built states in memory at once. DFS holds only one path from root to current node at a time — cheap memory, and it matches "build one candidate, finish it, then try the next."

See Depth-First-Search for the full traversal treatment.

4. Recursion & the call stack — how "climb back up" actually happens

You never write "climb back up" as code. Recursion does it for free.

The stack of boxes in the figure grows downward as you recurse deeper, and shrinks (pops) as calls finish — mirroring the depth of the DFS walk exactly.

Why the topic needs it: the parent's whole template is backtrack(state) calling itself. Without understanding that a return = pop back to the parent node, the "un-choose" step (next) makes no sense.

Deep dive: Recursion-and-the-call-stack.

5. Choose → Explore → Un-choose (and why un-choose exists)

This is the heart. Three plain words.

Why the topic needs it: this single line is what separates backtracking from plain recursion. Forgetting it is mistake #1 on the parent page — sibling branches inherit leftover choices and produce garbage.

6. Pruning & validity — killing dead branches early

Picture the tree again, but with a whole sub-triangle greyed out and scissored off: you never generate any of the states inside it.

Why the topic needs it — the entire point: for 8 queens there are $\left(\genfrac{}{}{0ex}{}{64}{8}\right)\approx 4.4$ billion raw placements. Pruning at the top of a doomed branch skips all its descendants at once. Pruning late (only at the leaf) throws that saving away — that's mistake #3 on the parent page, "pruning too late."

This is the idea developed in Branch-and-Bound and Constraint-Satisfaction-Problems.

7. The notation the parent uses on specific problems

Now the smaller symbols, each earned.

The diagonal keys (the trickiest symbols on the parent page)

Now, why do r-c and r+c identify diagonals? A picture explains it instantly.

Look at the ↘ (down-right) diagonal in blue: stepping to the next cell adds 1 to r and 1 to c, so r-c stays constant — every blue cell shares the same r-c value. On the ↗ (up-right, i.e. anti-) diagonal in yellow, stepping adds 1 to r and subtracts 1 from c, so r+c stays constant.

8. Big-O of the walk (just enough to read the parent)

See Time-Complexity-of-Recursive-Algorithms. (Distinct from Dynamic-Programming, which reuses overlapping sub-answers — backtracking's branches are usually distinct, so there's nothing to memoize.)

How the foundations feed the topic

Return to the parent: parent topic.

Equipment checklist

Cover the right side and answer aloud. If any fails, re-read that section above.