Lesson 29
Backtracking
Try a choice, recurse, undo it — systematic search with early pruning.
01Why it matters & the intuition
Sudoku solvers, N-Queens, permutations, subsets, combination sums and word search are all backtracking. The template is small; the skill is pruning dead branches early.
Think of it like…
Solving a maze by always taking the leftmost unexplored path and chalk-marking your way. At a dead end, you walk back to the last junction, rub out the chalk, and try the next path.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- trying
- attacked — pruned
- queen
03Key ideas
Choose → explore → un-choose
Add a candidate to the partial solution, recurse, then remove it so the next candidate starts from a clean state.
Pruning
Reject partial solutions that already break a rule. In N-Queens, never place a queen on an attacked square — whole subtrees vanish.
State tracking
Use sets for attacked columns and diagonals (r − c and r + c) so each validity check is O(1).
Exponential by nature
Subsets are 2ⁿ and permutations n!. Pruning doesn't change the worst case but makes real inputs fast.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
function solveNQueens(n: number): number[][] {
const solutions: number[][] = [];
const cols = new Set<number>(), diag = new Set<number>(), anti = new Set<number>();
const placement: number[] = []; // placement[row] = column
function place(row: number): void {
if (row === n) { solutions.push([...placement]); return; }
for (let c = 0; c < n; c++) {
if (cols.has(c) || diag.has(row - c) || anti.has(row + c)) continue; // prune
cols.add(c); diag.add(row - c); anti.add(row + c); placement.push(c); // choose
place(row + 1); // explore
cols.delete(c); diag.delete(row - c); anti.delete(row + c); placement.pop(); // un-choose
}
}
place(0);
return solutions;
}05Complexity
| Operation | Time | |
|---|---|---|
| All subsets | O(n · 2ⁿ) | — |
| All permutations | O(n · n!) | — |
| N-Queens (pruned) | ≈ O(n!) | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Count N-Queens solutions
Write total_n_queens(n) returning how many ways n queens can be placed on an n×n board so no two attack each other.