N-Queens
Problem Statement
Place n queens on an n x n chessboard so that no two queens attack each other. Return all distinct board configurations. A queen attacks along its row, column, and both diagonals.
Input
A single integer n, the board size and the number of queens to place.
Output
A list of boards. Each board has n strings of length n, using Q for a queen and . for an empty cell.
Constraints
- •
1 <= n <= 9
Examples
Example 1
n = 4
[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]Example 2
n = 1
[[Q]]Learning Objectives
- Recognise one-queen-per-row as the natural state compression for N-Queens.
- Track attacked columns and both diagonal families in O(1) per safety check.
- Use diagonal indices **r + c** and **r - c + (n - 1)** to avoid scanning the board.
- Build immutable board strings only when a full valid placement is reached.
Intuition
Pattern Recognition
N-Queens is board placement backtracking. We construct a configuration row by row, placing exactly one queen in each row. That removes row conflicts by design, so each recursive frame only chooses a column for the current row.
The important insight is that safety can be checked without scanning the board. A queen attacks its column, its down-right diagonal where r - c is constant, and its down-left diagonal where r + c is constant. Use r + c directly for one diagonal array, and use r - c + (n - 1) for the other so the index is non-negative.
The template is place, validate, recurse, undo the cell. If a column or diagonal is already used, prune that column immediately. When row n is reached, every row has one safe queen, so convert the board into strings and record one solution.
Common mistakes
- ×Scanning every previous queen for each candidate instead of tracking columns and diagonals.
- ×Forgetting the **n - 1** offset for **r - c**, causing negative diagonal indices.
- ×Placing multiple queens in the same row by recursing over cells instead of rows.
- ×Adding the mutable board directly to the result instead of creating fresh strings for each solution.
Algorithm Explanation
State
Each frame carries the current row. The board records placed queens, while three boolean arrays record occupied columns, occupied r + c diagonals, and occupied r - c + (n - 1) diagonals. Since rows are processed in order, all rows before row contain exactly one safe queen.
Recursion tree
For n = 4, the root represents row 0 with four column choices. If row 0 chooses column 0, many branches die by row 2 because every column is attacked by an existing queen. After undoing that branch, row 0 chooses column 1. Then row 1 column 3, row 2 column 0, and row 3 column 2 form one complete board. The second solution appears from the symmetric root choice at row 0 column 2.
Pruning
A candidate cell (r, c) is pruned if columns[c], diagSum[r + c], or diagDiff[r - c + (n - 1)] is already true. Those checks remove attacked squares before any recursive call. The search is still factorial because each row tends to choose among remaining columns, but diagonal pruning cuts most permutations early.
Algorithm
- Create an n x n board filled with ..
- Create boolean arrays for columns, r + c diagonals, and r - c + (n - 1) diagonals.
- Recurse on row = 0.
- For each column in the current row, compute the two diagonal indices.
- If any constraint is already used, skip the cell.
- Place Q, mark the column and diagonals, and recurse to row + 1.
- Undo the placement and marks before trying the next column.
- When row == n, convert the board to strings and add it to the answer.
Solutions
Solution: Row-by-row DFS with column and diagonal sets
Place one queen per row and maintain three constraint arrays. This makes each safety test O(1): the candidate is legal exactly when its column and both diagonal indices are unused.
Step-by-step
- Fill a character board with . and create the three boolean constraint arrays.
- Start DFS at row 0.
- For every column, compute sumDiagonal = row + col and diffDiagonal = row - col + n - 1.
- Skip the column if any corresponding constraint is already true.
- Place Q, mark all three constraints, and recurse to the next row.
- After recursion, reset the cell to . and unmark the constraints.
- When every row has a queen, copy the board into a list of strings.
O(n!)
O(n^2)
Rows are fixed and columns cannot repeat, so the search is bounded by permutations of columns. The board uses O(n^2) space, while constraints and recursion use O(n). Output storage is excluded.
Java implementation
Dry Run
Sample input
n = 4. Track row-by-row placements until the first valid board is recorded.
| step | cell | choice | action (place/undo) | state |
|---|---|---|---|---|
| 1 | row 0 col 0 | try first column | place Q | columns 0, sum 0, diff 3 marked |
| 2 | row 1 col 2 | candidate seems open | place Q | columns 0 and 2 marked |
| 3 | row 2 | no safe column | undo row 1 col 2 | backtrack to row 1 |
| 4 | row 1 col 3 | next safe candidate | place Q | continue branch from row 0 col 0 |
| 5 | row 2 col 1 | only possible column | place Q | row 3 has no safe column |
| 6 | row 0 col 0 | branch exhausted | undo row 0 col 0 | try next root column |
| 7 | row 0 col 1 | new root choice | place Q | columns 1, sum 1, diff 2 marked |
| 8 | row 1 col 3 | safe | place Q | queens at (0,1) and (1,3) |
| 9 | row 2 col 0 | safe | place Q | three rows filled |
| 10 | row 3 col 2 | safe | place Q | record .Q.. | ...Q | Q... | ..Q. |
The first root branch fails because later rows have no legal square. Undoing all marks returns the board to empty, allowing the successful branch starting at row 0 column 1.
Interview Tips
Start by saying one queen per row. That single design choice removes row conflicts and turns the problem into choosing a safe column at each depth. Then write the two diagonal formulas clearly: r + c and r - c + (n - 1). Interviewers often look for that non-negative offset because it proves you understand the board geometry.
Likely follow-ups
- How would you count the number of solutions without storing the boards?
- How would you optimize the constraint tracking with bit masks?
- How would the solution change if some cells were blocked?
- How would you return only the first valid board instead of all boards?
Similar Problems
Key Takeaways
- Placing one queen per row removes an entire class of conflicts from the state.
- Columns and diagonals can be tracked with boolean arrays for O(1) safety checks.
- Use **r - c + (n - 1)** to map difference diagonals into non-negative indices.
- Build board strings only at complete valid leaves.