N-Queens — Solution

Problem

Place N queens on an N×N chessboard so that no two queens threaten each other — no two queens can share the same row, column, or diagonal. Return every distinct board configuration that satisfies this constraint.

For N = 4, there are exactly two solutions:

• Input: n = 4
• Output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
• Explanation: In each board, every queen is on a unique row, column, and diagonal.

A counter-example: placing queens at (0,0) and (1,1) fails because both cells lie on the same main diagonal (row - col = 0 for both).

Intuition

Because we must place exactly one queen per row, we can iterate row by row and only choose which column to place the queen in. This reduces the problem to tracking three constraints per placement: which columns are occupied, which main diagonals are occupied (row - col is constant along a "" diagonal), and which anti-diagonals are occupied (row + col is constant along a "/" diagonal). When all three sets clear for a candidate column, we place the queen, recurse to the next row, and undo the placement when backtracking.

Solution — Backtracking

Try every column in each row. Skip any column that conflicts with an already-placed queen via a column check or either diagonal check. When all N rows are filled without conflict, record the board.

1. Maintain three sets: occupied columns, occupied main-diagonal keys (row - col), occupied anti-diagonal keys (row + col).
2. For the current row, iterate over each column from 0 to N-1.
3. If all three checks pass, place the queen (add to sets, record the column choice).
4. Recurse to the next row.
5. After returning, remove the queen from all three sets (backtrack).
6. When row == N, convert the column-per-row record into board strings and save.

1def solveNQueens(n: int) -> list[list[str]]:
2    results = []
3    queen_cols = []        # queen_cols[row] = column where queen sits in that row
4    occupied_cols = set()
5    occupied_diag = set()  # row - col is constant on a "\" diagonal
6    occupied_anti = set()  # row + col is constant on a "/" diagonal
7
8    def backtrack(row: int) -> None:
9        if row == n:
10            board = [
11                "." * col + "Q" + "." * (n - col - 1)
12                for col in queen_cols
13            ]
14            results.append(board)
15            return
16
17        for col in range(n):
18            if col in occupied_cols:
19                continue
20            if (row - col) in occupied_diag:
21                continue
22            if (row + col) in occupied_anti:
23                continue
24
25            queen_cols.append(col)
26            occupied_cols.add(col)
27            occupied_diag.add(row - col)
28            occupied_anti.add(row + col)
29
30            backtrack(row + 1)
31
32            queen_cols.pop()
33            occupied_cols.remove(col)
34            occupied_diag.remove(row - col)
35            occupied_anti.remove(row + col)
36
37    backtrack(0)
38    return results

Time: O(n!) — each row eliminates at least one column from consideration, so the search tree has at most n × (n-1) × (n-2) × … branches.

Space: O(n) — the recursion stack goes n levels deep, and each of the three sets holds at most n entries at any time (not counting the output).

Complexity Summary

Common Mistakes

• Checking rows explicitly — placing one queen per row in the outer loop already guarantees no two queens share a row; adding a row-conflict check is redundant and signals a misunderstanding of the structure.
• Swapping the diagonal keys — row - col tracks "" diagonals and row + col tracks "/" diagonals; swapping them still prunes some cases by coincidence, making the bug hard to spot on small inputs.
• Forgetting to remove from all three sets on backtrack — leaving a stale entry in even one set permanently blocks valid columns in future rows, causing the answer count to come out too low.
• Off-by-one when building the board string — the queen is at index col, so the left padding is col dots and the right padding is n - col - 1 dots; using n - col produces a string of length n + 1.
• Starting the recursion at row 1 instead of row 0 — skipping row 0 means the first queen is never placed, producing an empty result.

Related Problems

• N-Queens II — identical setup, but only returns the count of valid configurations instead of the boards themselves
• Sudoku Solver — backtracking on a 2D grid with multiple constraint types; same choose/explore/unchoose loop
• Permutations — backtracking to enumerate all orderings; the column-assignment step here is structurally a permutation with extra pruning
• Combination Sum II — backtracking with pruning to avoid duplicates; shows the same undo pattern
• Palindrome Partitioning — backtracking over a string; good contrast since the constraint check differs but the recursion skeleton is identical