Skip to content

level 8 · Core techniques

Backtracking

Guess, explore, and when it dead-ends — put it back exactly as it was.

13 min 105 XP

what is it

Start here

Backtracking is trial and error, made systematic. It has exactly three moves: **choose** an option, **explore** what follows from it, and — if that leads nowhere — **un-choose** it and put the world back precisely as it was.

That third move is the one everyone forgets, and it's the one the whole technique is named after.

Watch the N-Queens board. We place a queen in a row and move on, purely on faith. When a later row has no safe square anywhere, we've proved that earlier guess was wrong — so the queen gets lifted straight back off the board and we try the next column. Not adjusted. Not patched. **Removed**, so the board is exactly as it was before we guessed.

What makes it usable rather than hopeless is pruning. Brute force would place all the queens and only then check whether they attack each other, testing an astronomical number of arrangements. Backtracking checks *as it goes*, and the moment a partial board is impossible, it abandons that entire branch — every arrangement that started that way, thrown out at once.

Once you see the shape — choose, explore, un-choose — you'll see it everywhere: permutations, subsets, sudoku, word search, maze solving. They're all the same algorithm wearing different clothes.

real-life analogy

Picture it

Exploring a maze with a ball of string

At each junction you pick a corridor and unroll string as you go. Dead end? You don't guess where you came from — you follow the string back, winding it up exactly as it was, and take the next corridor instead. The string is the un-choosing.

interactive visualization

Watch it run

Board size 4 to 7. Watch queens get placed — and lifted back off.

6 queens · none may attack another

012345
0
1
2
3
4
5

Place 6 queens on a 6×6 board so no two share a row, a column, or a diagonal. One queen per row — the only question is which column.

step 01/255

  • comparing
  • moving
  • in final place
  • found it
  • ruled out
1// Place N queens so none can attack another.
2function solve(board, row, n) {
3 if (row === n) return true; // all placed — done
4
5 for (let col = 0; col < n; col++) {
6 if (!isSafe(board, row, col, n)) continue;
7
8 board[row] = col; // choose
9 if (solve(board, row + 1, n)) return true; // explore
10 board[row] = -1; // un-choose — BACKTRACK
11 }
12
13 return false; // no column worked in this row
14}
15
16function isSafe(board, row, col, n) {
17 for (let r = 0; r < row; r++) {
18 const c = board[r];
19 if (c === col) return false; // same column
20 if (Math.abs(c - col) === row - r) return false; // same diagonal
21 }
22 return true;
23}

variables right now

n
6
placed
0
comparisons 0moves 0

the dry run · every step, in words

255 steps

complexity

What it costs

best case
O(n!)
average
O(n!)
worst case
O(n!)
extra memory
O(n)

Factorial in the worst case — it is, after all, searching a huge space. But pruning is what makes it finish at all: the moment a partial board is impossible, every arrangement built on it is discarded at once. The space is just the recursion depth, O(n).

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²) · this one
input size →work →

common mistakes

Common traps

  • Forgetting to un-choose.

    The single most common bug. If you don't restore the state on the way back up, the next branch starts from a dirty board and the answers are nonsense.

  • Checking validity only at the end.

    That's brute force, and it's astronomically slower. Check as you go, so an impossible partial answer is abandoned before you waste time extending it.

  • Mutating shared state and not copying the result when you find it.

    The board keeps changing as you backtrack. If you store a reference to it, you'll come back later and find your 'answer' has been unwound. Copy it out.

  • Thinking backtracking is a different algorithm for each puzzle.

    It isn't. Subsets, permutations, sudoku, N-Queens, word search — all the same choose/explore/un-choose skeleton. Learn the shape once.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+105 XP

01What are the three moves of backtracking?

02What makes backtracking usable instead of hopeless?

03You forget to un-choose after a failed branch. What happens?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.