N-Queens

Problem in Plain English

Place n queens on an n by n board so no two share a row, column, or diagonal, and return every distinct board of Q and dot strings. Layouts that break any attack rule are excluded.

Problem Statement

The n-queens puzzle asks for placements of n queens on an n x n board where no two queens share a row, column, or diagonal.

Given n, return all distinct valid placements in any order.

Write each board as n strings of length n, using Q for a queen and . for an empty square.

Constraints

1 <= n <= 9

Examples

Example 1

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

The column sequences [1, 3, 0, 2] and [2, 0, 3, 1] use distinct columns and have no pair with equal row and column gaps. Every other sequence violates an attack rule. Reflection produces a different board, so both layouts belong in the answer.

Example 2

Input: n = 1
Output: [["Q"]]

A lone queen on a 1 by 1 board attacks nothing.

Example 3

Input: n = 3
Output: []

Starting in the middle column attacks every cell in the next row. Starting in an outer column forces the opposite outer column in row 1, leaving no safe cell in row 2. Thus every branch fails even though the board has three rows.

Intuition

With n queens and n rows, a safe board must put exactly one queen in each row. Represent a board by its chosen columns: [1, 3, 0, 2] means queens at (0, 1), (1, 3), (2, 0), and (3, 2). Distinct columns prevent vertical attacks. Two queens share a diagonal exactly when their row gap equals their column gap; equivalently, their row-plus-column or row-minus-column keys match. Backtracking explores a column choice, finishes its descendants, then removes its attack marks so the next choice starts from the same prefix.

Approaches

Guess Then Validate

Solution Details

Reveal Guess Then Validate: intuition, complexity, and code

Intuition

Guess every assignment of distinct columns to rows, then validate diagonal attacks only after all rows are filled. Column uniqueness reduces the candidates to permutations, but a diagonal clash in row 1 still allows every remaining permutation to be generated before rejection. Comparing this delayed check with immediate attack-set pruning shows why checking a partial choice matters.

Step-by-Step Logic

Keep one column per row and an array of used columns. For each row, try every currently unused column; in Example 1, the first full sequence is [0, 1, 2, 3].
Only when all n rows are filled, compare every pair of queens. Reject a candidate when the absolute row difference equals the absolute column difference; [0, 1, 2, 3] fails at rows 0 and 1.
If all pairs pass, convert each chosen column into a fresh dot string with one Q. Example 1 accepts [1, 3, 0, 2], producing [.Q.., ...Q, Q..., ..Q.].
After exploring a chosen column, clear its used mark before trying the next sibling. Previous row choices remain fixed until their own recursive call returns.
Continue through all permutations, rather than stopping after the first solution. Of the 24 candidates for n = 4, only [1, 3, 0, 2] and [2, 0, 3, 1] pass; return their two boards.

Why It Works

Every valid board has exactly one queen in each row and each column, so its column sequence is a permutation. The recursion tries every unused column at every row and therefore generates each permutation exactly once. At a complete candidate, checking every pair rejects it if and only if their row gap equals their column gap, the definition of a shared diagonal. Rows and columns are already distinct, so every accepted board is safe and every safe board is accepted. Building new row strings and a new board list at each successful leaf prevents later search choices from changing earlier answers.

Dry Run

Guess Then Validate: variable states at each step
Full columns after descending rows 0 to 3	First diagonal conflict / checks	Answers after leaf	Backtrack
[0, 1, 2, 3]	rows 0, 1: gap 1	0	clear row 3 column 3; resume unused choices
[0, 1, 3, 2]	rows 0, 1: gap 1	0	clear row 3 column 2; resume unused choices
[0, 2, 1, 3]	rows 0, 3: gap 3	0	clear row 3 column 3; resume unused choices
[0, 2, 3, 1]	rows 1, 2: gap 1	0	clear row 3 column 1; resume unused choices
[0, 3, 1, 2]	rows 2, 3: gap 1	0	clear row 3 column 2; resume unused choices
[0, 3, 2, 1]	rows 0, 2: gap 2	0	clear row 3 column 1; resume unused choices
[1, 0, 2, 3]	rows 0, 1: gap 1	0	clear row 3 column 3; resume unused choices
[1, 0, 3, 2]	rows 0, 1: gap 1	0	clear row 3 column 2; resume unused choices
[1, 2, 0, 3]	rows 0, 1: gap 1	0	clear row 3 column 3; resume unused choices
[1, 2, 3, 0]	rows 0, 1: gap 1	0	clear row 3 column 0; resume unused choices
[1, 3, 0, 2]	all 6 pairs pass; append fresh board	1	clear row 3 column 2; resume unused choices
[1, 3, 2, 0]	rows 1, 2: gap 1	1	clear row 3 column 0; resume unused choices
[2, 0, 1, 3]	rows 1, 2: gap 1	1	clear row 3 column 3; resume unused choices
[2, 0, 3, 1]	all 6 pairs pass; append fresh board	2	clear row 3 column 1; resume unused choices
[2, 1, 0, 3]	rows 0, 1: gap 1	2	clear row 3 column 3; resume unused choices
[2, 1, 3, 0]	rows 0, 1: gap 1	2	clear row 3 column 0; resume unused choices
[2, 3, 0, 1]	rows 0, 1: gap 1	2	clear row 3 column 1; resume unused choices
[2, 3, 1, 0]	rows 0, 1: gap 1	2	clear row 3 column 0; resume unused choices
[3, 0, 1, 2]	rows 0, 2: gap 2	2	clear row 3 column 2; resume unused choices
[3, 0, 2, 1]	rows 2, 3: gap 1	2	clear row 3 column 1; resume unused choices
[3, 1, 0, 2]	rows 1, 2: gap 1	2	clear row 3 column 2; resume unused choices
[3, 1, 2, 0]	rows 0, 3: gap 3	2	clear row 3 column 0; resume unused choices
[3, 2, 0, 1]	rows 0, 1: gap 1	2	clear row 3 column 1; resume unused choices
[3, 2, 1, 0]	rows 0, 1: gap 1	2	clear row 3 column 0; resume unused choices
All 24 permutations exhausted	22 rejected, 2 accepted	[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]	return both boards

