N-Queens

Problem

Place n chess queens on an n x n board so that no two queens attack each other — no two share a row, a column, or a diagonal. Return all distinct valid placements. Each placement is rendered as a list of n strings of length n, where 'Q' marks a queen and '.' an empty square. Solutions may be returned in any order.

Examples

• n = 4 → two solutions:

. Q . .      . . Q .
. . . Q      Q . . .
Q . . .      . . . Q
. . Q .      . Q . .

Each is the other’s mirror image; no smaller-than-4 board other than n=1 admits any solution.

• n = 1 → [["Q"]] — a lone queen attacks nothing.
• n = 2 → [] — on a 2×2 board every pair of squares shares a row, column, or diagonal.

Constraints

• 1 <= n <= 9 — solution counts stay small (352 for n=9), but the raw search space is enormous, so pruning row-by-row is the expected shape.

Think about it first

TL;DR

Row-by-row backtracking with O(1) conflict checks via column/diagonal sets — O(n!) time, O(n) space beyond the output.

Approach 1 — Brute force: try every column permutation

Since a valid placement has exactly one queen per row and per column, every candidate is a permutation perm where the queen of row i sits in column perm position i. Generate all n! permutations and keep those with no diagonal conflict: queens in rows i and j clash diagonally iff abs(perm[i] - perm[j]) == i - j (for j < i).

from itertools import permutations


def solveNQueens(n: int) -> list[list[str]]:
    res: list[list[str]] = []
    for perm in permutations(range(n)):
        ok = all(
            abs(perm[i] - perm[j]) != i - j
            for i in range(n)
            for j in range(i)
        )
        if ok:
            board = [
                "." * col + "Q" + "." * (n - col - 1) for col in perm
            ]
            res.append(board)
    return res

Complexity: O(n! · n²) time (n! permutations, O(n²) pair check each), O(n) space beyond the output.

At n = 9 that is 362 880 permutations with a full 36-pair scan each. It is feasible only because the constraint stops at 9. The flaw is that it validates complete placements instead of abandoning a partial placement after its first conflict. (Choosing any n of the n² squares is worse still: C(81, 9) ≈ 2.6 × 10^11 candidates.)

Approach 2 — Backtracking with column and diagonal sets

Prune at the earliest possible moment. Place queens row by row; before committing row r to column c, an O(1) test tells whether any earlier queen attacks it, because all cells of one ↘ diagonal share the value r - c and all cells of one ↙ anti-diagonal share r + c. Keep three hash sets — used columns, used r - c, used r + c — so a partial placement is cut off as soon as it becomes invalid, never extended. This is standard backtracking: depth-first extension of a partial solution with undo on failure.

def solveNQueens(n: int) -> list[list[str]]:
    res: list[list[str]] = []
    cols: set[int] = set()
    diag: set[int] = set()   # r - c, the "\" diagonals
    anti: set[int] = set()   # r + c, the "/" diagonals
    placement: list[int] = []  # placement of row r = its queen's column

    def backtrack(r: int) -> None:
        if r == n:
            board = [
                "." * c + "Q" + "." * (n - c - 1) for c in placement
            ]
            res.append(board)
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue
            cols.add(c)
            diag.add(r - c)
            anti.add(r + c)
            placement.append(c)
            backtrack(r + 1)
            placement.pop()
            cols.discard(c)
            diag.discard(r - c)
            anti.discard(r + c)

    backtrack(0)
    return res

Walkthrough on n = 4:

1. Row 0 tries column 0. Sets: cols {0}, diag {0}, anti {0}.
2. Row 1: c=0 (column), c=1 (diag: 1-1=0) blocked; c=2 free → place. anti gains 3.
3. Row 2: c=1 blocked (anti 2+1=3), c=3 blocked (diag 2-3=-1, same as 1-2) — every column fails → backtrack row 1 to c=3.
4. Row 2 now: c=1 free → place. Row 3: c=2 blocked (diag 3-2=1 = 2-1), everything else blocked → dead end. Unwind all of row 0 = 0.
5. Row 0 tries c=1: row 1 → c=3, row 2 → c=0, row 3 → c=2: r == 4, render [1,3,0,2] → .Q.. / ...Q / Q... / ..Q.
6. Symmetric search from row 0 c=2 yields [2,0,3,1]; c=3 yields nothing new. Two boards total.

