Appearance
4.18.9 — N-Queens
LeetCode 51 · Hard
The problem
Place n queens on an n × n board so that no two attack each other. A queen attacks along its row, its column, and both diagonals. Return every distinct arrangement.
n = 4 → 2 solutions
. Q . . . . Q .
. . . Q Q . . .
Q . . . . . . Q
. . Q . . Q . .n is at most 9.
The pattern
Two reductions make this tractable, and the first one is free.
One queen per row. No two queens can share a row, and there are n queens and n rows, so every row holds exactly one. That means you never search over rows — you place row 0, then row 1, and so on, and the only decision is which column.
The search space drops from "choose 8 squares out of 64" (4 \times 10^9) to "choose a column for each row" (8^8 = 16.7 million). Before any pruning.
Then: prune at the moment of placing. Check the conflict as you choose a column, not after building a whole board. That takes 16.7 million down to about 2,000 positions actually explored.
This is the difference the constraint step makes, and it is why N-Queens is the reference problem for backtracking.
Naming the conflict groups
A candidate square (r, c) conflicts if another queen shares its column or either diagonal. Checking that by scanning the board is O(n) per candidate. You can make it O(1) by giving each group a name and keeping a set of the occupied ones.
Column: the name is c. Obvious.
The ↘ diagonal (top-left to bottom-right): moving down-right adds 1 to both r and c, so r − c stays constant along it.
The ↗ diagonal (top-right to bottom-left): moving down-left adds 1 to r and subtracts 1 from c, so r + c stays constant.
r − c on a 4×4 board r + c on a 4×4 board
0 -1 -2 -3 0 1 2 3
1 0 -1 -2 1 2 3 4
2 1 0 -1 2 3 4 5
3 2 1 0 3 4 5 6Every ↘ diagonal is one value of r − c; every ↗ diagonal is one value of r + c.
This is exactly the box-index idea from 4.4.8 Valid Sudoku — give each group a computable name, keep one set per group, and membership becomes O(1). Same technique, different geometry.
Think of this like assigning zip codes to every diagonal line crossing a city grid. If you place a queen on a corner, you instantly look up the two "zip codes" for the two diagonal streets she controls. When placing the next queen, you just check if her street zip code is already in your "occupied" list. You don't need to manually walk down the street to see if someone is there.
The solution
python
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = [] # (1)
cols = set() # (2)
diag = set() # (3) r − c (the ↘ diagonals)
anti = set() # (4) r + c (the ↗ diagonals)
placement = [] # (5) placement[r] = the column used in row r
def backtrack(r: int): # (6)
if r == n: # (7) all rows filled
result.append(['.' * c + 'Q' + '.' * (n - c - 1)
for c in placement])
return
for c in range(n): # (8)
if c in cols or (r - c) in diag or (r + c) in anti: # (9)
continue # attacked — prune
cols.add(c) # (10)
diag.add(r - c)
anti.add(r + c)
placement.append(c) # (11)
backtrack(r + 1) # (12)
placement.pop() # (13) undo all four
anti.discard(r + c)
diag.discard(r - c)
cols.discard(c)
backtrack(0)
return resultts
function solveNQueens(n: number): string[][] {
const result: string[][] = []; // (1)
const cols = new Set<number>(); // (2)
const diag = new Set<number>(); // (3)
const anti = new Set<number>(); // (4)
const placement: number[] = []; // (5)
function backtrack(r: number): void { // (6)
if (r === n) { // (7)
result.push(placement.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
return;
}
for (let c = 0; c < n; c++) { // (8)
if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue; // (9)
cols.add(c); diag.add(r - c); anti.add(r + c); // (10)
placement.push(c); // (11)
backtrack(r + 1); // (12)
placement.pop(); // (13)
anti.delete(r + c); diag.delete(r - c); cols.delete(c);
}
}
backtrack(0);
return result;
}Line by line
(1) result collects every complete board.
(2) The columns that already hold a queen.
(3) The downward diagonals (↘) that already hold a queen. Every cell on one of these diagonals has the same value of r - c, row minus column. So that number names the diagonal.
(4) The upward diagonals (↗) that already hold a queen. Every cell on one of these has the same r + c.
(5) placement[r] is the column of the queen in row r. We place exactly one queen per row, so this is enough to describe the whole board.
(6) backtrack(r) places a queen in row r. Rows above it already have their queens.
(7) All n rows have a queen, so this is a solution. Only now do we build the board as strings: row r is c dots, a Q, and the rest dots.
(8) Try each column in this row.
(9) Skip a square that is attacked by an earlier queen: same column, same ↘ diagonal, or same ↗ diagonal. Each check is a set lookup, so it is constant time.
(10) Place the queen: record its column and its two diagonals as taken,
(11) and note its column for this row.
(12) Place queens in the remaining rows.
(13) Undo all four records, in reverse order, so the next column in this row starts from a clean state.
Four pieces of state, four undos. Miss one and later branches see phantom queens. Writing the undos in reverse order of the additions is a habit that makes them easy to check by eye.
No board is stored during the search. placement[r] = c is all the information there is, and the board strings are built only when a solution is complete. That keeps the recursion light and the state trivial to undo.
The check is one line and O(1), which is the entire performance story.
Why r − c can be negative
r − c ranges from −(n−1) to n−1. A set handles negative keys with no trouble.
If you wanted arrays instead of sets — which is faster — offset the index by n − 1 so it lands in 0 … 2n−2:
python
diag = [False] * (2 * n - 1) # index with (r - c + n - 1)
anti = [False] * (2 * n - 1) # index with (r + c)That offset is the only fiddly part. Mention it as the improvement you would make if the size mattered.
Edge cases
n = 1. One board:["Q"].n = 2andn = 3. No solution exists, and the answer is[]. Every placement ends with some row where all squares are attacked.n = 4. Two solutions, mirror images of each other.
Complexity
O(n!) in the worst case: n choices in the first row, at most n−1 compatible in the second, and so on. In practice the diagonal constraints cut it far below n!.
O(n) space for the sets and the placement, plus the output.
There is no known polynomial algorithm for counting N-Queens solutions, and the counts are only known up to about n = 27, each one having taken serious computing effort. Saying that is a good way to answer "can you do better".
Let's break this down further:
- Time Complexity: The first row has n choices. The second row has at most n-1 valid choices (since the column used above is blocked, and diagonals block others). The third row has at most n-2 choices, and so on. This bounds the total number of operations strictly by O(n!). Our constant-time O(1) set lookups mean checking legality adds no extra overhead.
- Space Complexity: The recursion goes n levels deep. The three sets (
cols,diag,anti) and theplacementarray each store at most n items. Therefore, auxiliary space is strictly O(n), excluding the final output arrays.
The bitmask version
For the fastest known implementation, replace the three sets with three integers, one bit per group.
python
def solveNQueens(self, n):
result = []
def backtrack(r, cols, diag, anti, placement):
if r == n:
result.append(...)
return
available = ~(cols | diag | anti) & ((1 << n) - 1) # free columns
while available:
bit = available & -available # lowest set bit
available -= bit
c = bit.bit_length() - 1
backtrack(r + 1, cols | bit, (diag | bit) << 1,
(anti | bit) >> 1, placement + [c])
backtrack(0, 0, 0, 0, [])
return resultThe elegant part: shifting the diagonal masks by one as you move to the next row is exactly what a diagonal does geometrically. A ↘ diagonal moves one column right per row, hence << 1; a ↗ diagonal moves one left, hence >> 1. No arithmetic on indices at all.
available & -available isolates the lowest set bit, an idiom from 4.29.
Know it exists. Write the set version in an interview — it is readable and you can explain every line — and mention this if asked about speed.
Where this goes next
- N-Queens II — count the solutions instead of listing them. Same search, no board building.
- Sudoku Solver — this template with three group families (row, column, box) instead of three (column, two diagonals). The validity check from 4.4.8 becomes the pruning step, which is why the bitmask version of that check earns its keep.
- Constraint satisfaction generally — graph colouring, scheduling, timetabling. All of them are "assign values to variables subject to constraints", and all of them are this template with better heuristics on top (choose the most constrained variable first, and the least constraining value).
What the interviewer will push on
"How do you name the diagonals?" r − c and r + c. Derive it by saying what happens to each coordinate as you step along the diagonal.
"Why one queen per row?" They cannot share a row, and there are n of each, so it is forced. That reduction is the first thing to say.
"Where does the pruning happen and how much does it buy?" At the moment of placing, and it takes 8^8 = 16.7 million down to about 2,000.
"Can you make the check O(1)?" Sets or arrays keyed by the three group names — which it already is.
"How would you speed it up further?" Bitmasks, with the diagonal masks shifted per row.
One thing to volunteer: connect it to Valid Sudoku. "Both problems are 'this cell belongs to several overlapping groups' — I name each group with a formula and keep one set per group." That is the transferable idea, and it is why these two problems belong in the same head.
Next: 4.19 moves from trees to graphs, where a node can have many parents and cycles are allowed — and where the heap you built in 4.16 becomes the engine of shortest-path search.