273. N-Queens
🔗 LeetCode Problem: 51. N-Queens
📊 Difficulty: Hard
🏷️ Topics: Array, Backtracking
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:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle
Example 2:
Input: n = 1
Output: [["Q"]]
Constraints:
- 1 <= n <= 9
🌟 ELI5: The Simple Idea!
Think of placing queens one row at a time, just like you would by hand:
Strategy (How a human would solve it):
1. Start with empty board
2. Place queen in row 0 at some column
3. Move to row 1
4. Try each column in row 1
- Look up: Any queen in same column? ✗
- Look diagonally up-left: Any queen? ✗
- Look diagonally up-right: Any queen? ✗
- If all safe → Place queen and move to next row
5. If stuck (no safe column) → Go back and move previous queen
6. Continue until all n queens placed!
Key Insight: Place one queen per row
- No need to check same row (automatically safe!)
- Only check upward (previous rows)
Visual Example - How YOU would solve it:
4×4 board, placing queens row by row:
Step 1: Place queen in row 0, column 1
. Q . . ← Start here
. . . .
. . . .
. . . .
Step 2: Try row 1
. Q . .
X . . ? ← Column 0 blocked by diagonal
← Column 1 blocked by same column
← Column 2 blocked by diagonal
← Try column 3!
. Q . .
. . . Q ← Safe! Place here
. . . .
. . . .
Step 3: Try row 2
. Q . .
. . . Q
? . . X ← Check each position...
Eventually find: Q at column 0
. Q . .
. . . Q
Q . . . ← Safe!
. . . .
Step 4: Try row 3
. Q . .
. . . Q
Q . . .
. . Q . ← Found at column 2! ✓
One solution found!
🎨 Visual Understanding
Queen Attack Patterns - Simple View
A queen at (row, col) attacks:
1. SAME COLUMN (straight down):
. Q . .
. | . .
. | . .
. X . . ← Attacked
2. DIAGONAL DOWN-LEFT (\):
. Q . .
. . \ .
. . . \
X . . . ← Attacked
3. DIAGONAL DOWN-RIGHT (/):
. Q . .
. . / .
. / . .
. . . X ← Attacked
Since we place row by row (top to bottom),
we ONLY need to check UPWARD!
The Natural Checking Logic
When placing queen at (currentRow, col):
CHECK 1: Same column - Look straight UP
for (row = currentRow - 1; row >= 0; row--) {
if (board[row][col] == 'Q') return false;
}
CHECK 2: Diagonal up-left - Look UP-LEFT
for (row = currentRow - 1, c = col - 1;
row >= 0 && c >= 0;
row--, c--) {
if (board[row][c] == 'Q') return false;
}
CHECK 3: Diagonal up-right - Look UP-RIGHT
for (row = currentRow - 1, c = col + 1;
row >= 0 && c < n;
row--, c++) {
if (board[row][c] == 'Q') return false;
}
If all three checks pass → Safe to place!
This is EXACTLY how you'd check by hand! 👀
🎨 How Tracking Works - Visual Step by Step
Complete State Tracking for n=4 (Intuitive Way)
Goal: Place 4 queens on 4×4 board
Initial board:
. . . .
. . . .
. . . .
. . . .
═══════════════════════════════════════════════════════════════
ROW 0: Place first queen
═══════════════════════════════════════════════════════════════
Try column 0:
No queens above (first row!)
→ Safe! Place queen
Board:
Q . . . ← Queen at (0,0)
. . . .
. . . .
. . . .
Move to row 1 →
═══════════════════════════════════════════════════════════════
ROW 1: Place second queen
═══════════════════════════════════════════════════════════════
Current board:
Q . . .
? . . . ← Trying to place in row 1
. . . .
. . . .
Try column 0:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ Look up column 0: (0,0) has Q ✗ │
│ BLOCKED! │
└─────────────────────────────────────────┘
Board view:
Q . . . ← Queen here blocks column 0
↓
X . . . ← Can't place here
Skip!
Try column 1:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ Look up column 1: (0,1) = '.' ✓ │
│ │
│ CHECK 2: Diagonal up-left? │
│ Position (0,0): Has Q ✗ │
│ BLOCKED! │
└─────────────────────────────────────────┘
Board view:
Q . . . ← Queen here blocks diagonal
\
X . . ← Can't place here
Skip!
Try column 2:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ Look up column 2: (0,2) = '.' ✓ │
│ │
│ CHECK 2: Diagonal up-left? │
│ Position (0,1): '.' ✓ │
│ │
│ CHECK 3: Diagonal up-right? │
│ Position (0,3): '.' ✓ │
│ │
│ ALL CHECKS PASS! ✓ │
└─────────────────────────────────────────┘
Board:
Q . . .
. . Q . ← Queen at (1,2) - Safe!
. . . .
. . . .
Move to row 2 →
═══════════════════════════════════════════════════════════════
ROW 2: Place third queen
═══════════════════════════════════════════════════════════════
Current board:
Q . . .
. . Q .
? . . . ← Trying to place in row 2
. . . .
Try column 0:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ Row 1, col 0: '.' ✓ │
│ Row 0, col 0: 'Q' ✗ │
│ BLOCKED! │
└─────────────────────────────────────────┘
Skip!
Try column 1:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ Row 1, col 1: '.' ✓ │
│ Row 0, col 1: '.' ✓ │
│ │
│ CHECK 2: Diagonal up-left? │
│ Row 1, col 0: '.' ✓ │
│ │
│ CHECK 3: Diagonal up-right? │
│ Row 1, col 2: 'Q' ✗ │
│ BLOCKED! │
└─────────────────────────────────────────┘
Board view:
Q . . .
. . Q . ← This queen blocks diagonal
/
. X . . ← Can't place here
Skip!
Try column 2:
CHECK 1: Same column?
Row 1, col 2: 'Q' ✗
BLOCKED!
Skip!
Try column 3:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ Row 1, col 3: '.' ✓ │
│ Row 0, col 3: '.' ✓ │
│ │
│ CHECK 2: Diagonal up-left? │
│ Row 1, col 2: 'Q' ✗ │
│ BLOCKED! │
└─────────────────────────────────────────┘
Skip!
ALL COLUMNS TRIED, NONE SAFE! 😱
BACKTRACK! ⬅️
═══════════════════════════════════════════════════════════════
BACKTRACK to ROW 1
═══════════════════════════════════════════════════════════════
Remove queen from (1,2):
Board:
Q . . .
. . . . ← Removed queen
. . . .
. . . .
Continue trying next column in row 1:
Try column 3:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ Row 0, col 3: '.' ✓ │
│ │
│ CHECK 2: Diagonal up-left? │
│ Row 0, col 2: '.' ✓ │
│ │
│ CHECK 3: Diagonal up-right? │
│ Out of bounds ✓ │
│ │
│ ALL CHECKS PASS! ✓ │
└─────────────────────────────────────────┘
Board:
Q . . .
. . . Q ← Queen at (1,3) - Safe!
. . . .
. . . .
Move to row 2 →
═══════════════════════════════════════════════════════════════
ROW 2: Place third queen (retry)
═══════════════════════════════════════════════════════════════
Current board:
Q . . .
. . . Q
? . . . ← Trying to place in row 2
. . . .
Try column 0:
CHECK 1: Same column?
Row 1, col 0: '.' ✓
Row 0, col 0: 'Q' ✗
BLOCKED! Skip!
Try column 1:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ All rows above: '.' ✓ │
│ │
│ CHECK 2: Diagonal up-left? │
│ Row 1, col 0: '.' ✓ │
│ Row 0, col −1: Out of bounds ✓ │
│ │
│ CHECK 3: Diagonal up-right? │
│ Row 1, col 2: '.' ✓ │
│ Row 0, col 3: '.' ✓ │
│ │
│ ALL CHECKS PASS! ✓ │
└─────────────────────────────────────────┘
Board:
Q . . .
. . . Q
. Q . . ← Queen at (2,1) - Safe!
. . . .
Move to row 3 →
═══════════════════════════════════════════════════════════════
ROW 3: Place fourth queen
═══════════════════════════════════════════════════════════════
Current board:
Q . . .
. . . Q
. Q . .
? . . . ← Trying to place in row 3
Try column 0:
CHECK 1: Same column? Has Q at (0,0) ✗
Skip!
Try column 1:
CHECK 1: Same column? Has Q at (2,1) ✗
Skip!
Try column 2:
┌─────────────────────────────────────────┐
│ CHECK 1: Same column? │
│ Row 2, col 2: '.' ✓ │
│ Row 1, col 2: '.' ✓ │
│ Row 0, col 2: '.' ✓ │
│ │
│ CHECK 2: Diagonal up-left? │
│ Row 2, col 1: 'Q' ✗ │
│ BLOCKED! │
└─────────────────────────────────────────┘
Skip!
Try column 3:
CHECK 1: Same column? Has Q at (1,3) ✗
Skip!
ALL COLUMNS TRIED, NONE SAFE! 😱
BACKTRACK! ⬅️
... (Continue backtracking and trying different positions)
Eventually find first solution:
. Q . . ← (0,1)
. . . Q ← (1,3)
Q . . . ← (2,0)
. . Q . ← (3,2)
Continue to find all solutions...
═══════════════════════════════════════════════════════════════
Final Solutions for n=4:
═══════════════════════════════════════════════════════════════
Solution 1: Solution 2:
. Q . . . . Q .
. . . Q Q . . .
Q . . . . . . Q
. . Q . . Q . .
🎯 Approach: Direct Checking (Most Intuitive) ⭐⭐⭐
The Natural Human Approach
Algorithm:
1. Place queens row by row (top to bottom)
2. For each row, try each column:
a. Check if position is safe by looking upward:
- Same column (straight up)
- Diagonal up-left (\)
- Diagonal up-right (/)
b. If safe:
- Place queen
- Recursively place queens in remaining rows
- If successful → found solution
- Else → remove queen, try next column
3. Base case: All rows filled → solution found!
Implementation
import java.util.*;
/**
* N-Queens with direct checking (most intuitive)
* Time: O(n!) - Same as optimized approach
* Space: O(n²) - Board storage
*/
class Solution {
private List<List<String>> result;
public List<List<String>> solveNQueens(int n) {
result = new ArrayList<>();
char[][] board = new char[n][n];
// Initialize board with empty cells
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}
backtrack(board, 0, n);
return result;
}
private void backtrack(char[][] board, int row, int n) {
// Base case: All queens placed successfully!
if (row == n) {
result.add(construct(board));
return;
}
// Try placing queen in each column of current row
for (int col = 0; col < n; col++) {
if (isSafe(board, row, col, n)) {
// Place queen
board[row][col] = 'Q';
// Recursively place queens in next rows
backtrack(board, row + 1, n);
// Backtrack - remove queen
board[row][col] = '.';
}
}
}
/**
* Check if placing queen at (row, col) is safe
* Only need to check upward (previous rows)
*/
private boolean isSafe(char[][] board, int row, int col, int n) {
// Check 1: Same column (straight up)
for (int r = row - 1; r >= 0; r--) {
if (board[r][col] == 'Q') {
return false; // Queen found in same column
}
}
// Check 2: Diagonal up-left (\)
for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) {
if (board[r][c] == 'Q') {
return false; // Queen found on diagonal
}
}
// Check 3: Diagonal up-right (/)
for (int r = row - 1, c = col + 1; r >= 0 && c < n; r--, c++) {
if (board[r][c] == 'Q') {
return false; // Queen found on diagonal
}
}
// All checks passed - position is safe!
return true;
}
private List<String> construct(char[][] board) {
List<String> solution = new ArrayList<>();
for (char[] row : board) {
solution.add(new String(row));
}
return solution;
}
public static void main(String[] args) {
Solution sol = new Solution();
List<List<String>> solutions = sol.solveNQueens(4);
System.out.println("Number of solutions: " + solutions.size());
for (List<String> solution : solutions) {
for (String row : solution) {
System.out.println(row);
}
System.out.println();
}
}
}
⏰ Time: O(n!) - Same as optimized approach with tracking arrays
💾 Space: O(n²) - Board storage
🎯 Approach 2: Optimized with Tracking Arrays (Advanced)
More Efficient But Requires Understanding Diagonal Math
/**
* Optimized with tracking arrays
* O(1) checking instead of O(n) loops
*/
class SolutionOptimized {
private List<List<String>> result;
private boolean[] cols; // Track columns
private boolean[] diag1; // Track \ diagonals
private boolean[] diag2; // Track / diagonals
public List<List<String>> solveNQueens(int n) {
result = new ArrayList<>();
cols = new boolean[n];
diag1 = new boolean[2 * n - 1]; // row - col + (n-1)
diag2 = new boolean[2 * n - 1]; // row + col
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}
backtrack(board, 0, n);
return result;
}
private void backtrack(char[][] board, int row, int n) {
if (row == n) {
result.add(construct(board));
return;
}
for (int col = 0; col < n; col++) {
int d1 = row - col + n - 1;
int d2 = row + col;
if (cols[col] || diag1[d1] || diag2[d2]) {
continue;
}
board[row][col] = 'Q';
cols[col] = diag1[d1] = diag2[d2] = true;
backtrack(board, row + 1, n);
board[row][col] = '.';
cols[col] = diag1[d1] = diag2[d2] = false;
}
}
private List<String> construct(char[][] board) {
List<String> solution = new ArrayList<>();
for (char[] row : board) {
solution.add(new String(row));
}
return solution;
}
}
Why this is faster: - O(1) checking vs O(n) loops - No iteration through board - Still same O(n!) overall time complexity
Why this is less intuitive: - Requires understanding diagonal formulas - Need to manage 3 separate boolean arrays - Less obvious what the code is checking - Harder to maintain and debug
When to use: - Competitive programming (slight speed advantage) - When you've already mastered the intuitive approach - Performance-critical applications with large n
🎯 Approach 3: Understanding the Diagonal Formulas (Deep Dive)
How Diagonal Tracking Works - Complete Explanation
If you want to understand the math behind Approach 2, read this section!
The Grid Layout with Coordinates
The 9×9 grid is divided into diagonals:
Col: 0 1 2 | 3 4 5 | 6 7 8
Row 0: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 1: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 2: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
----+---------+---------+---------
Row 3: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 4: [ ][ ][ ] [ ][X][ ] [ ][ ][ ] ← Example cell (4,4)
Row 5: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
----+---------+---------+---------
Row 6: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 7: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 8: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Understanding Diagonals - Two Types
There are TWO types of diagonals:
Type 1: Top-Left to Bottom-Right (\)
Diagonal value = row - col
col: 0 1 2 3 4
row 0: [0] [−1][−2][−3][−4]
row 1: [1] [0] [−1][−2][−3]
row 2: [2] [1] [0] [−1][−2]
row 3: [3] [2] [1] [0] [−1]
row 4: [4] [3] [2] [1] [0]
Pattern: Same diagonal has same (row - col) value
Example: (0,0), (1,1), (2,2), (3,3), (4,4) all have value 0
(1,0), (2,1), (3,2), (4,3) all have value 1
(0,1), (1,2), (2,3), (3,4) all have value -1
Type 2: Top-Right to Bottom-Left (/)
Diagonal value = row + col
col: 0 1 2 3 4
row 0: [0] [1] [2] [3] [4]
row 1: [1] [2] [3] [4] [5]
row 2: [2] [3] [4] [5] [6]
row 3: [3] [4] [5] [6] [7]
row 4: [4] [5] [6] [7] [8]
Pattern: Same diagonal has same (row + col) value
Example: (0,4), (1,3), (2,2), (3,1), (4,0) all have value 4
(0,3), (1,2), (2,1), (3,0) all have value 3
(1,4), (2,3), (3,2), (4,1) all have value 5
Why These Formulas Work - Visual Proof
Diagonal Type 1 (\ direction):
Move from (0,0) to (1,1) to (2,2):
(0,0): row=0, col=0 → 0−0 = 0
(1,1): row=1, col=1 → 1−1 = 0 ✓ Same diagonal!
(2,2): row=2, col=2 → 2−2 = 0 ✓ Same diagonal!
Move from (1,0) to (2,1) to (3,2):
(1,0): row=1, col=0 → 1−0 = 1
(2,1): row=2, col=1 → 2−1 = 1 ✓ Same diagonal!
(3,2): row=3, col=2 → 3−2 = 1 ✓ Same diagonal!
Visual:
[ ][ ][ ][ ]
[Q][ ][ ][ ] ← (1,0): 1−0 = 1
[ ][Q][ ][ ] ← (2,1): 2−1 = 1 (same!)
[ ][ ][Q][ ] ← (3,2): 3−2 = 1 (same!)
When moving diagonally (\):
row+1, col+1 → (row+1)−(col+1) = row−col (constant!)
Diagonal Type 2 (/ direction):
Move from (0,3) to (1,2) to (2,1):
(0,3): row=0, col=3 → 0+3 = 3
(1,2): row=1, col=2 → 1+2 = 3 ✓ Same diagonal!
(2,1): row=2, col=1 → 2+1 = 3 ✓ Same diagonal!
Move from (0,2) to (1,1) to (2,0):
(0,2): row=0, col=2 → 0+2 = 2
(1,1): row=1, col=1 → 1+1 = 2 ✓ Same diagonal!
(2,0): row=2, col=0 → 2+0 = 2 ✓ Same diagonal!
Visual:
[ ][ ][ ][Q] ← (0,3): 0+3 = 3
[ ][ ][Q][ ] ← (1,2): 1+2 = 3 (same!)
[ ][Q][ ][ ] ← (2,1): 2+1 = 3 (same!)
[Q][ ][ ][ ] ← (3,0): 3+0 = 3 (same!)
When moving diagonally (/):
row+1, col−1 → (row+1)+(col−1) = row+col (constant!)
Handling Negative Values for Diagonal 1
Problem: row − col can be negative!
(0,2): 0−2 = −2
(1,3): 1−3 = −2
Can't use negative as array index!
Solution: Add n−1 to make it positive
Formula: (row − col) + (n−1)
For n=4:
(0,2): (0−2) + 3 = 1
(1,3): (1−3) + 3 = 1 ✓
Range: 0 to 2n−2
Why n−1?
Minimum value: (0 − (n−1)) = −(n−1)
Add (n−1): −(n−1) + (n−1) = 0 ✓
Maximum value: ((n−1) − 0) = n−1
Add (n−1): (n−1) + (n−1) = 2n−2 ✓
Array size needed: 2n−1
Complete Diagonal Check Visual
For 4×4 board:
Diagonal Type 1 (\ direction):
Index = (row − col) + 3
col: 0 1 2 3
row 0: [3] [2] [1] [0]
row 1: [4] [3] [2] [1]
row 2: [5] [4] [3] [2]
row 3: [6] [5] [4] [3]
Diagonal Type 2 (/ direction):
Index = row + col
col: 0 1 2 3
row 0: [0] [1] [2] [3]
row 1: [1] [2] [3] [4]
row 2: [2] [3] [4] [5]
row 3: [3] [4] [5] [6]
Checking if position (2,1) is safe:
Column: Check cols[1] → is there a queen?
Diagonal \: Check diag1[(2−1)+3] = diag1[4] → is there a queen?
Diagonal /: Check diag2[2+1] = diag2[3] → is there a queen?
If all are false → Safe to place queen! ✓
Examples to Solidify Understanding
Example 1: Cell at (2, 1)
n = 4
Diagonal \ index:
row - col + (n-1) = 2 - 1 + 3 = 4
Diagonal / index:
row + col = 2 + 1 = 3
Cells on same \ diagonal (index 4):
(1,0): 1−0+3 = 4 ✓
(2,1): 2−1+3 = 4 ✓
(3,2): 3−2+3 = 4 ✓
Visual:
[ ][ ][ ][ ]
[Q][ ][ ][ ] ← (1,0) on diag1[4]
[ ][X][ ][ ] ← (2,1) on diag1[4]
[ ][ ][Q][ ] ← (3,2) on diag1[4]
Cells on same / diagonal (index 3):
(0,3): 0+3 = 3 ✓
(1,2): 1+2 = 3 ✓
(2,1): 2+1 = 3 ✓
(3,0): 3+0 = 3 ✓
Visual:
[ ][ ][ ][Q] ← (0,3) on diag2[3]
[ ][ ][Q][ ] ← (1,2) on diag2[3]
[ ][X][ ][ ] ← (2,1) on diag2[3]
[Q][ ][ ][ ] ← (3,0) on diag2[3]
Example 2: Cell at (0, 3)
n = 4
Diagonal \ index:
row - col + (n-1) = 0 - 3 + 3 = 0
Diagonal / index:
row + col = 0 + 3 = 3
Only cell on diag1[0]:
(0,3): 0−3+3 = 0
Cells on diag2[3]:
(0,3), (1,2), (2,1), (3,0) all sum to 3
Memory Aid for Formulas
Think of it as:
Diagonal \ (downward-right):
As you move down-right (row+1, col+1):
row - col stays CONSTANT
Add n-1 to avoid negatives
→ row - col + (n-1)
Diagonal / (downward-left):
As you move down-left (row+1, col-1):
row + col stays CONSTANT
Already positive!
→ row + col
Mnemonic:
"Minus for backslash (\), Plus for forward slash (/)"
row − col for \
row + col for /
Comparison: Direct Check vs Tracking Arrays
DIRECT CHECK (Approach 1):
Checking (row, col):
Loop up column: O(n)
Loop diagonal up-left: O(n)
Loop diagonal up-right: O(n)
Total per check: O(n)
Pros: Intuitive, easy to understand
Cons: O(n) per safety check
TRACKING ARRAYS (Approach 2):
Checking (row, col):
Check cols[col]: O(1)
Check diag1[row-col+n-1]: O(1)
Check diag2[row+col]: O(1)
Total per check: O(1)
Pros: O(1) checking
Cons: Complex formulas, less intuitive
Both have same O(n!) overall time complexity!
The difference is only in constant factors.
When to Use Each Approach
Use Direct Check (Approach 1) when:
✓ Learning the problem first time
✓ Code readability is important
✓ Need to maintain/debug easily
✓ In interviews (easier to explain)
Use Tracking Arrays (Approach 2) when:
✓ Performance optimization needed
✓ Already mastered direct approach
✓ Competitive programming
✓ Large n values
For interviews:
START with Approach 1 (direct check)
MENTION Approach 2 exists if asked about optimization
IMPLEMENT Approach 2 only if specifically requested
⚠️ Common Mistakes
Mistake 1: Checking downward instead of upward
// ❌ WRONG - Checks rows that haven't been filled yet!
for (int r = row + 1; r < n; r++) {
if (board[r][col] == 'Q') return false;
}
// ✓ CORRECT - Only check upward (already placed queens)
for (int r = row - 1; r >= 0; r--) {
if (board[r][col] == 'Q') return false;
}
Mistake 2: Checking same row
// ❌ UNNECESSARY - We place one queen per row!
for (int c = 0; c < n; c++) {
if (board[row][c] == 'Q') return false;
}
// ✓ CORRECT - Skip row check entirely
// One queen per row strategy handles this automatically
Mistake 3: Not backtracking
// ❌ WRONG - Queen stays placed even when path fails!
if (isSafe(board, row, col, n)) {
board[row][col] = 'Q';
backtrack(board, row + 1, n);
// Forgot to remove!
}
// ✓ CORRECT - Remove queen after exploring
if (isSafe(board, row, col, n)) {
board[row][col] = 'Q';
backtrack(board, row + 1, n);
board[row][col] = '.'; // Backtrack!
}
Mistake 4: Wrong diagonal direction
// ❌ WRONG - Incrementing both (goes down-right, not up-left!)
for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r++, c++) {
// This goes nowhere useful!
}
// ✓ CORRECT - Decrement both for up-left diagonal
for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) {
if (board[r][c] == 'Q') return false;
}
Mistake 5: Not checking all three directions
// ❌ WRONG - Only checks column!
private boolean isSafe(char[][] board, int row, int col, int n) {
for (int r = 0; r < row; r++) {
if (board[r][col] == 'Q') return false;
}
return true; // Forgot diagonals!
}
// ✓ CORRECT - Check all three: column, both diagonals
private boolean isSafe(char[][] board, int row, int col, int n) {
// Check column
for (int r = row - 1; r >= 0; r--) { ... }
// Check diagonal up-left
for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) { ... }
// Check diagonal up-right
for (int r = row - 1, c = col + 1; r >= 0 && c < n; r--, c++) { ... }
return true;
}
🎯 Pattern Recognition
Problem Type: Constraint Satisfaction
Core Pattern: Backtracking with Safety Checking
When to Apply:
✓ Place items with conflict rules
✓ No two items can attack/conflict
✓ Need all valid configurations
✓ Natural row-by-row or step-by-step placement
Recognition Keywords:
- "n-queens puzzle"
- "no two queens attack"
- "all distinct solutions"
- "placement on board"
Similar Problems:
- N-Queens II (LC 52) - Count solutions only
- Sudoku Solver (LC 37) - Different constraints
- Valid Sudoku (LC 36) - Just validation
Key Components:
┌────────────────────────────────────────────┐
│ One queen per row: Natural row-by-row │
│ isSafe(): Check column and both diagonals │
│ Check upward only: Queens below not placed│
│ Backtrack: Remove queen after exploring │
│ Time: O(n!), Space: O(n²) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I'll use backtracking with direct safety checking"
Step 2: "Place one queen per row, try each column"
Step 3: "Check if safe by looking upward in three directions"
Key Points to Mention:
- One queen per row (no row conflicts!)
- Check three directions upward:
1. Same column
2. Diagonal up-left
3. Diagonal up-right
- Only check upward (queens below not placed yet)
- Backtrack if no valid column found
Walk Through:
"For n=4:
Row 0: Try column 0
No queens above → Safe! Place it
Row 1: Try each column
Column 0: Check up → Queen at (0,0) ✗
Column 1: Check up-left → Queen at (0,0) ✗
Column 2: All checks pass! Place it
Row 2: Try each column
None safe → Backtrack to row 1
Row 1: Try column 3
All checks pass! Place it
Continue until solution found..."
Why This is Intuitive:
"This is exactly how you'd solve it by hand:
- Look at the board
- Check if position is safe by looking up
- If safe, place queen and continue
- If stuck, go back and try different position
No complex formulas, just direct checking!"
Complexity:
"Time: O(n!)
Row 0: n choices
Row 1: fewer valid choices due to constraints
Continues reducing → factorial behavior
Space: O(n²) for board
O(n) for recursion
Total: O(n²)"
If Asked About Optimization:
"Yes, we can use boolean arrays to track columns and
diagonals for O(1) checking instead of O(n) loops.
But the current approach is more intuitive and
maintainable, with same time complexity."
📝 Quick Revision Notes
🎯 Core Concept:
N-Queens: Place n queens on n×n board with no attacks. Use backtracking placing one queen per row. For each row, try each column. Check if safe by looking upward only: (1) same column (straight up), (2) diagonal up-left (row--, col--), (3) diagonal up-right (row--, col++). If safe, place queen and recurse. If stuck, backtrack (remove queen, try next column). This is exactly how you'd solve by hand!
⚡ Quick Implementation:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<String>> solveNQueens(int n) {
// return backtracking(n);
// just in case below approach. Above should be enough.
return backtrackingWithCaching(n);
}
private List<List<String>> backtrackingWithCaching(int n) {
char[][] board = new char[n][n];
List<List<String>> res = new ArrayList<>();
// step 1: fill with all '.'s
for (char[] row : board) {
Arrays.fill(row, '.');
}
// step 2: create tracking / visited arrays
// Ideally, we need to maintain 2D visited array. But with below, we can reduce
// to 1D arrays.
// concept:
// step 2a: cols is straight forward
// step 2b: diagonal from top left to bottom right
// (0, 0) to (n-1, n-1)
// For these cells, (row-col) is always a constant
// Create an array and update index which has value (row-col) as visited
// if row and col are 0 and n-1, it will become -ve. Hence, doube the size
// step 2c: diagonal from top right to bottom left
// (0, n-1) to (n-1, 0)
// For these cells, (row+col) is always a constant
// Create an array and update index which has value (row+col) as visited
boolean[] cols = new boolean[n];
boolean[] diag1 = new boolean[2 * n - 1];
boolean[] diag2 = new boolean[2 * n - 1];
backtrackingWithCachingUtil(board, 0, cols, diag1, diag2, res);
return res;
}
private void backtrackingWithCachingUtil(char[][] board, int row, boolean[] cols, boolean[] diag1, boolean[] diag2,
List<List<String>> res) {
// step 9: base case - result achieved
if (row == board.length) {
res.add(new ArrayList<>(getCurrBoard(board)));
return;
}
// step 3: try all columns of the incoming row index
for (int col = 0; col < board.length; col++) {
// step 4: check if placing queen at (row, col) is valid through tracking arrays
int r = row - col + (board.length - 1);
int c = row + col;
if (cols[col] || diag1[r] || diag2[c]) {
continue;
}
// step 6: place the queen in the valid cell and mark it as visited
board[row][col] = 'Q';
cols[col] = diag1[r] = diag2[c] = true;
// step 7: proceed for placing the queen in the next row
backtrackingWithCachingUtil(board, row + 1, cols, diag1, diag2, res);
// step 8: backtrack
board[row][col] = '.';
cols[col] = diag1[r] = diag2[c] = false;
}
}
private List<List<String>> backtracking(int n) {
char[][] board = new char[n][n];
List<List<String>> res = new ArrayList<>();
// step 1: fill with all '.'s
for (char[] row : board) {
Arrays.fill(row, '.');
}
// step 2: start with row 0 and try all columns in it
backtrackingUtil(board, 0, res);
return res;
}
private void backtrackingUtil(char[][] board, int row, List<List<String>> res) {
// step 9: base case - result achieved
if (row == board.length) {
res.add(new ArrayList<>(getCurrBoard(board)));
return;
}
// step 3: try all columns of the incoming row index
for (int col = 0; col < board.length; col++) {
// step 4: check if placing queen at (row, col) is valid
if (isValid(board, row, col)) {
// step 6: place the queen in the valid cell
board[row][col] = 'Q';
// step 7: proceed for placing the queen in the next row
// GOTCHA: this is diff from Sudoko where we immediately return if we find
// solution in this step. But, here, its asked to return all solutions.
backtrackingUtil(board, row + 1, res);
// step 8: backtrack
board[row][col] = '.';
}
}
}
private ArrayList<String> getCurrBoard(char[][] board) {
ArrayList<String> curr = new ArrayList<>();
for (char[] row : board) {
curr.add(new String(row));
}
return curr;
}
private boolean isValid(char[][] board, int row, int col) {
// step 6a: check all above filled rows of this col
for (int r = 0; r < row; r++) {
if (board[r][col] == 'Q') {
return false;
}
}
// step 6b: no need to check all cols of the same row as we are
// filling 1 row and then only proceeding to next row
// step 6c: check all cells diagonally from top left corner to bottom right (\)
// its like (row-1, col-1), (row-2, col-2) till (0,0)
int r = row - 1;
int c = col - 1;
while (r >= 0 && c >= 0) {
if (board[r][c] == 'Q') {
return false;
}
r--;
c--;
}
// step 6d: check all cells diagonally from top right to bottom left (/)
// its like (row-1, col+1), (row-2, col+2) and so on till boundaries
r = row - 1;
c = col + 1;
while (r >= 0 && c < board[0].length) {
if (board[r][c] == 'Q') {
return false;
}
r--;
c++;
}
return true;
}
public static void main(String[] args) {
Solution s = new Solution();
// [[.Q.., ...Q, Q..., ..Q.], [..Q., Q..., ...Q, .Q..]]
System.out.println(s.solveNQueens(4));
}
}
🔑 Key Insights:
- Most Intuitive: Direct checking, just like solving by hand
- One Per Row: Eliminates row conflict checking
- Check Upward Only: Queens below not placed yet
- Three Checks: Column up, diagonal up-left, diagonal up-right
- Simple Loops: No complex formulas or tracking arrays
- Easy to Maintain: Code is self-explanatory
- Time: O(n!), Space: O(n²) ✓
🎪 Memory Aid:
"One per row, check three up: column, left, right!"
"Look up like you would by hand!" ✨
⚠️ The Three Upward Checks:
When placing queen at (row, col):
Check 1: Column (straight up)
Start: row - 1, col
Move: row--, col (same)
Stop: row >= 0
Visual:
. Q . . ← Checking (0,1)
. | . .
. ? . . ← Placing at (2,1)
Check 2: Diagonal up-left (\)
Start: row - 1, col - 1
Move: row--, col--
Stop: row >= 0 && col >= 0
Visual:
Q . . . ← Checking (0,0)
\
\ . .
. . ? . ← Placing at (2,2)
Check 3: Diagonal up-right (/)
Start: row - 1, col + 1
Move: row--, col++
Stop: row >= 0 && col < n
Visual:
. . . Q ← Checking (0,3)
/
/ . .
. ? . . ← Placing at (2,1)
Why only upward?
We place row by row from top to bottom.
Queens below current row haven't been placed yet!
No need to check downward.
🧪 Edge Cases
Case 1: n=1
Input: n = 1
Output: [["Q"]]
Only one queen, trivial
Case 2: n=2
Input: n = 2
Output: []
No solution possible!
Case 3: n=3
Input: n = 3
Output: []
No solution possible!
Case 4: n=4
Input: n = 4
Output: 2 solutions
[".Q..","...Q","Q...","..Q."]
["..Q.","Q...","...Q",".Q.."]
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(n!)
Why factorial?
Row 0: Try n columns
Row 1: At most n−2 valid (constraints eliminate some)
Row 2: Even fewer valid
...
Pattern: n × (n−2) × (n−4) × ... ≈ n!
isSafe() checking:
Each check: O(n) worst case
But doesn't affect overall O(n!) complexity
Total operations: O(n! × n) but simplified to O(n!)
Space Complexity: O(n²)
Board storage: n × n = O(n²)
Recursion stack: O(n)
One level per row
Total: O(n²) auxiliary space
📚 Related Problems
Same Core Pattern: - N-Queens II (LC 52) - Count solutions (same logic) - Sudoku Solver (LC 37) - Different constraints - Word Search (LC 79) - Path constraints
🎉 Why This Approach is Better for Learning
Intuitive Approach (Direct Checking):
✓ Natural - Matches how humans solve
✓ Readable - Easy to understand code
✓ Maintainable - Changes are straightforward
✓ Debuggable - Can visualize what's happening
✓ Extendable - Easy to add new constraints
✓ Interview-friendly - Easier to explain
Optimized Approach (Tracking Arrays):
✓ Slightly faster (O(1) vs O(n) checking)
✗ Less intuitive - Complex formulas
✗ Harder to maintain - Three arrays to sync
✗ Harder to debug - Less obvious what's wrong
For interviews and real-world code:
START with intuitive approach!
Mention optimization exists if asked.
Happy practicing! 🎯
Note: This direct checking approach is how you'd actually solve N-Queens by hand! It's much more intuitive than tracking arrays with complex diagonal formulas. The time complexity is the same (O(n!)) because the pruning eliminates most branches regardless of checking method. In interviews, this approach shows clear thinking and is easier to code correctly under pressure. Master this first, then learn the optimization if needed! 💪✨