#52 N-Queens II

frequently reported atAmazon Microsoft Google

the problem

In plain words

Same puzzle as N-Queens: put n queens on an n × n board so that no two attack each other. This time, return only how many different boards are possible.

in n = 4

out 2

The two boards from N-Queens.

in n = 1

out 1

1 ≤ n ≤ 9

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBacktracking with constraint pruning Bitmask as a set

Counting means you can drop the board completely and just count leaves. The three "attacked" sets also fit in three ints, so one expression gives every safe column of a row: full & ~(cols | downRight | downLeft).

solutions

From brute force to optimal

The N-Queens search with cols, diag and anti boolean arrays — but return 1 at a full board and add the results.

row == n → return 1.
For each col: skip if attacked.
Mark, count += place(row + 1), unmark.
Return count.

timeO(n!)

Row r has at most n − r safe columns, so at most n! placements; each attack test is O(1).

spaceO(n)

Three boolean arrays of size ≤ 2n and recursion depth n. No board at all.

java

1class Solution {2    public int totalNQueens(int n) {3        return place(0, n, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);4    }5 6    /** Counts the boards that can be completed from `row` down. */7    private int place(int row, int n, boolean[] cols, boolean[] diag, boolean[] anti) {8        if (row == n) return 1;                         // a queen in every row: one valid board9        int count = 0;10        for (int col = 0; col < n; col++) {11            int d = row - col + n - 1, a = row + col;   // ↘ and ↙ diagonal ids12            if (cols[col] || diag[d] || anti[a]) continue;13            cols[col] = diag[d] = anti[a] = true;       // place14            count += place(row + 1, n, cols, diag, anti);15            cols[col] = diag[d] = anti[a] = false;      // remove16        }17        return count;18    }19}

Bit c of cols, downRight, downLeft means "column c of this row is attacked". The safe columns are one AND; peel them off with free & -free.

full = (1 << n) − 1; cols == full → one board found.
free = full & ~(cols | downRight | downLeft).
While free ≠ 0: bit = free & −free; free &= free − 1.
Recurse with cols | bit, (downRight | bit) << 1, (downLeft | bit) >> 1.

timeO(n!)

Same tree, but each node visits only its safe columns, and the state is three ints passed by value — nothing to undo.

spaceO(n)

Recursion depth n; each frame holds a few ints.

java

1class Solution {2    public int totalNQueens(int n) {3        return place((1 << n) - 1, 0, 0, 0);4    }5 6    /** Bit c of each mask = column c of the CURRENT row is attacked from above. */7    private int place(int full, int cols, int downRight, int downLeft) {8        if (cols == full) return 1;                             // every column used → every row has a queen9        int count = 0;10        int free = full & ~(cols | downRight | downLeft);       // safe columns in this row11        while (free != 0) {12            int bit = free & -free;                             // lowest safe column13            free &= free - 1;                                   // remove it from the to-do set14            count += place(full, cols | bit,15                    (downRight | bit) << 1,                     // ↘ attacks move one column right per row16                    (downLeft | bit) >> 1);                     // ↙ attacks move one column left per row17        }18        return count;19    }20}

in the room

How to say it in the interview

talk track

"Counting means no board strings: I return 1 at each complete placement and add up."
Show the bitmask line free = full & ~(cols | downRight | downLeft) and explain why each diagonal mask shifts by one per row.
Sanity values: n = 4 → 2, n = 8 → 92.

traps

Building every board as strings just to count them — O(n²) wasted per solution.
Forgetting & full: bits above column n − 1 look "free".
Mixing up the shift directions: ↘ attacks move one column right each row (<< 1), ↙ attacks one column left (>> 1).

what they ask next

Follow-ups

Why does each diagonal mask shift by one per row?

A queen in column c attacks column c + 1 one row down on one diagonal and column c − 1 on the other. Shifting the whole mask moves every attack at once.

Can you halve the work?

Use mirror symmetry: only try first-row columns in the left half, double the count, and add the middle column's count once when n is odd.

before you submit

Edge cases to test

n = 1 → 1.
n = 2 and n = 3 → 0.
n = 9 → 352, the maximum.

practise next