N-Queens Problem (Backtracking)
The N-Queens Problem places N chess queens on an N x N board so no two attack each other, solved via backtracking with O(1) column and diagonal bitmask pruning.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
N-Queens Problem (Backtracking)
The N-Queens Problem asks how to place $N$ queens on an $N \times N$ chessboard so that no two queens share the same row, column, or diagonal. Placing one queen per row and tracking attacked columns and diagonals with 3 bitmasks (cols, diag1, diag2) prunes invalid branches in $O(1)$ per cell!
At a Glance
| Property | Value |
| :--- | :---: |
| Time Complexity | $O(N!)$ worst case (heavily pruned in practice) |
| Auxiliary Space | $O(N)$ recursion stack |
| Bitmask Pruning | cols, diag1 (r - c), diag2 (r + c) shift in $O(1)$! |
---
Practice Problems
Intermediate
1. Count All Valid N-Queens Solutions (Bitmask Backtracking, LeetCode 52)
Return the exact number of distinct valid placements for an $N \times N$ board.
Approach: At each row, available columns are avail = fullMask & ~(cols | d1 | d2). Extract the lowest set bit bit = avail & -avail and recurse with (d1 | bit) << 1 and (d2 | bit) >> 1!
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
int countNQueens(int n) {
int full = (1 << n) - 1, total = 0;
auto dfs = [&](auto& self, int cols, int d1, int d2) -> void {
if (cols == full) { ++total; return; }
int avail = full & ~(cols | d1 | d2);
while (avail) {
int bit = avail & -avail;
avail -= bit;
self(self, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
}
};
dfs(dfs, 0, 0, 0);
return total;
}
int main() {
std::cout << countNQueens(4) << " " << countNQueens(8) << "\n"; // 2 92
return 0;
}
</details>
---
Related Algorithms
- Sudoku Solver — constraint-pruned backtracking on a $9 \times 9$ grid.
- Subsets Generation — foundational backtracking recursion tree.