Log inSign up
hardLeetCodeNot Started

N-Queens

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 *all distinct solutions to the n-queens puzzle*. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1 · 4-Queens:

Input: n = 4
Output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown.

Example 2 · 1-Queen:

Input: n = 1
Output: [["Q"]]
Explanation: Single queen on 1x1 board.

Constraints:

  • 1 <= n <= 9

What You'll Learn

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

  • Understand row-by-row decomposition to eliminate row conflicts by design.
  • Master O(1) diagonal indexing mathematical formulas (r - c + n - 1 and r + c).
  • Implement ultra-fast bitwise manipulation N-Queens search.

Pattern Recognition Trigger

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

Signals to Look For:

  • Place N non-attacking items on an N x N grid
  • Each row and each column must contain exactly 1 queen
  • Two diagonal attack lines for every cell (r-c and r+c)

Algorithmic Decision Tree:

  • Recurse row-by-row solve(row).
  • Track occupied columns and diagonals using arrays or bitmasks: col[c], diag1[r - c + n - 1], diag2[r + c].
  • If all three are false: mark true, place Q, recurse row + 1, and unmark false.

Connected Patterns:

N-Queens IISudoku SolverKnight's Tour

1. Board Traversal with O(N) Safety Check Function

Intuition

For each row, iterate col from 0 to n - 1. Check safety with helper function isSafe(row, col) that scans vertically up, diagonally up-left, and diagonally up-right. If safe, place Q and recurse.

When to apply: Intuitive baseline without auxiliary lookup arrays.

