Log inSign up
hardLeetCodeNot Started

N-Queens II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

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 · 4-Queens Count:

Input: n = 4
Output: 2
Explanation: There are 2 distinct solutions to the 4-queens puzzle.

Example 2 · 1-Queen Count:

Input: n = 1
Output: 1
Explanation: Single valid configuration on a 1x1 board.

Constraints:

  • 1 <= n <= 9

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master high-performance bitwise backtracking with bitshift propagation.
  • Understand how removing string formatting transforms backtracking performance.
  • Derive the exact number of solutions for small N (N=1..9).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Count total valid configurations without needing full board strings
  • Exact N-Queens constraints (non-attacking queens on N x N grid)
  • Bitmask optimization fits perfectly in a single integer for N <= 9

Algorithmic Decision Tree:

  • Maintain bit registers: cols, diags, antiDiags.
  • Extract free positions using bitwise NOT and bitwise AND with mask (1 << n) - 1.
  • Traverse set bits using p = available & -available and bit clear available &= available - 1.

Connected Patterns:

N-QueensSudoku SolverMatchsticks to Square

1. Board Traversal with Upward Safety Checking

Intuition

Place Q on an N x N boolean board, checking up, up-left, and up-right in O(N) time for every placement.

When to apply: Baseline comparison with full board simulation.

Algorithm

  1. Initialize N x N board.
  2. In solve(row):
  3. - If row == n, count++, return.
  4. - For each col: if isSafe(row, col), place queen, recurse row + 1, backtrack.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 bool isSafe(int row, int col, int n, const vector<vector<bool>>& board) {
8 for (int i = 0; i < row; i++) if (board[i][col]) return false;
9 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) if (board[i][j]) return false;
10 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) if (board[i][j]) return false;
11 return true;
12 }
13
14 void solve(int row, int n, vector<vector<bool>>& board, int& count) {
15 if (row == n) {
16 count++;
17 return;
18 }
19
20 for (int col = 0; col < n; col++) {
21 if (isSafe(row, col, n, board)) {
22 board[row][col] = true;
23 solve(row + 1, n, board, count);
24 board[row][col] = false;
25 }
26 }
27 }
28
29public:
30 int totalNQueens(int n) {
31 vector<vector<bool>> board(n, vector<bool>(n, false));
32 int count = 0;
33 solve(0, n, board, count);
34 return count;
35 }
36};
37
38int main() {
39 Solution sol;
40 cout << sol.totalNQueens(4) << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N! * N) — Explores N! states with an O(N) check per step.
  • Space complexity: O(N^2) — Board array takes O(N2) memory.

2. Diagonal Boolean Array Hashing

Intuition

Maintain boolean arrays cols[n], diag1[2n-1], and diag2[2n-1]. A cell is safe if none of the 3 arrays is true.

When to apply: When implementing clear O(1) lookups without bit manipulation.

Algorithm

  1. Initialize boolean arrays cols, diag1, diag2.
  2. In solve(row):
  3. - If row == n, return 1.
  4. - For each col from 0 to n - 1:
  5. - If free in all 3 arrays, mark true, recurse solve(row + 1), unmark.
  6. - Return total count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 int solve(int row, int n, vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2) {
8 if (row == n) return 1;
9
10 int count = 0;
11 for (int col = 0; col < n; col++) {
12 int d1 = row - col + n - 1;
13 int d2 = row + col;
14
15 if (!cols[col] && !diag1[d1] && !diag2[d2]) {
16 cols[col] = diag1[d1] = diag2[d2] = true;
17 count += solve(row + 1, n, cols, diag1, diag2);
18 cols[col] = diag1[d1] = diag2[d2] = false; // backtrack
19 }
20 }
21 return count;
22 }
23
24public:
25 int totalNQueens(int n) {
26 vector<bool> cols(n, false);
27 vector<bool> diag1(2 * n - 1, false);
28 vector<bool> diag2(2 * n - 1, false);
29 return solve(0, n, cols, diag1, diag2);
30 }
31};
32
33int main() {
34 Solution sol;
35 cout << sol.totalNQueens(4) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N!) — Safety checks run in O(1) time.
  • Space complexity: O(N) — Uses 3 boolean arrays of size O(N).

3. Bitmask Register Backtracking (Optimal)

Intuition

Using bitwise operations, all free positions in a row are calculated simultaneously: available = (~(cols | diags | antiDiags)) & ((1 << n) - 1). When traversing rows, diagonals shift: (diags | p) << 1 and (antiDiags | p) >> 1.

When to apply: The optimal, high-performance counting algorithm for N-Queens.

Algorithm

  1. In solve(row, cols, diags, antiDiags):
  2. - If row == n, return 1.
  3. - available = (~(cols | diags | antiDiags)) & ((1 << n) - 1).
  4. - While available != 0:
  5. - p = available & -available.
  6. - count += solve(row + 1, cols | p, (diags | p) << 1, (antiDiags | p) >> 1).
  7. - available &= available - 1.
  8. - Return count.

N-Queens Solution Counting Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Row 0: Available bits: 0b1111 (cols 0, 1, 2, 3)
Visual state
Values and pointers at this exact step
tree
Row 0
Placed col 1

Node order shown; add connections to display explicit tree edges.

Variables at this step
row
0
cols
0010
diags
0100
antiDiags
0001
Why this step matters

Row 0: Available bits: 0b1111 (cols 0, 1, 2, 3). Pick col 1 (p = 0b0010).

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6 int solve(int row, int n, int cols, int diags, int antiDiags) {
7 if (row == n) return 1;
8
9 int count = 0;
10 int available = (~(cols | diags | antiDiags)) & ((1 << n) - 1);
11
12 while (available) {
13 int p = available & -available; // Extract lowest bit
14 count += solve(row + 1, n, cols | p, (diags | p) << 1, (antiDiags | p) >> 1);
15 available &= available - 1; // Clear lowest bit
16 }
17
18 return count;
19 }
20
21public:
22 int totalNQueens(int n) {
23 return solve(0, n, 0, 0, 0);
24 }
25};
26
27int main() {
28 Solution sol;
29 cout << sol.totalNQueens(4) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N!) — Bitwise instructions run in single CPU clock cycles.
  • Space complexity: O(N) — Only N recursion frames on call stack with zero heap memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Board Traversal with Upward Safety CheckO(N! * N)O(N^2)Full board array simulation.Directional board scanning
2.Diagonal Boolean Array HashingO(N!)O(N)O(1) safety checks with 3 boolean arrays.N! search space
3.Bitmask Register BacktrackingOptimalO(N!)O(N)Bitwise shifts and bit register operations.N! search space

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting the bitmask bounding mask ((1 << n) - 1) when inverting bits with ~.

Pitfall 2:

Not shifting diags and antiDiags on recursive call.

Crucial Edge Cases to Validate:

  • n = 1: returns 1.
  • n = 2, 3: returns 0.
  • n = 4: returns 2.
  • n = 8: returns 92.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight how bitwise operations calculate all available slots in a single CPU cycle.
  2. Mention known solution counts (N=4: 2, N=8: 92) to verify code outputs.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we shift diags with << 1 and antiDiags with >> 1 when moving to row + 1?

2.What is the count of distinct solutions for n = 8 (standard chessboard)?

Back to DSA Sheet