51. N-Queens — DSA Atlas

HardBacktrackingDFS backtracking, one queen per row, O(1) attack checksRow-by-row placement with diagonal conflict sets

N-Queens

Place n queens on an n x n chessboard so that no two attack each other (no shared row, column, or diagonal). Return all distinct board configurations, each drawn as a list of strings using 'Q' for a queen and '.' for empty.

Open official problem prompt ↗

In plain English

Enumerate every arrangement of n mutually non-attacking queens, rendered as string boards.

Picture it like this

Seating n guests who each refuse to share a row, column, or diagonal sightline; you seat one per row and back out the instant the next row has no free seat.

Example

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Why: These are the only two ways to place 4 non-attacking queens; in each, every row, column, and both diagonal directions hold at most one queen.

Constraints

1 <= n <= 9

Pattern lesson

See the pattern, then code

Row-by-row placement with diagonal conflict sets

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Placing one queen per row removes row conflicts automatically. A cell (r,c) shares a main diagonal with all cells of equal r-c and an anti-diagonal with equal r+c, so three sets (columns, r-c, r+c) give O(1) safety checks.

New words, made simpleKnow these before the algorithm

Main diagonal (r-c): All cells on the same top-left-to-bottom-right line share the value row minus column.
Anti-diagonal (r+c): All cells on the same top-right-to-bottom-left line share the value row plus column.
Row-by-row search: Fixing one queen per row so row conflicts are impossible and depth equals the row index.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check all placed queens each time

Correct but each safety test is linear in placed queens.

For a candidate cell, loop over already-placed queens testing column and diagonal clashes.

Time O(n!) with O(n) per checkSpace O(n)

Best choiceThree conflict sets

Constant-time legality and cheap backtracking make it the clean standard.

Maintain sets of used columns, r-c, and r+c for O(1) checks and O(1) undo.

Time O(n!)Space O(n)

The rule we keep true

Invariant

At recursion depth r, exactly one queen sits in each of rows 0..r-1 and no two of them attack each other.

Why this is correct

Reasoning

One queen per row eliminates row attacks by construction; the column, r-c, and r+c sets capture the only remaining attack lines, so a placement passing all three is safe against every earlier queen. Exhaustively trying every safe column in every row reaches all valid boards, and undoing keeps state exact.

The algorithm in three movesSay these aloud before coding

1Recurse row by row starting at row 0

row 0: place at col 1 -> cols={1}, diag(r-c)={-1}, anti(r+c)={1}

2For each column in the row, skip if its column, r-c, or r+c is already occupied

row 1: cols 0,1,2 blocked -> col 3 safe

3Place the queen, add to the three sets, mark the board

row==4 reached -> snapshot board

4Recurse to the next row; when row == n, snapshot the board into the result

5Undo the placement and try the next column

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readcolumns 0-3

2 · Askwhich columns are safe?

3 · Update stateall sets empty

4 · Resulttry col 1 (leads to a solution): cols={1}, diag={-1}, anti={1}

Key takeaway

Row 0 of a 4-queens solution with the queen in column 1; later rows must avoid that column and both diagonals.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-6State setup
res holds boards; three sets track columns and both diagonals; board is the working grid.
2
Lines 7-9Base case
When r reaches n every row has a queen, so join each row into a string and store.
3
Lines 10-12Safety check
Skip a column if it or either diagonal key is already occupied.
4
Lines 13-19Place and revert
Add to all sets and the board, recurse to the next row, then remove everything to try the next column.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n = 1 -> a single board ["Q"]
n = 2 and n = 3 -> no solutions, empty list
Larger n where early rows fan out into many partial dead ends

Common beginner mistakes

Using r+c for the main diagonal or r-c for the anti-diagonal (swapped keys)
Forgetting to remove a queen from all three sets on undo
Iterating over all cells instead of one queen per row, which reintroduces row conflicts and blows up the search

Check your understanding

Why do cells on one diagonal share a constant r-c (or r+c)?

PyPython 3 · solution.py

Optimal

1class Solution:2    def solveNQueens(self, n: int) -> list[list[str]]:3        res: list[list[str]] = []4        cols: set[int] = set()5        diag: set[int] = set()6        anti: set[int] = set()7        board = [['.'] * n for _ in range(n)]8        def backtrack(r: int) -> None:9            if r == n:10                res.append([''.join(row) for row in board])11                return12            for c in range(n):13                if c in cols or (r - c) in diag or (r + c) in anti:14                    continue15                cols.add(c); diag.add(r - c); anti.add(r + c)16                board[r][c] = 'Q'17                backtrack(r + 1)18                board[r][c] = '.'19                cols.discard(c); diag.discard(r - c); anti.discard(r + c)20        backtrack(0)21        return res

Time complexityO(n!) in the worst case, since each row has fewer valid columns as queens accumulateOptimized

Space complexityO(n) for the three sets and recursion, plus O(n^2) per stored boardExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleApple

N-Queens

N-Queens

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking