Backtracking — N-Queens II
↗ LeetCode: N-Queens II · Hard · pattern chapter →
Return count of distinct N-Queens solutions.
Example 1 — n=4 → 2Example 2 — n=1 → 1Example 3 — n=8 → 92 (the classic 8-queens count)
Constraints — 1 ≤ n ≤ 9. Brute checks C(64, 8) placements at n=8 — 4·10⁹ ops (TLE). Backtracking with cols/diag1/diag2 bitmask visits n! = 40320 valid states at n=8 — <10 ms; scales to n=15 in ~10⁶ ops.
Interview timer00:00
Approach 1 — Brute force (arrays for column + diagonals)
Intuition. Standard N-Queens: recurse row by row. At each row, try every column; check conflicts against arrays cols[], d1[], d2[]. If none conflict, mark, recurse, unmark.
int totalNQueensBrute(int n) {
boolean[] cols = new boolean[n];
boolean[] d1 = new boolean[2 * n]; // r + c
boolean[] d2 = new boolean[2 * n]; // r - c + n
int[] count = {0};
dfs(n, 0, cols, d1, d2, count);
return count[0];
}
void dfs(int n, int row, boolean[] cols, boolean[] d1, boolean[] d2, int[] count) {
if (row == n) { count[0]++; return; }
for (int c = 0; c < n; c++) {
if (cols[c] || d1[row + c] || d2[row - c + n]) continue;
cols[c] = d1[row + c] = d2[row - c + n] = true;
dfs(n, row + 1, cols, d1, d2, count);
cols[c] = d1[row + c] = d2[row - c + n] = false;
}
}Complexity — Time O(n!) worst case; Space O(n) for the arrays. Correct and standard for n ≤ 9. In an interview state this and mention bitmask is a ~50× constant-factor speedup.
Approach 2 — Bitmask backtracking (canonical)
Insight. Instead of boolean arrays, track cols, d1, d2 as int bitmasks. Available columns per row = ~(cols | d1 | d2) & fullMask. Iterate free positions via avail & -avail (isolate lowest set bit). Shift diagonals by one per row (d1 << 1, d2 >>> 1). Every check becomes a single AND — no memory writes, cache-friendly.
int totalNQueens(int n) {
int[] count = {0};
dfs(n, 0, 0, 0, 0, count);
return count[0];
}
void dfs(int n, int row, int cols, int d1, int d2, int[] count) {
if (row == n) { count[0]++; return; }
int full = (1 << n) - 1;
int avail = full & ~(cols | d1 | d2);
while (avail != 0) {
int pick = avail & -avail;
avail ^= pick;
dfs(n, row + 1, cols | pick, (d1 | pick) << 1 & full, (d2 | pick) >>> 1, count);
}
}Complexity — Time O(n!) worst but ~50× faster than Approach 1 in practice; Space O(n) recursion only. Say aloud in an interview: "the avail & -avail idiom isolates the lowest set bit — that's every 'try this column' becoming a single-cycle op."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Boolean-array backtracking | O(n!) | O(n) | Correct baseline |
| Bitmask backtracking | O(n!) | O(n) | Canonical (50× faster constant) |
When to use which
- Count only → this problem.
- Return boards → N-Queens.
- Very large n — no known polynomial algorithm.