Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets: Visual walkthrough

We use a tiny board, $N = 4$ (four queens on a $4 \times 4$ grid), because it is small enough to draw every branch yet big enough to fail, backtrack, and succeed. Everything here scales straight to the $8 \times 8$ or Sudoku case.

Prerequisite ideas we lean on (build them if you're shaky): Recursion-and-the-call-stack, Depth-First-Search, Constraint-Satisfaction-Problems.

Step 0 — The vocabulary, drawn before it is used

Before a single queen moves, let us name the picture so no symbol is a stranger.

Our whole strategy rests on one simplification from the parent note:

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

Look at the figure: the four rows are stacked; a queen must land somewhere on each row's four columns. Our job is to pick one blue square per row so that no two picked squares attack.

Step 1 — The three things that make squares "attack"

WHAT. Given a queen already placed at some square, which other squares are forbidden for the next queen?

WHY. If we can test "is square (r,c) safe?" in one glance, we can prune a bad choice before recursing — that early pruning is the entire speed advantage over brute force.

PICTURE. Three coloured rays leave a placed queen:

The vertical yellow ray = same column. Square (r,c) clashes if some earlier queen shares column c.
The pink ↘ ray = the "down-right" diagonal. Notice: stepping one square down-right adds $1$ to r and $1$ to c, so the difference $r - c$ never changes along that ray.
The blue ↗ ray = the "down-left" (anti-)diagonal. Stepping down-left adds $1$ to r and subtracts $1$ from c, so the sum $r + c$ never changes along it.

Why sets? Because "is this number already in the bag?" is an instant lookup — that's what makes the safety test $O (1)$ instead of scanning the whole board.

Step 2 — Row 0: the first free choice

WHAT. We start backtrack(r=0). All three bags (cols, diag, anti) are empty, so every square in row 0 is safe. We try columns left-to-right and take the first, c=0.

WHY. With nothing placed yet there is no conflict possible; the for c in range(n) loop simply hands us c=0 first. We choose it: add $c = 0$ to cols, add $r - c = 0$ to diag, add $r + c = 0$ to anti.

PICTURE. The queen lands top-left; its three rays now shade the squares those numbers forbid for the future.

$cols = {0}, diag = {0}, anti = {0}$

Every shaded square below is now off-limits. Notice how much of the board one queen already kills — that is pruning working for us.

Step 3 — Row 1: the first pruning (and a forced hop)

WHAT. Recurse into backtrack(r=1). Test columns 0,1,2,3 in order.

WHY / PICTURE. Walk the test for each column using the shaded rays from Step 2:

c=0: $c = 0 \in cols$ → blocked (same column as row-0 queen).
c=1: $r - c = 1 - 1 = 0 \in diag$ → blocked (same ↘ diagonal).
c=2: $c = 2$ ? not in cols. $r - c = - 1$ ? not in diag. $r + c = 3$ ? not in anti. → SAFE. Choose it.

So row 1 skips two doomed squares and lands at (1,2). We update the bags:

$cols = {0, 2}, diag = {0, - 1}, anti = {0, 3}$

Each new entry is annotated: $c = 2$ (the column), $r - c = - 1$ (the ↘ line), $r + c = 3$ (the ↗ line).

Step 4 — Row 2: a dead end (all four columns blocked)

WHAT. Recurse to backtrack(r=2). Now every column fails — this row has no legal move.

WHY. This is the crucial moment the parent note calls "hitting a wall in the maze." Check all four:

c=0: $c = 0 \in cols$ → blocked.
c=1: $r + c = 2 + 1 = 3 \in anti$ → blocked (↗ diagonal of the (1,2) queen).
c=2: $c = 2 \in cols$ → blocked.
c=3: $r - c = 2 - 3 = - 1 \in diag$ → blocked (↘ diagonal of the (1,2) queen).

The for c loop finishes with no queen placed. The function simply returns. No solution recorded. Row 2 is a dead branch given the choices above it.

Step 5 — The backtrack: un-choose row 1, slide the queen over

WHAT. Back in row 1's call, we execute the undo for c=2: $cols.remove (2), diag.remove (- 1), anti.remove (3)$ then the for loop advances to the next column, c=3.

WHY. This is the heart of backtracking. We restore the shared state so the board looks exactly as it did before we tried (1,2). Only then is it honest to try a sibling square. Skip this undo and row 1's next attempt inherits phantom forbidden squares.

PICTURE. The queen is lifted from (1,2), the pink/blue/yellow rays it cast vanish, and it slides to (1,3).

Test c=3 in row 1: $c = 3$ ? not in cols ${0}$ . $r - c = 1 - 3 = - 2$ ? not in diag. $r + c = 4$ ? not in anti. → SAFE. Choose (1,3):

$cols = {0, 3}, diag = {0, - 2}, anti = {0, 4}$

Step 6 — Row 2 again, then row 3: reaching a solution

WHAT. With row 1 now at column 3, recurse to row 2 afresh.

WHY / PICTURE. New parent choices ⇒ new shaded squares ⇒ a legal move reappears.

Row 2 (cols={0,3}, diag={0,-2}, anti={0,4}):

c=0: in cols → blocked.
c=1: $c = 1$ ? no. $r - c = 1$ ? no. $r + c = 3$ ? no. → SAFE. Choose (2,1).

Update: $cols = {0, 3, 1}, diag = {0, - 2, 1}, anti = {0, 4, 3}$ .

Row 3 (backtrack(r=3)):

c=0,1: both in cols → blocked.
c=2: $c = 2$ ? no. $r - c = 3 - 2 = 1 \in diag$ → blocked (↘ line of (2,1)).
c=3: in cols → blocked.

Row 3 dead-ends! Backtrack again: undo (2,1), but row 2 has no more columns, so undo (1,3) too. Row 1 also exhausts its columns → undo (0,0). The search now tries row 0, c=1, and this branch does succeed. The mechanics are identical to Steps 2–6, so we jump to that winning board:

$Solution: (0, 1), (1, 3), (2, 0), (3, 2)$

Verify it has no repeats among cols, r-c, r+c and you have a valid 4-Queens board — the algorithm found it purely by choose/explore/un-choose.

Step 7 — The degenerate cases you must have seen

WHAT / WHY. A walkthrough is only complete if it survives the weird inputs. Three of them:

$N = 1$ : one square, one queen, zero conflicts. Row 0 chooses c=0, r==n immediately → 1 solution. The tree is a single edge.
$N = 2$ and $N = 3$ : zero solutions. Trace $N = 2$ : row 0 picks c=0; row 1 finds c=0 (column) and c=1 ( $r - c = 0$ ) both blocked → dead. Try row 0 c=1; row 1 blocked again → dead. The recursion explores the whole tiny tree and records nothing. Backtracking proves impossibility by exhausting branches — it never crashes or loops.
The empty bags at the start (Step 2): when no queen is placed, the safety test is False or False or False, so every square is safe. The degenerate "nothing forbidden yet" case is handled by the same set-membership code — no special case needed.

Recall Why exhaustion is not brute force

Even for the "no solution" $N = 2$ case we didn't enumerate all $(2 4) = 6$ raw placements. We pruned each branch the moment row 1 failed, so the doomed configurations were never fully built. Pruning still pays even when the answer is "impossible."

The one-picture summary

This single figure stacks the whole story: the DFS tree of column choices for $N = 4$ . Green edges are chosen-and-alive, dashed red edges are pruned squares that never became nodes, and the ✗ marks are dead ends where we backtracked. The one path reaching the bottom row is the recorded solution. Read top-to-bottom to descend (choose → explore); read a red ✗ upward to backtrack (un-choose).

Recall Feynman retelling — the whole walkthrough in plain words

We fill the chessboard one row from the top down, because two queens on the same row would always fight — so each row gets exactly one queen and our only question per row is "which column?" For each row we go column by column. Before placing a queen we peek along three lines: its column, its down-right diagonal (all squares where row-minus-column is the same number), and its down-left diagonal (row-plus-column the same). If any of those numbers is already claimed, that square is under attack, so we skip it. When we find a safe square we drop the queen, remember its three numbers, and move to the next row down. If a row runs out of safe columns, we're stuck — so we walk back up to the previous queen, lift it, erase its three numbers, and slide it to its next column. That lift-and-erase is the single move that makes this work; without it the leftover numbers would haunt every later attempt. Keep sliding and dropping and lifting until either the bottom row gets a queen (a full solution — save a copy) or the top row runs out of columns (we've tried everything). For a one-square board it's instantly done; for two- and three-square boards nothing ever fits and the search politely reports "no solutions" after exhausting the tiny tree.

See also: Branch-and-Bound (pruning with a cost bound), Time-Complexity-of-Recursive-Algorithms (why the pruned tree beats $N^{N}$ ), and the parent topic note.