Algorithm

  1. In isSafe(row, col):
  2. - Check column: iterate i from 0 to row - 1, if board[i][col] == 'Q', return false.
  3. - Check up-left: i = row-1, j = col-1 while >= 0, if board[i][j] == 'Q', return false.
  4. - Check up-right: i = row-1, j = col+1 while i >= 0, j < n, if board[i][j] == 'Q', return false.
  5. - Return true.
  6. In solve(row): iterate cols, check isSafe, recurse row + 1, backtrack.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 bool isSafe(int row, int col, int n, const vector<string>& board) {
9 // Check column upward
10 for (int i = 0; i < row; i++) {
11 if (board[i][col] == 'Q') return false;
12 }
13
14 // Check top-left diagonal
15 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
16 if (board[i][j] == 'Q') return false;
17 }
18
19 // Check top-right diagonal
20 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
21 if (board[i][j] == 'Q') return false;
22 }
23
24 return true;
25 }
26
27 void solve(int row, int n, vector<string>& board, vector<vector<string>>& result) {
28 if (row == n) {
29 result.push_back(board);
30 return;
31 }
32
33 for (int col = 0; col < n; col++) {
34 if (isSafe(row, col, n, board)) {
35 board[row][col] = 'Q';
36 solve(row + 1, n, board, result);
37 board[row][col] = '.'; // backtrack
38 }
39 }
40 }
41
42public:
43 vector<vector<string>> solveNQueens(int n) {
44 vector<vector<string>> result;
45 vector<string> board(n, string(n, '.'));
46 solve(0, n, board, result);
47 return result;
48 }
49};
50
51int main() {
52 Solution sol;
53 auto res = sol.solveNQueens(4);
54 for (const auto& b : res) {
55 for (const string& row : b) cout << row << endl;
56 cout << "---" << endl;
57 }
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(N! * N) — There are N! placements explored, each performing an O(N) safety check.
  • Space complexity: O(N^2) — Board of size N x N.

2. Diagonal Hash Array Lookup Backtracking

Intuition

Every cell (r, c) belongs to column c, main diagonal r - c + n - 1, and anti-diagonal r + c. Storing occupancy in 3 boolean arrays allows testing safety in O(1) time without scanning the board.

When to apply: The standard interview approach balancing simplicity and O(1) lookups.

Algorithm

  1. Initialize cols (size n), diag1 (size 2n-1), diag2 (size 2n-1) to false.
  2. In solve(row):
  3. - If row == n, save board copy to result.
  4. - For col from 0 to n - 1:
  5. - If !cols[col] && !diag1[row - col + n - 1] && !diag2[row + col]:
  6. - Mark all 3 as true.
  7. - board[row][col] = 'Q'.
  8. - Recurse solve(row + 1).
  9. - Unmark all 3 to false, reset board[row][col] = '.'.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 void solve(int row, int n, vector<string>& board,
9 vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2,
10 vector<vector<string>>& result) {
11 if (row == n) {
12 result.push_back(board);
13 return;
14 }
15
16 for (int col = 0; col < n; col++) {
17 int d1 = row - col + n - 1;
18 int d2 = row + col;
19
20 if (!cols[col] && !diag1[d1] && !diag2[d2]) {
21 cols[col] = diag1[d1] = diag2[d2] = true;
22 board[row][col] = 'Q';
23
24 solve(row + 1, n, board, cols, diag1, diag2, result);
25
26 board[row][col] = '.';
27 cols[col] = diag1[d1] = diag2[d2] = false; // backtrack
28 }
29 }
30 }
31
32public:
33 vector<vector<string>> solveNQueens(int n) {
34 vector<vector<string>> result;
35 vector<string> board(n, string(n, '.'));
36 vector<bool> cols(n, false);
37 vector<bool> diag1(2 * n - 1, false);
38 vector<bool> diag2(2 * n - 1, false);
39
40 solve(0, n, board, cols, diag1, diag2, result);
41 return result;
42 }
43};
44
45int main() {
46 Solution sol;
47 auto res = sol.solveNQueens(4);
48 for (const auto& b : res) {
49 for (const string& row : b) cout << row << endl;
50 cout << "---" << endl;
51 }
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(N!) — Safety check takes O(1) instead of O(N), bringing total time strictly to O(N!).
  • Space complexity: O(N) — Uses 3 boolean arrays of total size O(N).

3. Bitmask Register Backtracking (Optimal)

Intuition

Bitwise integers store attacked columns and diagonals. Available positions in row = (~(cols | diags | antiDiags)) & ((1 << n) - 1). Extract lowest set bit p = available & -available in O(1) time and transition diagonals with (diags | p) << 1 and (antiDiags | p) >> 1.

When to apply: The fastest, competitive-programming gold standard for N-Queens.

Algorithm

  1. In solve(row, cols, diags, antiDiags):
  2. - If row == n, construct board and add to result.
  3. - Available bits = (~(cols | diags | antiDiags)) & ((1 << n) - 1).
  4. - While available != 0:
  5. - p = available & -available (extract lowest bit).
  6. - col = countTrailingZeros(p).
  7. - Place queen at (row, col).
  8. - Recurse with cols | p, (diags | p) << 1, (antiDiags | p) >> 1.
  9. - Remove lowest bit: available &= available - 1.

4-Queens Placement Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Row 0: Try col 1
Visual state
Values and pointers at this exact step
matrix
c0
r0
(0, 1) Q
Variables at this step
row
0
col
1
placed
[[0,1]]
Why this step matters

Row 0: Try col 1. Place Queen at (0, 1). Occupies col 1, diag1 (0-1+3 = 2), diag2 (0+1 = 1).

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 void solve(int row, int n, int cols, int diags, int antiDiags,
9 vector<int>& queensPos, vector<vector<string>>& result) {
10 if (row == n) {
11 vector<string> board(n, string(n, '.'));
12 for (int r = 0; r < n; r++) {
13 board[r][queensPos[r]] = 'Q';
14 }
15 result.push_back(board);
16 return;
17 }
18
19 int available = (~(cols | diags | antiDiags)) & ((1 << n) - 1);
20 while (available) {
21 int p = available & -available; // Lowest set bit
22 int col = __builtin_ctz(p);
23
24 queensPos[row] = col;
25 solve(row + 1, n, cols | p, (diags | p) << 1, (antiDiags | p) >> 1, queensPos, result);
26
27 available &= available - 1; // Clear lowest set bit
28 }
29 }
30
31public:
32 vector<vector<string>> solveNQueens(int n) {
33 vector<vector<string>> result;
34 vector<int> queensPos(n, 0);
35 solve(0, n, 0, 0, 0, queensPos, result);
36 return result;
37 }
38};
39
40int main() {
41 Solution sol;
42 auto res = sol.solveNQueens(4);
43 for (const auto& b : res) {
44 for (const string& row : b) cout << row << endl;
45 cout << "---" << endl;
46 }
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N!) — Bitwise operations compute all valid positions simultaneously in a single CPU cycle.
  • Space complexity: O(N) — Recursion depth is N.

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 O(N) CheckO(N! * N)O(N^2)Scan board upwards to verify safety.Directional board scanning
2.Diagonal Hash Array LookupO(N!)O(N)O(1) safety checks with cols, diag1, and diag2 arrays.N! search complexity
3.Bitmask Register BacktrackingOptimalO(N!)O(N)Bitwise shifts and bit register operations for parallel position calculation.Output board string creation

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting the + n - 1 offset for diag1 (resulting in negative array index errors).

Pitfall 2:

Forgetting to backtrack all 3 lookup arrays / bitmasks.

Crucial Edge Cases to Validate:

  • n = 1: Single queen [[Q]].
  • n = 2, 3: No valid placement exists -> returns [].
  • n = 9: Maximum constraint (352 distinct solutions generated in ~10ms).

Interview Tips & Best Practices

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

  1. Explain the three conflict invariants: row constraint (solved by row recursion), column constraint (cols[c]), and diagonal constraints (r-c and r+c).
  2. Mention bitmask acceleration as an optional optimization.

Quick Comprehension Check

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

1.Why does diagonal 1 use the formula row - col + n - 1?

2.How many total solutions exist for the 4-Queens problem?

Back to DSA Sheet