Backtracking: try it, and be willing to undo it

01 · Foundation

The explore → recurse → undo loop

Every backtracking algorithm, no matter how different the problem looks on the surface, runs the same three-beat rhythm at every decision point:

• Explore — make a choice. Place a queen in a column, fill an empty Sudoku cell with a digit, pick the next item for a subset.
• Recurse — assume that choice is correct, and go solve the rest of the problem exactly the same way, one level deeper.
• Undo — once that recursive call is completely finished — whether it eventually succeeded or ran into a dead end — remove the queen, clear the cell, un-pick the item. Put the shared state back exactly the way it was before you made the choice.

The "undo" step is the part people skip mentally and then get bitten by. It has to run every time, success or failure, because the very next thing that happens is a sibling choice at the same level — trying column 2 instead of column 1 — and that sibling choice needs to start from a clean board, not one still holding a leftover queen from a path that didn't even work out.

02 · Efficiency

Pruning is what makes it fast

Without pruning, backtracking would generate the entire combinatorial search space — every possible arrangement of queens, every possible digit in every cell — which for anything past toy sizes is astronomically large. What actually makes backtracking usable is pruning: checking constraints as early as possible, the moment a partial choice already breaks a rule, and abandoning that branch immediately instead of continuing to build on top of an already-invalid partial solution.

Two queens attacking each other, a Sudoku digit repeating in its row, column, or 3×3 box — these are all detectable the instant you place the piece. There's no reason to keep recursing five levels deeper on a board that's already broken; the check happens before you commit, so a bad branch gets cut off at its root instead of being discovered after wasted work.

03 · Method

A repeatable framework for any backtracking problem

This is the sequence to work through, in order, whether the problem is N-Queens, Sudoku, or a subset/permutation problem you've never seen before.

1. 1 Define what a single "choice" looks likeWhich row does the next queen go in? Which digit goes in the next empty cell? Nail down the shape of one decision before writing any recursion.
2. 2 Write the constraint check firstIs this choice even valid given everything decided so far? Check it before recursing, not after — that ordering is the entire pruning idea from the section above.
3. 3 If valid, make the choice and recurseMutate the shared state — place the queen, fill the cell — then recurse into the next decision as if this one were permanent.
4. 4 Undo the choice after the call returnsWhether that recursive call found a solution or hit a dead end, remove the queen, clear the cell. The next sibling option must start from a clean slate.
5. 5 Define a clear base caseWhat does "a complete, valid solution" actually look like — every row filled, every cell filled? And once you hit it: record it and stop, or record it and keep searching for more? Decide this up front.

04 · Worked example

Placing 4 queens on a 4×4 board

Rows are filled top to bottom (row 0 to row 3); at each row we try columns left to right (0 to 3) and place a queen the moment a column doesn't conflict with any queen already on the board. Two queens conflict if they share a row, a column, or a diagonal — since we place one queen per row by construction, only column and diagonal checks matter here.

Steps 1–4 place queens at (0,0) and (1,2). At row 2, every column already conflicts — column 0 shares row 0's column, column 1 is diagonal to row 1's queen, column 2 shares row 1's column, column 3 is diagonal to row 1's queen. That's a genuine dead end, so we backtrack: undo row 1's queen and try the next column there instead of giving up entirely.

Row 1's next option, column 3, is valid, and it lets row 2 place at column 1. But row 3 then finds every column blocked too, forcing a second, deeper cascade of backtracking: undo row 2, discover row 1 has no columns left either, undo row 1, and climb all the way back to row 0 to try its next option.

Row 0's column 1 opens up a path with no dead ends at all: row 1 lands on column 3, row 2 on column 0, row 3 on column 2. Checking every pair confirms it — no shared rows, columns, or diagonals anywhere. That's the queen placement [1, 3, 0, 2] (reading column-per-row), one of the two valid solutions to 4-Queens.

Open the N-Queens visualizer to watch this exact explore/prune/backtrack sequence animate on the board.

05 · Complexity

Why pruning matters so much

Without any pruning, trying all placements of n items where each has n choices is O(n^n) in the worst case — for N-Queens that means checking every way to drop n queens anywhere on the board, then filtering out the invalid ones at the very end. That's the "generate everything, filter after" approach the intro warned against, and it's hopeless past small boards.

Checking constraints during placement instead of after shrinks the effective search space enormously, even though the worst-case bound technically remains exponential — most branches get cut off two or three levels deep instead of being built out to full depth first. The practical takeaway: where you check constraints — as early as possible — is usually the single biggest lever on backtracking performance, more so than any other optimization you could apply afterward.

06 · Before you start coding

Common mistakes

• Forgetting to actually undo the choice after recursing — mutating shared state like a board array without reverting it corrupts every sibling branch that runs afterward.
• Checking constraints too late, after recursing instead of before — this wastes time exploring branches that were already invalid the moment they were created.
• Not distinguishing "found one valid solution, stop" from "find all valid solutions, keep going" — the base-case handling is genuinely different code depending on which one you need.
• Redoing expensive validity checks from scratch at every cell instead of incrementally tracking what's already placed — e.g. tracking used columns and diagonals as sets, rather than rescanning the whole board on every single attempt.
• Off-by-one errors when mapping board positions to row, column, and diagonal indices — diagonal indices in particular are easy to get backwards.

07 · Try it yourself

See it animate

Both cards below run the exact explore → recurse → undo loop from this page, with pruning visible step by step on the board.