LeetCode · #51

N-Queens Solution

Place n non-attacking queens on an n × n chessboard. Return all distinct board configurations where no two queens share a row, column, or diagonal.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #51

🏗️

Pattern

Backtracking — constraint propagation per row

Place n queens on an n × n chessboard so that no two queens attack each other (no shared row, column, or diagonal). Return all distinct solutions as board grids where 'Q' marks a queen and '.' marks an empty cell.

Example (n = 4)

 Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],
          ["..Q.","Q...","...Q",".Q.."]]
// Two valid configurations exist for n=4 

Constraints

 • 1 ≤ n ≤ 9  ← at most 352 solutions for n=9. Backtracking is feasible. • A queen attacks all cells in the same row, column, main diagonal (r-c=const),  and anti-diagonal (r+c=const). 

Section Two · Approach 1

Brute Force — Try All Placements

Generate all ways to place n queens anywhere on the n×n board (nᵃ possibilities). After placing all n queens, validate the board by checking every pair of queens for conflicts. Return configurations with no conflicts.

Why it works

Exhaustive enumeration with post-hoc validation guarantees finding every valid configuration. The correctness is trivial — all placements are tried and bad ones discarded.

Why we can do better

Problem: O(n^(n²)) placement candidates — for n=9 that is 9^81, astronomically large. We can prune early by placing one queen per row (since two queens in the same row is always invalid). This reduces placement candidates to n! immediately. Further, checking constraints with O(1) hash sets instead of scanning the board gives us O(n!) overall calls with O(1) validation per step.

Java — One-per-row backtracking (already smarter than full brute force)

 import java.util.*;
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
backtrack(board, 0, res);
return res;
    }
private void backtrack(char[][] board, int row,
List<List<String>> res) {
if (row == board.length) {
            res.add(toBoard(board)); return;
        }
for (int col = 0; col < board.length; col++) {
if (isValid(board, row, col)) { // O(n) scan — will optimize
board[row][col] = 'Q';
backtrack(board, row + 1, res);
                board[row][col] = '.';
            }
        }
    }
private boolean isValid(char[][] b, int r, int c) {
for (int i = 0; i < r; i++) { // check column and diagonals above if (b[i][c] == 'Q') return false;
if (c-(r-i) >= 0 && b[i][c-(r-i)] == 'Q') return false;
if (c+(r-i) < b.length && b[i][c+(r-i)] == 'Q') return false;
        }
return true;
    }
private List<String> toBoard(char[][] b) {
List<String> board = new ArrayList<>();
for (char[] row : b) board.add(new String(row));
return board;
    }
}

Python — One-per-row with O(n) validation

 class Solution:
def solveNQueens(self, n: int) -> list[list[str]]:
        board = [['.']*n for _ in range(n)]
        res = []
def is_valid(r: int, c: int) -> bool:
for i in range(r):
                diff = r - i
if board[i][c] == 'Q': return False if c-diff >= 0 and board[i][c-diff] == 'Q': return False if c+diff < n and board[i][c+diff] == 'Q': return False return True def bt(row: int) -> None:
if row == n:
                res.append([''.join(r) for r in board])
return for col in range(n):
if is_valid(row, col):
                    board[row][col] = 'Q' bt(row + 1)
                    board[row][col] = '.' bt(0)
return res

Metric	Value
Time	O(n! · n) — n! placements, O(n) validation each
Space	O(n²) board + O(n) call stack

Section Three · Approach 2

Backtracking with O(1) Constraint Sets

Instead of scanning the board on each placement, maintain three hash sets: cols (occupied columns), diag1 (row−col constants), and diag2 (row+col constants). Any placement is valid iff its column and both diagonal keys are absent from these sets.

💡 Mental model: Imagine a security manager assigning guards to rows in a building, one per floor. She keeps three logs on her clipboard: which columns are occupied, which "/" diagonals are blocked, and which "\" diagonals are blocked. Before placing a guard on floor n at position c, she checks all three logs in O(1). If clear, she adds c, (n−c), and (n+c) to the logs, places the guard, and moves to the next floor. On backtracking, she un-logs all three entries.

Algorithm — O(1) constraint check at each step

Place one queen per row — guarantees no two queens share a row.
cols stores used column indices — rejects same-column placements.
diag1 stores used row − col values — rejects same "\" diagonal placements.
diag2 stores used row + col values — rejects same "/" diagonal placements.
On place: add all three keys. On backtrack: remove all three keys. Set board[row][col] = 'Q' and '.' to match.
Base case: row == n → convert board to list of strings and add to result.