The search tree for n = 4, keeping only the branches that survive the row-1 pruning:

flowchart TD
    R["row 0"] --> A["col 0"]
    R --> B["col 1"]
    R --> C["col 2"]
    R --> D["col 3"]
    A --> A1["row 1 col 2, then dead end"]
    B --> B1["row 1 col 3"]
    B1 --> B2["row 2 col 0"]
    B2 --> B3["row 3 col 2: solution [1,3,0,2]"]
    C --> C1["...: solution [2,0,3,1]"]
    D --> D1["no free column"]

Complexity: O(n!) time — row r has at most n - r non-conflicting columns, and each placement/test is O(1); rendering adds O(n²) per solution found. O(n) space for the sets, path, and recursion.

Approach 3 — Bitmask backtracking

The three sets can be three integers, one bit per column. In row r, bit c of diag means some earlier queen’s ↘ diagonal passes through column c of this row, and moving down one row shifts every ↘ threat one column right (<< 1) and every ↙ threat one column left (>> 1). Free columns come from one AND/NOT, and x & -x peels off candidates one bit at a time. Same asymptotics, but each check is a few word-level operations. This is the standard optimization when n-queens is the inner loop of a larger computation.

def solveNQueens(n: int) -> list[list[str]]:
    full = (1 << n) - 1
    res: list[list[str]] = []
    placement: list[int] = []

    def backtrack(cols: int, diag: int, anti: int) -> None:
        if cols == full:
            board = [
                "." * c + "Q" + "." * (n - c - 1) for c in placement
            ]
            res.append(board)
            return
        free = full & ~(cols | diag | anti)
        while free:
            bit = free & -free           # lowest free column
            free ^= bit
            placement.append(bit.bit_length() - 1)
            backtrack(
                cols | bit,
                ((diag | bit) << 1) & full,
                (anti | bit) >> 1,
            )
            placement.pop()

    backtrack(0, 0, 0)
    return res

Walkthrough on n = 4, first solution: row 0 masks all zero → free = 1111. Taking bit 0010 (column 1): next call gets cols=0010, diag=0100 (shifted left: the ↘ threat now covers column 2 of row 1), anti=0001. Row 1 free = 1111 & ~0111 = 1000 → column 3 forced. Row 2 masks: cols 1010, diag ((0100|1000)<<1)&1111 = 1000, anti (0001|1000)>>1 = 0100 → free = 0001 → column 0 forced. Row 3 similarly forces column 2, cols reaches 1111 → emit [1,3,0,2], matching Approach 2.

Complexity: O(n!) time, O(n) space — same tree as Approach 2, cheaper constants.

Common pitfalls

• Only checking columns — diagonal conflicts are the whole difficulty; abs(r1 - r2) == abs(c1 - c2) is the test people forget.
• Using r + c for both diagonal directions — one direction needs r - c (or n - 1 + r - c if you index arrays); mixing them accepts illegal boards like queens at (0,0) and (1,1).
• Forgetting to undo all three sets plus the path on backtrack — a single missed discard silently kills valid solutions further right in the tree.
• Rendering with a shared mutable row — build each row string independently; mutating one list of characters reused across rows aliases every board in the output.

Pattern takeaway

Constraint-satisfaction backtracking depends on how early you can reject a partial solution. Reformulate the choice so structural constraints are free (one queen per row ⇒ choose only a column), and encode the remaining constraints as O(1)-checkable summaries of the partial solution (c, r-c, r+c sets). The same recipe — pick the decision granularity, then design incremental conflict bookkeeping — powers Sudoku solvers, graph coloring, and exam scheduling.