N-Queens II
Problem Description
The n-queens puzzle asks you to place n queens on an n x n chessboard so that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Examples
Example 1:Input: n = 4 Output: 2
Input: n = 1 Output: 1
Constraints
1 ≤ n ≤ 9
Same Algorithm, Skip the Board Construction
N-Queens II is the same problem as N-Queens, minus the requirement to return the board configurations. Only the count matters. That means you can strip out the board construction entirely and just increment a counter at the leaf node.
This is also a good problem to introduce bitmask optimization: use integer bitmasks instead of sets for column, diagonal, and anti-diagonal tracking. Bit operations are faster than set operations, and the code is more compact once you understand the pattern.
Solution 1: Backtracking with Sets (Straightforward)
import java.util.*;
class Solution {
private int count = 0;
public int totalNQueens(int n) {
backtrack(n, 0, new HashSet<>(), new HashSet<>(), new HashSet<>());
return count;
}
private void backtrack(int n, int row,
Set<Integer> cols, Set<Integer> diag, Set<Integer> antiDiag) {
if (row == n) {
count++;
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diag.contains(row - col) || antiDiag.contains(row + col)) {
continue;
}
cols.add(col); diag.add(row - col); antiDiag.add(row + col);
backtrack(n, row + 1, cols, diag, antiDiag);
cols.remove(col); diag.remove(row - col); antiDiag.remove(row + col);
}
}
}class Solution:
def totalNQueens(self, n: int) -> int:
count = 0
cols, diag, anti_diag = set(), set(), set()
def backtrack(row: int):
nonlocal count
if row == n:
count += 1
return
for col in range(n):
if col in cols or (row - col) in diag or (row + col) in anti_diag:
continue
cols.add(col); diag.add(row - col); anti_diag.add(row + col)
backtrack(row + 1)
cols.discard(col); diag.discard(row - col); anti_diag.discard(row + col)
backtrack(0)
return count#include <unordered_set>
class Solution {
int count = 0;
public:
int totalNQueens(int n) {
std::unordered_set<int> cols, diag, antiDiag;
backtrack(n, 0, cols, diag, antiDiag);
return count;
}
private:
void backtrack(int n, int row,
std::unordered_set<int>& cols, std::unordered_set<int>& diag,
std::unordered_set<int>& antiDiag) {
if (row == n) { count++; return; }
for (int col = 0; col < n; col++) {
if (cols.count(col) || diag.count(row - col) || antiDiag.count(row + col)) continue;
cols.insert(col); diag.insert(row - col); antiDiag.insert(row + col);
backtrack(n, row + 1, cols, diag, antiDiag);
cols.erase(col); diag.erase(row - col); antiDiag.erase(row + col);
}
}
};Complexity Analysis:
- Time Complexity: O(n!). Same as N-Queens; board construction is simply skipped.
- Space Complexity: O(n) for the sets and recursion stack.
Where it breaks: the constraint caps at n = 9, which has 352 solutions and runs in microseconds. At n = 15, you’d be exploring millions of paths, which starts to feel slow.
Solution 2: Bitmask Backtracking (Faster in Practice)
Use integer bitmasks to represent occupied columns, diagonals, and anti-diagonals. Bit shifts propagate the diagonal constraints automatically as the row increases.
class Solution {
public int totalNQueens(int n) {
return backtrack(n, 0, 0, 0, 0);
}
private int backtrack(int n, int row, int cols, int diag, int antiDiag) {
if (row == n) return 1;
int count = 0;
int available = ((1 << n) - 1) & ~(cols | diag | antiDiag);
while (available != 0) {
int bit = available & (-available); // lowest set bit
available &= (available - 1); // clear it
count += backtrack(n, row + 1,
cols | bit,
(diag | bit) << 1,
(antiDiag | bit) >> 1);
}
return count;
}
}class Solution:
def totalNQueens(self, n: int) -> int:
def backtrack(row: int, cols: int, diag: int, anti: int) -> int:
if row == n:
return 1
count = 0
available = ((1 << n) - 1) & ~(cols | diag | anti)
while available:
bit = available & (-available) # lowest set bit
available &= (available - 1)
count += backtrack(row + 1, cols | bit, (diag | bit) << 1, (anti | bit) >> 1)
return count
return backtrack(0, 0, 0, 0)class Solution {
public:
int totalNQueens(int n) {
return backtrack(n, 0, 0, 0, 0);
}
private:
int backtrack(int n, int row, int cols, int diag, int antiDiag) {
if (row == n) return 1;
int count = 0;
int available = ((1 << n) - 1) & ~(cols | diag | antiDiag);
while (available) {
int bit = available & (-available); // lowest set bit
available &= (available - 1);
count += backtrack(n, row + 1, cols | bit, (diag | bit) << 1, (antiDiag | bit) >> 1);
}
return count;
}
};Complexity Analysis:
- Time Complexity: O(n!). Same asymptotic bound, but bitmask operations run faster in practice than set operations.
- Space Complexity: O(n) recursion stack. No extra data structures.
Where it breaks: the bitmask approach shifts diagonals by 1 each row, which naturally propagates the constraint. The shift direction matters: << 1 for one diagonal type, >> 1 for the other. Swapping these gives wrong results that are hard to debug.
Common Mistakes
- Returning 2 for
n=4from memory but forgetting the algorithm check. Always verify:n=1returns 1,n=2andn=3return 0,n=4returns 2. - Using a class-level mutable counter without resetting it between calls. Use a return value instead.
Frequently Asked Questions
What’s the difference between N-Queens and N-Queens II? N-Queens returns all board configurations. N-Queens II returns only the count. The backtracking algorithm is identical; you just skip building the board string.
When would you use the bitmask version over the set version? In competitive programming or performance-critical contexts. For an interview, the set version is clearer to explain and implement. Both are correct.