🎯 When to recognize this pattern:

Problems placing items on a grid with constraint propagation — "no two in the same row/column/diagonal." The key insight is using mathematical invariants (r−c, r+c) to represent diagonals as integers, enabling O(1) lookup.
This exact pattern also solves LC 52 (N-Queens II — count solutions only).

Why r−c identifies a diagonal:

All cells on the same "\" diagonal have the same r−c value. All cells on the same "/" diagonal have the same r+c value.
Storing these in sets lets you check both diagonal constraints in O(1) instead of scanning the board row by row.

Section Four · Trace

Visual Walkthrough

Trace for n = 4, finding the first valid configuration. Columns tried at each row and pruning decisions shown.

N-Queens n=4 — Backtracking Row-by-Row

Section Five · Implementation

Code — Java & Python

Java — Backtracking with O(1) constraint sets

 import java.util.*;
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
backtrack(board, 0, new HashSet<>(),
new HashSet<>(), new HashSet<>(), res);
return res;
    }
private void backtrack(char[][] board, int row,
Set<Integer> cols,
Set<Integer> diag1, // row - col constant Set<Integer> diag2, // row + col constant List<List<String>> res) {
if (row == board.length) {
List<String> solution = new ArrayList<>();
for (char[] r : board) solution.add(new String(r));
            res.add(solution);
return;
        }
for (int col = 0; col < board.length; col++) {
if (cols.contains(col) ||
                diag1.contains(row - col) ||
                diag2.contains(row + col)) continue; // O(1) check
board[row][col] = 'Q';
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
backtrack(board, row + 1, cols, diag1, diag2, res);

            board[row][col] = '.'; // backtrack
cols.remove(col);
            diag1.remove(row - col);
            diag2.remove(row + col);
        }
    }
}

Python — Backtracking with O(1) constraint sets

 class Solution:
def solveNQueens(self, n: int) -> list[list[str]]:
        cols, diag1, diag2 = set(), set(), set()
        board = [['.']*n for _ in range(n)]
        res = []
def backtrack(row: int) -> None:
if row == n:
                res.append([''.join(r) for r in board])
return for col in range(n):
if col in cols or (row-col) in diag1 or (row+col) in diag2:
continue # O(1) constraint check
board[row][col] = 'Q'
cols.add(col); diag1.add(row-col); diag2.add(row+col)
backtrack(row + 1)

                board[row][col] = '.' # backtrack
cols.discard(col)
                diag1.discard(row-col)
                diag2.discard(row+col)
backtrack(0)
return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force all positions	O(n^(n²))	O(n²)	Completely infeasible for n > 3
One-per-row + O(n) validation	O(n! · n)	O(n²)	Feasible but each check scans the board
One-per-row + O(1) sets ← optimal	O(n!)	O(n)	Constant-time constraint check — strictly better than O(n!) · n

Why does the set approach reduce the time constant?:

Both approaches make the same number of recursive calls (O(n!) in the pruned tree).
The difference is the per-call cost: scanning the board is O(n) while O(1) set lookups eliminate the inner loop.
For n=9, the reduction is significant — n=9 means removing 9× work per recursive call.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
n = 1	`n=1`	Only one cell — the single queen has no attackers. Result: `[["Q"]]`.
n = 2, n = 3	`n=2` or `n=3`	No valid placement exists. Result: `[]`. Algorithm explores and prunes all branches.
n = 4	`n=4`	Two solutions. Both are found by continuing backtracking after the first.
Diagonal key collision	negative r−c	r−c can be negative (e.g., row=0, col=3 → −3). HashSet handles negative integers correctly.
Not removing from all sets	any n	Forgetting to remove from any of the 3 sets on backtrack leaves stale constraints — future rows incorrectly see blocked positions.
n = 9 (max)	`n=9`	352 valid solutions. O(9!) ≈ 362,880 max calls. Runs well under 1ms.

⚠ Common Mistake: Using only a cols set and forgetting to track diagonals. A column check alone lets queens attack each other diagonally. You need both diagonal sets: diag1 for "\" diagonals (row−col constant) and diag2 for "/" diagonals (row+col constant). Missing either set produces configurations where queens attack diagonally.

← Back to Backtracking problems

LearningTree

LC 51 · N-Queens — Solution & Explanation | DSA Guide