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.

row
Two queens in the same row attack. So: exactly one queen per row.

n queens, n rows, at most one each, so every row gets exactly one.

column
Same for columns: exactly one queen per column.

So a solution is a list of n different column numbers.

diagonal
The tricky one. Two queens on the same diagonal attack, even if they're far apart.

(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.

0123
0123

03 The attack test

Since rows are always different, we only check columns and diagonals. Take two queens at (r₁, c₁)and (r₂, c₂):

c₁ = c₂   or   |r₁ − r₂| = |c₁ − 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)22diagonal ✗
(0, 1) and (1, 3)12safe ✓
(1, 3) and (3, 3)20column ✗
(0, 1) and (3, 2)31safe ✓

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:

StrategyFormulan = 4n = 8
Any n squaresC(n², n)1,8204,426,165,368
One queen per rownⁿ25616,777,216
One per row and columnn!2440,320
Backtracking, all solutionsqueens placed162,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.

0123
0123
0/36

07 Worked trace

The same run as a paper trace. Coordinates are (row, column):

4×4, first solution35 steps
#StepWhy
1place (0, 0)safe from every queen above
2check (1, 0)column 0 taken by row 0
3check (1, 1)|1−0| = |1−0| = 1 → diagonal with (0, 0)
4place (1, 2)safe from every queen above
5check (2, 0)column 0 taken by row 0
6check (2, 1)|2−1| = |1−2| = 1 → diagonal with (1, 2)
7check (2, 2)|2−0| = |2−0| = 2 → diagonal with (0, 0)
8check (2, 3)|2−1| = |3−2| = 1 → diagonal with (1, 2)
9row 2 exhaustedno safe column → backtrack
10remove (1, 2)try column 3 next
11place (1, 3)safe from every queen above
12check (2, 0)column 0 taken by row 0
13place (2, 1)safe from every queen above
14check (3, 0)column 0 taken by row 0
15check (3, 1)|3−1| = |1−3| = 2 → diagonal with (1, 3)
16check (3, 2)|3−2| = |2−1| = 1 → diagonal with (2, 1)
17check (3, 3)|3−0| = |3−0| = 3 → diagonal with (0, 0)
18row 3 exhaustedno safe column → backtrack
19remove (2, 1)try column 2 next
20check (2, 2)|2−0| = |2−0| = 2 → diagonal with (0, 0)
21check (2, 3)column 3 taken by row 1
22row 2 exhaustedno safe column → backtrack
23remove (1, 3)try column 4 next
24row 1 exhaustedno safe column → backtrack
25remove (0, 0)try column 1 next
26place (0, 1)safe from every queen above
27check (1, 0)|1−0| = |0−1| = 1 → diagonal with (0, 1)
28check (1, 1)column 1 taken by row 0
29check (1, 2)|1−0| = |2−1| = 1 → diagonal with (0, 1)
30place (1, 3)safe from every queen above
31place (2, 0)safe from every queen above
32check (3, 0)column 0 taken by row 2
33check (3, 1)column 1 taken by row 0
34place (3, 2)safe from every queen above
35solutioncolumns [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.

  1. empty board
  2. row 0 → col 0row 1 rejects col 0, 1dead end
  3. row 1 → col 2row 2 rejects col 0, 1, 2, 3dead end
  4. row 1 → col 3row 2 rejects col 0, 2, 3dead end
  5. row 2 → col 1row 3 rejects col 0, 1, 2, 3dead end
  6. row 0 → col 1row 1 rejects col 0, 1, 2
  7. row 1 → col 3
  8. row 2 → col 0row 3 rejects col 0, 1
  9. 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?

nSolutionsn!Fraction of permutations that work
1111 in 1
202none
306none
42241 in 12
5101201 in 12
647201 in 180
7405,0401 in 126
89240,3201 in 438
9352362,8801 in 1,031
107243,628,8001 in 5,012
112,68039,916,8001 in 14,894
1214,200479,001,6001 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 datacols[r] = column of the queen in row r
Attack testc₁ = c₂ or |r₁ − r₂| = |c₁ − c₂|
O(1) testsets of used c, r − c, r + c
Algorithmrow by row: try a safe column → recurse → undo
Search spaceC(n², n) ≫ nⁿ ≫ n! ≫ what backtracking visits
Countsn = 4: 2 · n = 8: 92 (12 up to symmetry) · n = 2, 3: none
Same pattern inSudoku, graph coloring, subsets/permutations, crosswords, SAT solvers
Open the solver →