Problem Statement
Place N queens on an N x N chessboard such that:
- No two queens attack each other.
- Queens cannot share:
- Row
- Column
- Diagonal
Return all possible valid board configurations.
Brute Force Intuition
Try placing queens in every possible cell.
After placing all queens, check whether the board is valid.
Most configurations are invalid, making brute force extremely expensive.
Complexity
- Time Complexity: O(N^N)
- Space Complexity: O(N²)
Moving Towards the Optimal Approach
Instead of placing queens randomly:
Place one queen per column.
For each column:
Try every row.
Before placing a queen:
Check if the position is safe.
If safe:
Place Queen
Recurse
Backtrack
Pattern Recognition
Whenever you see:
- Generate all valid arrangements
- Constraints while placing elements
- Chessboard problems
Think:
Backtracking + Constraint Checking
Key Observation
For each column:
Try all rows
If current cell is safe:
Place Queen
Otherwise:
Skip
Optimal Java Solution
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
solve(0, board, ans);
return ans;
}
private void solve(int col,
char[][] board,
List<List<String>> ans) {
if (col == board.length) {
List<String> temp = new ArrayList<>();
for (char[] row : board) {
temp.add(new String(row));
}
ans.add(temp);
return;
}
for (int row = 0; row < board.length; row++) {
if (isSafe(row, col, board)) {
board[row][col] = 'Q';
solve(col + 1, board, ans);
board[row][col] = '.';
}
}
}
private boolean isSafe(int row,
int col,
char[][] board) {
int r = row;
int c = col;
while (c >= 0) {
if (board[r][c] == 'Q')
return false;
c--;
}
r = row;
c = col;
while (r >= 0 && c >= 0) {
if (board[r][c] == 'Q')
return false;
r--;
c--;
}
r = row;
c = col;
while (r < board.length && c >= 0) {
if (board[r][c] == 'Q')
return false;
r++;
c--;
}
return true;
}
}
Dry Run
n = 4
Column 0 → Place Queen
Q . . .
. . . .
. . . .
. . . .
Column 1 → Try safe rows
Continue until:
. . Q .
Q . . .
. . . Q
. Q . .
Valid Solution
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N!) |
| Space Complexity | O(N²) |
Interview One-Liner
Place one queen column by column, checking whether the current position is safe. Backtrack whenever a conflict occurs.
Memory Trick
Column Wise Placement
Try Row
↓
Safe?
↓
Place Queen
↓
Recurse
↓
Backtrack