N-Queens asked for the boards. This one asks only how many there are. That sounds like a smaller problem — delete the rendering code and return a number — and the naive version of that answer is exactly what the question is designed to catch.
The problem
Given n, return the number of distinct solutions to the n-queens puzzle.
n = 1 -> 1
n = 2 -> 0
n = 3 -> 0
n = 4 -> 2
n = 8 -> 92
n = 9 -> 352Do not build what you are going to count
The tempting move is to call the previous solution and return boards.size(). It is
correct, and it allocates n strings for every one of those 92 solutions in order to
throw all of them away. For n = 9 that is over three thousand strings whose only
contribution is to be counted.
The fix is structural, not cosmetic: make the recursion return a count rather than append to a list. The base case stops being "record this board" and becomes "return 1".
place(row) = 1 if row == n
= sum over legal cols of place(row + 1)That is the whole change, and it is the one the interviewer is looking for. Everything below is about making the legality test cheaper.
From an O(n) check to an O(1) one
The previous solution rescanned every placed queen to validate a square, so each placement cost
O(n). Instead, mark what is already attacked and check the marks in constant time.
Columns are easy — one flag per column. Diagonals need a way to name them, and both have a neat one:
↘ diagonal row - col is constant along it
↙ diagonal row + col is constant along it
r-c: 0 -1 -2 -3 r+c: 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 6So a square is safe when its column, its row - col diagonal and its
row + col diagonal are all unmarked. In Java row - col is negative half
the time, so shift it by n - 1 to index an array. Python skips that entirely — a set
takes negative keys without complaint.
Java
class Solution {
public int totalNQueens(int n) {
// Diagonal indices run 0 .. 2n-2 after the shift, so 2n slots is enough
// and stays valid for n = 0 (a size 2n-1 array would throw there).
return place(n, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
}
private int place(int n, int row, boolean[] col, boolean[] down, boolean[] up) {
if (row == n) return 1; // a full board -- count it, do not build it
int count = 0;
for (int c = 0; c < n; c++) {
int d = row - c + n - 1; // shifted so the index is never negative
int u = row + c;
if (col[c] || down[d] || up[u]) continue;
col[c] = down[d] = up[u] = true;
count += place(n, row + 1, col, down, up);
col[c] = down[d] = up[u] = false; // the undo is mandatory here
}
return count;
}
}The undo that N-Queens could skip is load-bearing now. Those three arrays are shared by every branch of the search, so leaving a mark set after a branch returns would make later branches believe a square is attacked when it is not — and the symptom is an answer that is too small, with no crash and no obvious culprit.
Python
class Solution:
def totalNQueens(self, n: int) -> int:
cols: set[int] = set()
down: set[int] = set() # keyed by row - col
up: set[int] = set() # keyed by row + col
def place(row: int) -> int:
if row == n:
return 1
count = 0
for col in range(n):
if col in cols or row - col in down or row + col in up:
continue
cols.add(col); down.add(row - col); up.add(row + col)
count += place(row + 1)
cols.remove(col); down.remove(row - col); up.remove(row + col)
return count
return place(0)No shift, because a set is keyed by value rather than by offset and -3 is a perfectly
good key. This is the kind of place where reaching for the Python data structure instead of
transliterating the Java one actually removes a bug source.
The bitmask version, if you are asked to go faster
The three boolean arrays are really three bit sets, and Java has integers. Each recursive call
shifts the diagonal masks by one, because a diagonal that blocks column c on this row
blocks c ± 1 on the next:
private int place(int n, int cols, int down, int up) {
int full = (1 << n) - 1;
if (cols == full) return 1; // n bits set means n queens placed
int count = 0;
int free = ~(cols | down | up) & full;
while (free != 0) {
int bit = free & -free; // lowest set bit: the next candidate column
free -= bit;
count += place(n, cols | bit, ((down | bit) << 1) & full, (up | bit) >> 1);
}
return count;
}free & -free isolating the lowest set bit is the trick worth knowing; it turns
"loop over columns and skip the blocked ones" into "loop over exactly the free ones". There is no
row parameter because cols already encodes the depth.
Offer this only after the readable version works. Leading with it reads as memorised, and if the
interviewer asks you to explain the << 1 you need to be able to.
Complexity
| Time | Space | |
|---|---|---|
| Rescan each placement (51) | O(n! · n) | O(n) |
| Marked columns and diagonals | O(n!) | O(n) |
| Bitmask | O(n!) | O(n) recursion only |
All three are exponential — the marks remove a linear factor, not the factorial. What actually
changes between them is the constant, and the constant is the entire reason n = 14 is
reachable and n = 20 is not.
The output space is the real win over problem 51: O(n) here against
O(n² · solutions) there.
The symmetry you can mention but should not implement
Every board's mirror image is also a solution, so for n > 1 you can search only
the first half of the columns in row 0 and double the count — with a correction when n
is odd and the queen sits in the middle column. It roughly halves the work.
Mentioning it shows you are still thinking; writing it under interview pressure invites an off-by-one in the odd case that costs more than it saves. Say it, then leave it.
What the interviewer is checking
- That the recursion returns a count instead of building boards you discard.
row - colandrow + colas the two diagonal identities.- That you shift
row - colbefore using it as a Java array index, or use a set. - That you undo all three marks — and can explain why this version cannot skip the undo when problem 51 could.
n = 2andn = 3returning0, which is the answer and not a failure.- That you can name a further optimisation without being tempted to write it.