Backtracking & Pruning: N-Queens

Sudoku solvers, crossword fillers, timetable schedulers and regex engines all work the same way: build a solution step by step and back off the moment it breaks a rule. That habit turns hopeless searches into fast ones.

★ Lecture: rekursia_queen · Zaza Gamezardashvili▶ video intermediate⏱ 14 min read

←Builds on

4Generating Subsets & PermutationsBacktracking is subset generation that abandons a branch the moment it breaks a rule.3Stack (LIFO) & Expression EvaluationUndoing a choice on return is popping it off the stack of choices made so far.

Leads to→

6Depth-First Search (DFS)DFS goes deep and backs up exactly like a backtracking search.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01The N-Queens puzzle

Place n queens on an n × n chessboard so that no two attack each other. A queen attacks along its row, its column and both diagonals.

Pure brute force would try every way to put n queens on n² squares: for n = 8 that is about 4.4 billion placements. A first observation cuts this down: two queens can never share a row, so put exactly one queen per row and only choose its column. That leaves nⁿ choices, about 16.7 million for n = 8.

Still, almost all of them are hopeless from the second queen on. If queens 1 and 2 already attack each other, none of the n^(n−2) ways to finish the board (8⁶ for n = 8) can help. The search should notice that and stop.

02Choose, explore, undo

Backtracking builds a solution one decision at a time. For N-Queens, place(r) puts a queen in row r:

if r == n, all queens are placed: a solution;
for each column c: if the square is attacked, skip it; otherwise choose (put the queen at (r, c)), explore (place(r + 1)), and if that fails, undo (remove the queen) and try the next column.

When no column in row r works, place(r) returns false and the caller moves its own queen. That retreat is the "back" in backtracking.

It is the same recursion as generating subsets, with one addition: a validity check before going deeper. Because each undo restores the state exactly, one shared board is enough for the whole search.

03Pruning: cut whole subtrees

Picture the search tree: the root is the empty board, each level is a row, each child a column choice. Brute force visits every leaf. Backtracking checks each new queen as soon as it is placed; a conflict means that node is dropped together with its entire subtree, which is never generated at all.

That is pruning, and it is where the speed comes from. For n = 4, the first solution is found after examining only 26 squares, with 4 backtracks, instead of 4⁴ = 256 full placements. For n = 8, finding all 92 solutions examines about 15 700 squares instead of 16.7 million full placements.

General rule: test constraints as early as possible. The earlier a dead branch is recognised, the bigger the subtree you skip.

04O(1) checks and the real cost

Checking a square against every earlier queen costs O(n). You can make it O(1) with three boolean arrays:

col[c]: column c is taken;
d1[r − c + n − 1]: the ↘ diagonal is taken (all its squares share r − c);
d2[r + c]: the ↙ diagonal is taken (all its squares share r + c).

Placing a queen sets three flags; removing it clears them. That is the whole "undo" step.

The worst case of backtracking is still exponential: pruning changes how much of the tree you see, not the size of the tree. In practice it is often fast enough for n up to 12 or so when counting all solutions. If it is still too slow, better pruning, a smarter order of choices, or memoization (dynamic programming) are the next steps.

Cost at a glance

Worst caseO(n!)

Safety check (with arrays)O(1)

MemoryO(n)

Remember

Backtracking builds a solution step by step: choose, explore recursively, then undo to restore the state.
Checking constraints before going deeper prunes whole subtrees, which is where the speedup comes from.
For N-Queens, arrays indexed by column, r − c and r + c make every safety check O(1).

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

More from the lectures▶ Knight's tour

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the tree grow on the right: red X’s are pruned squares, grey circles are dead ends you backtracked from. Try n = 5 (no backtracking at all) and n = 6.

Interactive visualizerfocus here, then space ← →

4 queens: board and search tree

Search tree (node = queen column)

queenattackedpruneddead end (backtracked)

Place 4 queens on a 4×4 board so that no two attack each other. One queen per row; we try columns left to right and undo choices that lead nowhere.

Pseudocode

 1 bool place(int r):           // put a queen in row r 2   if r == n: return true      // all n queens placed 3   for c in 0..n-1: 4     if attacked(r, c): continue    // prune this branch 5     queen[r] = c 6     if place(r+1): return true 7     remove queen[r]            // backtrack, try next c 8   return false                 // dead end

1 / 1

Check

Three questions. Pick an answer to see why.

A queen stands at row 1, column 2 (0-based). Which square in row 3 is attacked diagonally?

place(r) tried every column of row r and all were attacked. What happens next?

Why is checking each queen right after placing it faster than checking only complete boards?

Practice

Real problems to lock it in, easiest first.

CSESChessboard and Queens intermediate↗LeetCodeWord Search intermediate↗LeetCodeN-Queens advanced↗LeetCodeSudoku Solver advanced↗CSESGrid Path Description advanced↗