Complexity Analysis

Time Complexity

O(n^2 n!)

Space Complexity

O(n + S n^2)

Let S be the number of returned boards. There are n! complete column permutations, each with at most n(n - 1)/2 pair checks. The recursion has O(n!) prefixes and scans n candidate columns per prefix; leaf checks and O(S n^2) board construction fit the displayed O(n^2 n!) upper bound because S is at most n!. Early conflicts can make execution faster. Columns, used marks and recursion require O(n) auxiliary space. Each returned board stores n strings of length n, so output storage is O(S n^2); constructing one board uses O(n^2) temporary space only at a successful leaf, where the output bound already covers it.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public List<List<String>> solveNQueens(int n) {5        List<List<String>> res = new ArrayList<>();6        dfs(0, n, new int[n], new boolean[n], res);7        return res;8    }9
10    private void dfs(int r, int n, int[] cols, boolean[] used, List<List<String>> res) {11        if (r == n) {12            if (!clashes(cols, n)) res.add(build(cols, n));13            return;14        }15        for (int c = 0; c < n; c++) {16            if (used[c]) continue;17            // Enforce distinct columns now; defer diagonal checks to the complete board.18            cols[r] = c;19            used[c] = true;20            dfs(r + 1, n, cols, used, res);21            used[c] = false; // Restore the parent prefix before the next sibling.22        }23    }24
25    private boolean clashes(int[] cols, int n) {26        // Equal row and column gaps identify either diagonal slope.27        for (int i = 0; i < n; i++) {28            for (int j = i + 1; j < n; j++) {29                if (cols[i] == cols[j] || Math.abs(i - j) == Math.abs(cols[i] - cols[j])) {30                    return true;31                }32            }33        }34        return false;35    }36
37    private List<String> build(int[] cols, int n) {38        List<String> board = new ArrayList<>();39        for (int r = 0; r < n; r++) {40            char[] row = new char[n];41            Arrays.fill(row, '.');42            row[cols[r]] = 'Q';43            board.add(new String(row));44        }45        return board;46    }47}

Hints

Hint 1

Each row needs exactly one queen, so the whole puzzle is choosing one column per row.

Hint 2

A new queen at row r and column c is safe exactly when no earlier queen shares c, r + c, or r - c.

Hint 3

Track those three values in sets while descending row by row, and emit the board only when all n rows are filled.

Edge Cases

n = 1 accepts the single cell at once and returns [["Q"]].
n = 2 and n = 3 have no valid layout at all, so the answer is an empty list.
n = 9 fans out widely, which is why pruning dead rows early matters far more than board-copy speed.

Common Mistakes and Interview Tips

Checking only columns and rows while forgetting diagonals, which accepts boards where queens snipe along a slope.
Mixing up the two diagonal keys, such as using row + col for both, which blocks safe cells and frees attacked ones.
Removing a queen from the board but leaving its column or diagonal marked, which silently kills every later branch.
Saving the shared columns array as an answer makes later choices overwrite earlier solutions. Build a fresh board at every successful leaf.
Returning after the first solution misses other placements, including the reflected board for n = 4.
Interview tip: derive both diagonal keys from two coordinates, then explain why all three attack marks must be removed after recursion.

Key Takeaway

Constraint puzzles shrink when each choice is validated against the choices above it: track exactly what past decisions forbid and prune the moment a row has nothing legal left.