A placement service must seat eight replicas on an 8×8 rack grid: one per row, one per column, and no two on the same power diagonal. The intern generates every permutation of columns, then checks diagonals. n = 8 is 40,320 boards. n = 12 is 479 million. The next engineer still finishes the permutation. The prefix with two replicas already on a diagonal was illegal at row 2.
The same job shows up as a feature-flag set with pairwise conflicts, or a Sudoku-shaped config: the next digit is legal only given the cells you already filled. Still a path. Still a reason to stop early.
Backtracking places a choice, recurses, and undoes — the next pick is legal only given the path. You do not generate every complete assignment and filter. You prune when the partial board cannot succeed.
This post is that search. Families, greedy-versus-DP vocabulary, and the catalog live on the Algorithms Roadmap. DFS walks a graph that already exists. This procedure builds a partial assignment and tears the last choice off when the branch dies. 0/1 Knapsack is the other fork: overlapping (item, capacity) cells. Do not fill that table here.
The shape: choose, recurse, undo
At depth k the state is a prefix: the columns already taken, the diagonals already hot, the flags already on. A candidate for slot k is legal or it is not. Illegal means this prefix cannot extend to a solution — do not descend.
- Choose. Pick a candidate that the prefix still allows. Write it into the path. Mark occupancy.
- Recurse. Run the same procedure at depth
k + 1. If depth isn, record a solution (or return, if one is enough). - Undo. Clear the mark. Remove the pick from the path. The sibling candidate must see the prefix as it was before this try.
The undo is the algorithm. Forget it and every later branch inherits a lie: a column still “used,” a flag still on, a digit still in the box.
Note: Recursion is a stack of prefixes. Depth here is the assignment length — n for N-queens, n for a pick-or-skip walk over n items — not |V| of a service graph. The DFS post already owns the production-sized call-stack trap.
Lab: N-queens on n = 4
One queen per row. col[row] is the column. Two queens attack if they share a column, a diagonal (row - col), or an anti-diagonal (row + col). The intern’s model is “every permutation of columns, then scan pairs.” Columns-as-permutation already kills the column attacks. Diagonals are still a post-pass.
Finishing the permutation is the wrong primitive once a prefix is already illegal. Place row by row. Refuse a column the occupancy arrays already reject.
n = 4, columns left to right. First try at row 0 dies early. Second try yields a solution.
n = 4. col[row] = column.
row 0 → col 0
row 1: 0 column, 1 diagonal → prune; place 2
row 2: 0 / 1 / 2 / 3 all attack the prefix → prune
undo 2
row 1: place 3
row 2: place 1
row 3: 0 / 1 used, 2 diagonal, 3 used → prune
undo 1
undo 0
row 0 → col 1
row 1: 0 diagonal, 1 column, 2 diagonal → prune; place 3
row 2: place 0
row 3: place 2 → solution [1, 3, 0, 2]The board for that solution:
. Q . .
. . . Q
Q . . .
. . Q .Columns 1, 3, 0, 2 are unique. Diagonals row - col are -1, -2, 2, 1. Anti-diagonals row + col are 1, 4, 2, 5. No repeat, so no two queens share a slash. A second solution [2, 0, 3, 1] is the left-right mirror; the same procedure finds it when row 0 continues to column 2.
The dead branch at row 0 / column 0 never built a 4-tuple. Row 2 had nowhere to sit. That is prune: the partial assignment cannot succeed, so the subtree is not a search, it is a return.
Java: occupancy arrays and an undo
There is no java.util.Backtracking. The path is an int[]. The prune is three boolean arrays so a candidate is O(1) to accept or reject. row - col is shifted by n - 1 so the index is non-negative.
static List<int[]> nQueens(int n) {
List<int[]> solutions = new ArrayList<>();
int[] col = new int[n];
boolean[] usedCol = new boolean[n];
boolean[] usedDiag = new boolean[2 * n];
boolean[] usedAnti = new boolean[2 * n];
place(0, n, col, usedCol, usedDiag, usedAnti, solutions);
return solutions;
}
static void place(int row, int n, int[] col, boolean[] usedCol,
boolean[] usedDiag, boolean[] usedAnti, List<int[]> solutions) {
if (row == n) {
solutions.add(col.clone());
return;
}
for (int c = 0; c < n; c++) {
int d = row - c + (n - 1);
int a = row + c;
if (usedCol[c] || usedDiag[d] || usedAnti[a]) {
continue;
}
col[row] = c;
usedCol[c] = usedDiag[d] = usedAnti[a] = true;
place(row + 1, n, col, usedCol, usedDiag, usedAnti, solutions);
usedCol[c] = usedDiag[d] = usedAnti[a] = false;
}
}Clone on success: col is mutated on the way back down. Count-only is an int increment at row == n — do not store boards you will throw away. One-solution is a boolean return as soon as a leaf is legal.
Note: The three = false lines are the undo. Drop them and column c stays occupied for every sibling of this row. The walk above would never retry column 1 after column 0 failed.
Same shape: subsets, not a second lab
Pick-or-skip each index: append a[i], recurse i + 1, remove last; then skip a[i] and recurse. Same choose / recurse / undo. Sudoku is the same occupancy idea on a cell, a row, a column, and a box. Neither needs a second full walk in this post.
at i: choose a[i] → path.add → recurse(i + 1) → path.removeLast
skip a[i] → recurse(i + 1)
leaf: i == n, record pathIf the job is “every subset,” you visit 2^n leaves — there is nothing to memoize. If the job is “best value under a kilogram cap, each crate once,” that tree recomputes (i, remaining). That is 0/1 Knapsack, not this undo.
When a table beats the tree
Overlapping subproblems: two different paths reach the same remaining question. Knapsack’s naive pick-or-skip is correct and exponential; the cell (item i, capacity w) is shared. Fill it once. Coin change, LCS, and edit distance on the hub are the same fork — a recurrence with a table, not a mutable path you undo.
Do not backtrack a 0/1 knapsack and call the call stack a table. Undo is for constraints the next choice reads from the path: attacks, conflicts, “must take A if you took B.” Best-value-under-capacity is a different procedure. This series leaves contest-only DP on the table.
Complexity
| What | Cost | Why |
|---|---|---|
| Time (N-queens) | Exponential in n | Branching starts at n and drops; prune cuts dead prefixes |
| Permute-then-check | Θ(n!) boards | Every column permutation, diagonal test after the fact |
| Time (all subsets) | Θ(2^n) leaves | Each index is choose or skip; no shared cell |
| Extra space | O(n) | Path plus occupancy (or the subset list) |
| Prune test | O(1) per candidate | Boolean column / diagonal (or a HashSet of conflicts) |
Worst case is still exponential: a loose constraint set visits almost every leaf. Pruning is not a different Big-O class. It is why n = 8 queens is instant and n = 8 permute-then-check was already the wrong default. Space is the depth of the assignment, not a second n × W grid.
Branching × depth, minus the prefixes you refuse. Quote n! only for the unpruned permutation generator. Quote 2^n for unconstrained subsets. Do not quote knapsack’s O(nW) for this search.
When not to backtrack
Skip this search when the job is not “extend a constrained prefix.”
- Overlapping subproblems. Pick-or-skip knapsack, unbounded coin change, LCS, edit distance: the same remaining state shows up on many paths. Memoize or fill. That grid lives on 0/1 Knapsack; do not re-derive it here.
- A greedy-choice property holds. Interval scheduling on the hub takes the earliest finish and never revisits it. Searching the power set of meetings is a different bill.
- The graph already exists. Finish times, back edges, and an explicit
ArrayDequeare DFS. Walking adjacency is not buildingcol[row]. - The layout is the data structure. Tree walks and Union-Find live with the layouts, not this procedure catalog. Out of scope here.
- You needed one scan, not a tree. Kadane, sliding window, prefix sums: the hot path is an index, not a partial assignment.
- You only need a count that DP already names. “How many ways to make amount
W” is coin change, not a backtracking counter you forgot to memoize.
Next choice depends on the path, and the prefixes do not repeat as table cells — that is the job. Anything else is a named procedure on the roadmap.
Cheat sheet
Job: search a constrained assignment; next pick depends on the path
Shape: choose → recurse → undo
Prune: if the prefix cannot succeed, do not descend
Lab: N-queens — one queen per row; occupancy on col / diag / anti
Same shape: subsets (choose/skip); Sudoku (cell + row/col/box)
Undo: clear the mark; clone the path on success
Time: exponential; prune beats n! permutations in practice, not in class
Space: O(n) path + occupancy
JDK: none — recursion plus arrays (or ArrayDeque of choices)
Not this: knapsack table, DFS of a given graph, greedy interval pick, layout walksDo:
- Name the occupancy the next choice will read (columns, diagonals, conflicts) before you recurse.
- Undo on the way out, including the failure path. Clone (or copy) a solution off the shared
colarray. - Return at the first leaf if the spec is existence, not enumeration.
- Send overlapping
(i, w)to the knapsack post.
Don’t:
- Generate every permutation and test diagonals at the end.
- Skip the undo and debug “why is this column still taken.”
- Quote a polynomial for N-queens because the prune felt fast on
n = 8. - Re-teach a DP table when the prefixes are the same remaining capacity. Look up 0/1 Knapsack.
Wrap-up
Backtracking replaces “every complete assignment” with one decision at the current depth: choose a still-legal candidate, recurse, undo. N-queens is that loop with three occupancy arrays; a dead prefix at row 2 never becomes a 4-tuple. Subsets and Sudoku use the same shape. When two paths ask the same remaining question, you wanted a table — knapsack, not this tree. When the graph is already built, you wanted DFS.
The layout of a constraint is whatever occupancy you marked. The procedure is this undo. Wave 7 starts at consistent hashing: move few keys when a node joins or dies, not hash % n.