The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example 1:
Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 9The N-Queens II problem asks you to count how many distinct ways you can place n queens on an n x n chessboard so that no two queens attack each other. The most effective strategy is backtracking, where you place queens row by row while ensuring that each placement does not conflict with previous ones.
To efficiently check validity, maintain structures that track used columns, main diagonals (row - col), and anti-diagonals (row + col). When exploring each row, try every column that is not under attack. If the placement is safe, continue recursively to the next row; otherwise, skip it and try another position.
This pruning significantly reduces the search space compared to brute force. Some optimized implementations also use bitmasks for faster checks and lower memory overhead. The backtracking tree can grow rapidly, but pruning ensures only valid partial configurations are explored.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with column and diagonal tracking | O(N!) | O(N) |
| Backtracking with bitmask optimization | O(N!) | O(N) |
NeetCode
This approach involves using backtracking to explore all possible ways of placing queens on the board. We maintain three sets to keep track of which columns and diagonals are already occupied by queens, ensuring no two queens threaten each other.
Time Complexity: O(n!), where n is the number of queens. Each queen has n options initially, and it decreases with increasing constraints.
Space Complexity: O(n) for the call stack and additional space for tracking columns and diagonals.
1#include <vector>
2#include <unordered_set>
3
4class Solution {
5public:
6 int totalNQueens(int n) {
7 std::unordered_set<int> columns, diag1, diag2;
8 return backtrack(0, n, columns, diag1, diag2);
9 }
10
11private:
12 int backtrack(int row, int n, std::unordered_set<int>& columns, std::unordered_set<int>& diag1, std::unordered_set<int>& diag2) {
13 if (row == n) return 1;
14 int count = 0;
for (int col = 0; col < n; ++col) {
if (columns.count(col) || diag1.count(row + col) || diag2.count(row - col)) continue;
columns.insert(col);
diag1.insert(row + col);
diag2.insert(row - col);
count += backtrack(row + 1, n, columns, diag1, diag2);
columns.erase(col);
diag1.erase(row + col);
diag2.erase(row - col);
}
return count;
}
};The C++ solution utilizes `std::unordered_set` for columns and diagonals to check the safety of placing the queens. Through recursive backtracking, it explores each row, placing a queen only if no set has the conflicting column or diagonal.
This approach leverages bitmasking to store state information about occupied columns and diagonals. By using integer variables as bit masks, we can efficiently check and update occupation states, which is particularly useful for handling small fixed-size constraints like n <= 9.
Time Complexity: O(n!). Recursive full exploration, though bitwise operations are computationally efficient.
Space Complexity: O(n) due to recursion depth and bitmask integers.
1 public int TotalNQueens(int n) {
return Solve(n, 0, 0, 0, 0);
}
private int Solve(int n, int row, int columns, int diag1, int diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; col++) {
int colMask = 1 << col;
if ((columns & colMask) == 0 && (diag1 & (1 << (row + col))) == 0 && (diag2 & (1 << (row - col + n - 1))) == 0) {
count += Solve(n, row + 1, columns | colMask, diag1 | (1 << (row + col)), diag2 | (1 << (row - col + n - 1)));
}
}
return count;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, N-Queens style problems are frequently used in coding interviews at FAANG and other tech companies. They test understanding of backtracking, recursion, pruning techniques, and optimization strategies.
The optimal approach uses backtracking while tracking columns, main diagonals, and anti-diagonals to quickly detect conflicts. This pruning prevents exploring invalid board states and significantly reduces the search space.
Common implementations use sets or boolean arrays to track occupied columns and diagonals. More optimized solutions use bitmasks, which allow constant-time checks and are especially efficient for larger board sizes.
The original N-Queens problem typically asks you to return all valid board configurations. N-Queens II instead asks for the total count of valid solutions, which simplifies output but still requires exploring valid placements.
This C# version employs bitwise operations similarly, adeptly balancing checks on column and diagonal occupation with quick updates achieved through bit shifts.