Learn
Understand backtracking with n queens on a chessboard
A queen attacks along its row, column and both diagonals. Place n of them on an n×n board so that none attack each other. The puzzle is small, but the way you solve it (try, check, recurse, undo) shows up everywhere from Sudoku to compilers.
01 The puzzle
A queen can move any distance in a straight line: sideways, up and down, or diagonally. Two queens attackeach other if one could move onto the other. We want n queens on an n × n board with no attacking pair.
n queens, n rows, at most one each, so every row gets exactly one.
So a solution is a list of n different column numbers.
(0, 0) and (3, 3) attack across the whole board.
Because there's exactly one queen per row, a whole board fits in a list: cols[r] = the column of the queen in row r. The 4×4 answer [1, 3, 0, 2] means row 0 → column 1, row 1 → column 3, and so on.
02 Try it by hand
Before any algorithm, try it yourself. Click squares to place queens. Attacking pairs turn red, a line connects them, and the caption shows the arithmetic. 4×4 takes a minute; 8×8 takes a while.
Click squares to place 4 queens so that no two share a row, column or diagonal.
03 The attack test
Since rows are always different, we only check columns and diagonals. Take two queens at (r₁, c₁)and (r₂, c₂):
Why the second part means "same diagonal": moving diagonally changes the row and the column by the same amount. So two squares are on a shared diagonal exactly when the vertical gap equals the horizontal gap.
| Queens | |Δrow| | |Δcol| | Attack? |
|---|---|---|---|
| (0, 1) and (2, 3) | 2 | 2 | diagonal ✗ |
| (0, 1) and (1, 3) | 1 | 2 | safe ✓ |
| (1, 3) and (3, 3) | 2 | 0 | column ✗ |
| (0, 1) and (3, 2) | 3 | 1 | safe ✓ |
A faster version: diagonals as numbers
Every square on a ↘ diagonal has the same r − c, and every square on a ↗ diagonal has the samer + c. For the queen at (1, 3): r − c = −2 and r + c = 4. Any other square with r − c = −2, like (0, 2) or (2, 4), shares its ↘ diagonal.
Keep three sets: used columns, used r − c values and used r + c values. Then "is this square safe?" is three lookups, O(1), instead of a loop over every queen above.
04 How big is the search?
Each rule we bake in shrinks the number of boards we'd have to look at:
| Strategy | Formula | n = 4 | n = 8 |
|---|---|---|---|
| Any n squares | C(n², n) | 1,820 | 4,426,165,368 |
| One queen per row | nⁿ | 256 | 16,777,216 |
| One per row and column | n! | 24 | 40,320 |
| Backtracking, all solutions | queens placed | 16 | 2,056 |
Where the formulas come from: C(n², n) chooses n of the n² squares. With one queen per row, each of the n rows picks one of n columns: n × n × … = nⁿ. If columns must differ too, row 0 has n choices, row 1 has n − 1, and so on: n!.
Brute force over n! would build every complete board and then test it. Backtracking only ever builds partial boards, and drops one the moment two queens clash: one bad queen in row 1 cuts off every board that would have built on it. For n = 8 it places 2,056 queens in total (checking 15,720 squares along the way) instead of building 40,320 full boards.
05 Backtracking
Fill the board one row at a time. In each row, try columns left to right:
solve(row):
if row == n:
record the solution
return
for col in 0 .. n−1:
if safe(row, col):
place a queen at (row, col)
solve(row + 1)
remove the queen from (row, col) # backtrack- Try: put a queen in the next safe column.
- Recurse: move on to the next row with that choice locked in.
- Undo: when the recursion comes back (a dead end, or we want more solutions), lift the queen and try the next column.
The "remove" line is the whole idea. Without it, one bad early choice would be permanent. With it, the search explores choices like a depth-first walk and climbs back up whenever a branch fails.
06 Watch it solve 4×4
Step through the smallest interesting case. The caption shows the attack test for every square, and the call stack shows which rows are "in progress". It finds [1, 3, 0, 2] after 35 steps.
Empty 4×4 board. The solver fills one row at a time, trying columns left to right.
07 Worked trace
The same run as a paper trace. Coordinates are (row, column):
| # | Step | Why |
|---|---|---|
| 1 | place (0, 0) | safe from every queen above |
| 2 | check (1, 0) | column 0 taken by row 0 |
| 3 | check (1, 1) | |1−0| = |1−0| = 1 → diagonal with (0, 0) |
| 4 | place (1, 2) | safe from every queen above |
| 5 | check (2, 0) | column 0 taken by row 0 |
| 6 | check (2, 1) | |2−1| = |1−2| = 1 → diagonal with (1, 2) |
| 7 | check (2, 2) | |2−0| = |2−0| = 2 → diagonal with (0, 0) |
| 8 | check (2, 3) | |2−1| = |3−2| = 1 → diagonal with (1, 2) |
| 9 | row 2 exhausted | no safe column → backtrack |
| 10 | remove (1, 2) | try column 3 next |
| 11 | place (1, 3) | safe from every queen above |
| 12 | check (2, 0) | column 0 taken by row 0 |
| 13 | place (2, 1) | safe from every queen above |
| 14 | check (3, 0) | column 0 taken by row 0 |
| 15 | check (3, 1) | |3−1| = |1−3| = 2 → diagonal with (1, 3) |
| 16 | check (3, 2) | |3−2| = |2−1| = 1 → diagonal with (2, 1) |
| 17 | check (3, 3) | |3−0| = |3−0| = 3 → diagonal with (0, 0) |
| 18 | row 3 exhausted | no safe column → backtrack |
| 19 | remove (2, 1) | try column 2 next |
| 20 | check (2, 2) | |2−0| = |2−0| = 2 → diagonal with (0, 0) |
| 21 | check (2, 3) | column 3 taken by row 1 |
| 22 | row 2 exhausted | no safe column → backtrack |
| 23 | remove (1, 3) | try column 4 next |
| 24 | row 1 exhausted | no safe column → backtrack |
| 25 | remove (0, 0) | try column 1 next |
| 26 | place (0, 1) | safe from every queen above |
| 27 | check (1, 0) | |1−0| = |0−1| = 1 → diagonal with (0, 1) |
| 28 | check (1, 1) | column 1 taken by row 0 |
| 29 | check (1, 2) | |1−0| = |2−1| = 1 → diagonal with (0, 1) |
| 30 | place (1, 3) | safe from every queen above |
| 31 | place (2, 0) | safe from every queen above |
| 32 | check (3, 0) | column 0 taken by row 2 |
| 33 | check (3, 1) | column 1 taken by row 0 |
| 34 | place (3, 2) | safe from every queen above |
| 35 | solution | columns [1, 3, 0, 2] |
Solution [1, 3, 0, 2] after 4 dead ends and 4 backtracks
08 The search tree
Draw every placed queen as a node and the run becomes a tree. Depth = row. Red columns were rejected by the attack test; they're pruned, so nothing below them is ever explored.
- empty board
- row 0 → col 0row 1 rejects col 0, 1dead end
- row 1 → col 2row 2 rejects col 0, 1, 2, 3dead end
- row 1 → col 3row 2 rejects col 0, 2, 3dead end
- row 2 → col 1row 3 rejects col 0, 1, 2, 3dead end
- row 0 → col 1row 1 rejects col 0, 1, 2
- row 1 → col 3
- row 2 → col 0row 3 rejects col 0, 1
- row 3 → col 2solution
Every branch under column 0 in row 0 dies, so the solver backs all the way up to row 0 and moves the first queen to column 1. From there it reaches a solution without a single further backtrack.
09 How many solutions?
| n | Solutions | n! | Fraction of permutations that work |
|---|---|---|---|
| 1 | 1 | 1 | 1 in 1 |
| 2 | 0 | 2 | none |
| 3 | 0 | 6 | none |
| 4 | 2 | 24 | 1 in 12 |
| 5 | 10 | 120 | 1 in 12 |
| 6 | 4 | 720 | 1 in 180 |
| 7 | 40 | 5,040 | 1 in 126 |
| 8 | 92 | 40,320 | 1 in 438 |
| 9 | 352 | 362,880 | 1 in 1,031 |
| 10 | 724 | 3,628,800 | 1 in 5,012 |
| 11 | 2,680 | 39,916,800 | 1 in 14,894 |
| 12 | 14,200 | 479,001,600 | 1 in 33,733 |
Why n = 2 and n = 3 are impossible
- n = 2: any two squares on a 2×2 board share a row, column or diagonal.
- n = 3: look at row 1's queen. In the middle, (1, 1), it attacks every other square on the board, so rows 0 and 2 have nowhere to go. On a side, say (1, 0), the only squares left in rows 0 and 2 are (0, 2) and (2, 2), and those two share column 2.
Symmetry
Rotating or mirroring a solution gives another solution. 8×8's 92 solutions come from just 12 "shapes": 11 shapes × 8 rotations/reflections + 1 symmetric shape × 4 = 88 + 4 = 92.
10 Cost and faster checks
- Upper bound: at most n! complete boards, times O(n) per check with the simple loop, so O(n · n!). Pruning makes the real number far smaller, but it still grows exponentially when you want all solutions.
- Sets for O(1) checks: track used columns, r − c and r + c (section 03).
- Bitmasks: store those three sets as integers. Shifting the diagonal masks by one each row lets a solver find all 14,200 solutions for n = 12 in milliseconds.
- Just one solution, huge n: skip backtracking entirely. Min-conflicts local search (start with any permutation, repeatedly move the queen with the most conflicts) solves n = 1,000,000 in seconds.
11 Check yourself
Q1. Do (2, 5) and (5, 2) attack each other?
|Δrow| = |2 − 5| = 3 and |Δcol| = |5 − 2| = 3. Equal, so yes, they share a diagonal. Check with sums: 2 + 5 = 7 and 5 + 2 = 7, the same ↗ diagonal.
Q2. Why does the solver never check if two queens share a row?
It places exactly one queen per row by construction, so a row clash can't happen.
Q3. On 4×4, why does starting at (0, 0) fail?
Row 1 can only use column 2 or 3. Column 2 blocks all of row 2. Column 3 leaves only (2, 1), which then blocks all of row 3. Every branch dies, so (0, 0) is in no solution. By mirror symmetry, neither is (0, 3).
Q4. What changes in the code to find all solutions instead of the first?
Don't stop at the first row == n. Record it and return normally, so the loop keeps backtracking and trying the remaining columns.
12 Cheat sheet
| Board as data | cols[r] = column of the queen in row r |
| Attack test | c₁ = c₂ or |r₁ − r₂| = |c₁ − c₂| |
| O(1) test | sets of used c, r − c, r + c |
| Algorithm | row by row: try a safe column → recurse → undo |
| Search space | C(n², n) ≫ nⁿ ≫ n! ≫ what backtracking visits |
| Counts | n = 4: 2 · n = 8: 92 (12 up to symmetry) · n = 2, 3: none |
| Same pattern in | Sudoku, graph coloring, subsets/permutations, crosswords, SAT solvers |