AntInLoop

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