Counting n-queens placements
Hard · Target 25 minutes · Backtracking· Type asked at
Amazon
Deutsche Bank
G-Research
Place n queens on an n × n chessboard so that no two attack each other: no two share a row, a column or a diagonal. Return the number of distinct placements.
Examples
| Input | Output | Why |
|---|---|---|
n = 4 | 2 | Columns by row: 2, 4, 1, 3 and its mirror 3, 1, 4, 2. |
n = 1 | 1 | One queen on one square. |
n = 3 | 0 | No placement exists for n = 2 or n = 3. |
Constraints
- 1 ≤ n ≤ 12
Hints
Hint 1
Two queens in one row always attack each other, so each row holds exactly one queen. What does that reduce the problem to?
Hint 2
Place queens row by row. For the current row, which columns are still safe given the queens above?
Hint 3
Keep three sets: columns in use, "\" diagonals in use (row − column constant) and "/" diagonals in use (row + column constant). A square is safe if it is in none of them.
Where people lose marks
- Checking attacks by scanning the whole board for every candidate square: correct but O(n²) per check.
- Forgetting one diagonal direction. Both r − c and r + c must be tracked.
- With arrays for diagonals, indexing r − c without an offset: it goes negative. Add n − 1.
- In the bitmask version, not masking with (1 << n) − 1: bits shifted past column n − 1 are treated as columns.
Dry run on 4
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 32column per row10·1·2·3row1found0
Row 1: column 1 is not attacked. Place a queen and go down a row.
-
Step 2 / 32column per row1031·2·3row2found0
Row 2: column 3 is not attacked. Place a queen and go down a row.
-
Step 3 / 32column per row1031·2·3row3found0
Row 3 has no safe column left. Back up to row 2.
-
Step 4 / 32column per row1041·2·3row2found0
Row 2: column 4 is not attacked. Place a queen and go down a row.
-
Step 5 / 32column per row104122·3row3found0
Row 3: column 2 is not attacked. Place a queen and go down a row.
-
Step 6 / 32column per row104122·3row4found0
Row 4 has no safe column left. Back up to row 3.
-
Step 7 / 32column per row1041·2·3row3found0
Row 3 has no safe column left. Back up to row 2.
-
Step 8 / 32column per row10·1·2·3row2found0
Row 2 has no safe column left. Back up to row 1.
-
Step 9 / 32column per row20·1·2·3row1found0
Row 1: column 2 is not attacked. Place a queen and go down a row.
-
Step 10 / 32column per row2041·2·3row2found0
Row 2: column 4 is not attacked. Place a queen and go down a row.
-
Step 11 / 32column per row204112·3row3found0
Row 3: column 1 is not attacked. Place a queen and go down a row.
-
Step 12 / 32column per row20411233row4found0
Row 4: column 3 is not attacked. Place a queen and go down a row.
-
Step 13 / 32column per row20411233found1
All 4 rows filled: columns 2, 4, 1, 3. Solution 1.
-
Step 14 / 32column per row204112·3row4found1
Row 4 has no safe column left. Back up to row 3.
-
Step 15 / 32column per row2041·2·3row3found1
Row 3 has no safe column left. Back up to row 2.
-
Step 16 / 32column per row20·1·2·3row2found1
Row 2 has no safe column left. Back up to row 1.
-
Step 17 / 32column per row30·1·2·3row1found1
Row 1: column 3 is not attacked. Place a queen and go down a row.
-
Step 18 / 32column per row3011·2·3row2found1
Row 2: column 1 is not attacked. Place a queen and go down a row.
-
Step 19 / 32column per row301142·3row3found1
Row 3: column 4 is not attacked. Place a queen and go down a row.
-
Step 20 / 32column per row30114223row4found1
Row 4: column 2 is not attacked. Place a queen and go down a row.
-
Step 21 / 32column per row30114223found2
All 4 rows filled: columns 3, 1, 4, 2. Solution 2.
-
Step 22 / 32column per row301142·3row4found2
Row 4 has no safe column left. Back up to row 3.
-
Step 23 / 32column per row3011·2·3row3found2
Row 3 has no safe column left. Back up to row 2.
-
Step 24 / 32column per row30·1·2·3row2found2
Row 2 has no safe column left. Back up to row 1.
-
Step 25 / 32column per row40·1·2·3row1found2
Row 1: column 4 is not attacked. Place a queen and go down a row.
-
Step 26 / 32column per row4011·2·3row2found2
Row 2: column 1 is not attacked. Place a queen and go down a row.
-
Step 27 / 32column per row401132·3row3found2
Row 3: column 3 is not attacked. Place a queen and go down a row.
-
Step 28 / 32column per row401132·3row4found2
Row 4 has no safe column left. Back up to row 3.
-
Step 29 / 32column per row4011·2·3row3found2
Row 3 has no safe column left. Back up to row 2.
-
Step 30 / 32column per row4021·2·3row2found2
Row 2: column 2 is not attacked. Place a queen and go down a row.
-
Step 31 / 32column per row4021·2·3row3found2
Row 3 has no safe column left. Back up to row 2.
-
Step 32 / 32column per row40·1·2·3row2found2
Row 2 has no safe column left. Back up to row 1. Search finished: 2 placements.
How to think about it
Every row must hold exactly one queen, so a placement is a choice of column for each row. Place queens row by row, and for each row try only the columns that are not attacked by the queens already placed. When a row has no safe column, back up one row and try its next option.
A square (r, c) is attacked from above if its column is taken, or its "\" diagonal
(r − c constant) or its "/" diagonal (r + c constant) is. Keeping those three
as sets makes the check O(1). With bitmasks it is one expression: as you move down a row, the
diagonal masks shift one place left and right, and the safe columns are the zero bits of
cols | diag1 | diag2.
The pruning is what makes it work. Trying every one-per-row placement for n = 8 means 8⁸ ≈ 16.8 million leaves; the backtracking search places a queen only 2,056 times in total, and finds all 92 solutions.
The trick bits & −bits isolates the lowest set bit, which is how the
bitmask version walks through the safe columns without looping over all n.
Complexity. Time O(n!) at worst, far less in practice · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def n_queens_count(n):
full = (1 << n) - 1 # one bit per column
def place(cols, d1, d2):
if cols == full:
return 1 # every row has its queen
count = 0
free = full & ~(cols | d1 | d2) # columns not attacked in this row
while free:
bit = free & -free # lowest free column
free ^= bit
count += place(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
return count
return place(0, 0, 0)static int place(int full, int cols, int d1, int d2) {
if (cols == full) return 1; // every row has its queen
int count = 0, free = full & ~(cols | d1 | d2);
while (free) {
const int bit = free & -free; // lowest free column
free ^= bit;
count += place(full, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
}
int solve(int n) {
return place((1 << n) - 1, 0, 0, 0);
}class Solution {
public int nQueensCount(int n) {
return place((1 << n) - 1, 0, 0, 0);
}
private int place(int full, int cols, int d1, int d2) {
if (cols == full) return 1; // every row has its queen
int count = 0, free = full & ~(cols | d1 | d2);
while (free != 0) {
int bit = free & -free; // lowest free column
free ^= bit;
count += place(full, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
}
}function nQueensCount(n) {
const full = (1 << n) - 1; // one bit per column
const place = (cols, d1, d2) => {
if (cols === full) return 1; // every row has its queen
let count = 0, free = full & ~(cols | d1 | d2);
while (free) {
const bit = free & -free; // lowest free column
free ^= bit;
count += place(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
};
return place(0, 0, 0);
}fn place(full: u32, cols: u32, d1: u32, d2: u32) -> u32 {
if cols == full {
return 1; // every row has its queen
}
let (mut count, mut free) = (0, full & !(cols | d1 | d2));
while free != 0 {
let bit = free & free.wrapping_neg(); // lowest free column
free ^= bit;
count += place(full, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
count
}
fn solve(n: u32) -> u32 {
place((1 << n) - 1, 0, 0, 0)
}import Data.Bits ((.&.), (.|.), complement, shiftL, shiftR, xor)
-- cols, d1, d2 are bitmasks of attacked columns in the current row.
solve :: Int -> Int
solve n = place 0 0 0
where
full = shiftL 1 n - 1 :: Int
place cols d1 d2
| cols == full = 1
| otherwise = go (full .&. complement (cols .|. d1 .|. d2))
where
go 0 = 0
go free =
let bit = free .&. negate free -- lowest free column
in place (cols .|. bit) (shiftL (d1 .|. bit) 1 .&. full) (shiftR (d2 .|. bit) 1)
+ go (free `xor` bit)Variants to try
- Return the boards themselves (N-Queens I): record the column chosen in each row at every solution.
- Use symmetry: count placements with the first queen in the left half and double, handling the middle column separately for odd n.
- n up to 27: the bitmask search with symmetry is what the published counts used; the numbers grow roughly like n! / cⁿ.
Next problems
Sum of every subset’s XOR
Every element is either in or out. Walking that binary tree visits each subset once, carrying its XOR as you go.
Open the problem → Medium20 minSigns that reach a target
Put + or − in front of each number and count the ways to hit the target. Search first, then notice the states repeat.
Open the problem →Write a solution and run it against the real test table.
Keep going
Sum of every subset’s XOR
Every element is either in or out. Walking that binary tree visits each subset once, carrying its XOR as you go.
Open the problem → Medium20 minSigns that reach a target
Put + or − in front of each number and count the ways to hit the target. Search first, then notice the states repeat.
Open the problem → BacktrackingThe pattern behind it
Build a solution one choice at a time, and abandon a branch the moment it cannot succeed.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.