N-Queens

The board is only the output surface. The real N-Queens solution is a depth-n search over column assignments, with three constraints checked before each assignment.

The reliable structure is:

1. Process one row per recursion level.
2. Track occupied columns and both diagonal directions.
3. Place, recurse, and undo.
4. Copy the board only when all rows are complete.

That turns mutable board manipulation into a constrained search over partial assignments.

Read the contract before the board

Given an integer n, return every distinct n × n board that places n queens without attacks. Each board is represented by n strings of length n:

• "Q" represents a queen.
• "." represents an empty cell.

The result must contain all valid configurations, not just one. The order does not matter. The input satisfies 1 <= n <= 9.

Queens cannot share:

• a row,
• a column,
• a diagonal.

The first reduction follows immediately: if we place exactly one queen in each row, row conflicts disappear by construction.

So instead of making an independent decision for every cell, make one decision per row:

row 0 -> choose a column
row 1 -> choose a column
row 2 -> choose a column
...
row n - 1 -> choose a column

A board becomes a sequence of n column choices. For example:

[1, 3, 0, 2]

means:

row 0 -> column 1
row 1 -> column 3
row 2 -> column 0
row 3 -> column 2

That sequence renders as:

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

The search must enumerate every legal sequence, not stop after the first complete board.

Derive the search tree before pruning

A cell-level brute-force approach starts with n² possible cells and decides whether to place a queen in each one. That search explores states containing multiple queens in the same row, then repeatedly checks and rejects those row conflicts. It spends search effort representing arrangements the problem structure already forbids.

The row-by-row decomposition removes that waste before diagonal pruning begins.

At depth row, the algorithm considers only the n columns in that row. Once earlier columns are occupied, at most n - 1 choices remain for the next row, then at most n - 2, and so on. Ignoring diagonals, the search therefore has a factorial-shaped upper bound:

n · (n - 1) · (n - 2) · ... · 1 = n!

This is already a major reduction from cell-level subset search. It also gives each recursion level a clear meaning: dfs(row) decides the queen's column for exactly one row.

The search still has many branches. The next reduction is constraint pruning: reject a partial assignment as soon as it makes completion impossible.

Suppose the first two queens are at (0, 0) and (1, 2). When processing row 2:

• column 0 is occupied,
• column 2 is occupied,
• column 1 shares a diagonal with (1, 2),
• column 3 shares a diagonal with (1, 2).

There is no reason to place another queen and discover the failure later. The branch is already dead.

Build only prefixes that can still become solutions. Backtracking is the discipline of killing a branch at the first provable contradiction.

For this problem, row decomposition removes row conflicts structurally. Occupancy sets then prune columns and diagonals incrementally.

Turn attacks into constant-time state

A candidate cell is identified by (row, col). Because we process rows from top to bottom, every existing queen is in an earlier row. We only need to check the three attack relationships that are not already guaranteed by the recursion structure.

Columns

Two cells share a column when their column values are equal.

Maintain:

used_columns

A candidate is vertically blocked when:

col in used_columns

One diagonal direction

Cells on the same upper-left to lower-right diagonal share:

row - col

For example:

(0, 0) ->  0
(1, 1) ->  0
(2, 2) ->  0

Maintain:

used_diagonals

A candidate is blocked in this direction when row - col is already present.

The value can be negative. Python sets handle that directly, so no coordinate transformation is needed.

The other diagonal direction

Cells on the opposite diagonal share:

row + col

For example:

(0, 3) -> 3
(1, 2) -> 3
(2, 1) -> 3

Maintain:

used_anti_diagonals

A candidate is blocked when row + col is already present.

Therefore (row, col) is legal exactly when:

col not in used_columns
row - col not in used_diagonals
row + col not in used_anti_diagonals

Each state variable answers one named obligation:

State	Prevents
used_columns	Shared columns
used_diagonals	Shared row - col diagonals
used_anti_diagonals	Shared row + col diagonals
row	Shared rows, by construction

The board remains necessary for producing the required output, but it should not be the primary constraint index. Rescanning the board after every attempted placement obscures the mechanism and adds unnecessary work. The sets are the fast index; the board is the rendering buffer.

Define the invariant and the undo operation

Define dfs(row) with this invariant:

Before dfs(row) begins, every row before row contains exactly one mutually safe queen. Every row from row onward is empty. The board and all three occupancy sets describe exactly that placed prefix.

For each column in the current row:

1. Check the three constraints.
2. Write "Q" into the board.
3. Add the column and diagonal keys to the sets.
4. Recurse on the next row.
5. Clear the board cell.
6. Remove the same three keys.

The branch has one strict shape:

check -> place -> recurse -> undo

The undo belongs to the stack frame that performed the placement. If a branch places (row, col) but fails to remove one marker afterward, that marker leaks into the next sibling branch. The algorithm then rejects a legal placement because it remembers a queen that no longer exists.

At row == n, every row contains one queen. Since every placement passed the constraints, the board is valid. Convert it to independent strings and append that snapshot to the results.

The snapshot matters. The working board is mutable and will be changed as recursion returns. Appending the mutable board itself would not preserve a stable answer.

Prove that every solution appears exactly once

Passing examples is not a correctness proof. For an enumeration problem, establish soundness, completeness, uniqueness, and state restoration separately.

Soundness

Every recorded board has one queen in every row because recursion advances only after placing one queen in the current row.

When a queen is placed at (row, col), the algorithm confirms that:

• col is unused,
• row - col is unused,
• row + col is unused.

Those checks compare the new queen with every earlier queen. Therefore no two queens share a column or either diagonal. Rows are already unique.

Every recorded board is valid.

Completeness

Take any valid board. Because it contains one queen in every row, it defines exactly one column choice for row 0, one for row 1, and so on.

When the search reaches a row from that board, its intended column is legal: the original board contains no attacking pair. The loop tries every column, so it eventually tries that intended choice. Repeating this argument row by row shows that the search reaches the complete sequence for every valid board.

Pruning removes only candidates that already violate a constraint. It cannot remove a prefix of a valid board.

Uniqueness

A board has one column choice for each row. Reading the rows from top to bottom produces one sequence:

[col_for_row_0, col_for_row_1, ..., col_for_row_n-1]

The search makes decisions in exactly that order. No different decision path can produce the same sequence.

Therefore each valid board is generated once.

State restoration

Immediately before every dfs(row) call, the board and occupancy sets describe exactly the current prefix. After the call returns, the caller removes the markers it added, restoring the state that existed before that candidate was tried.

This restoration makes sibling branches independent. Without it, the search is not exploring separate candidates; it is exploring candidates contaminated by old state.

Trace pruning with n = 4

Use zero-based coordinates. For a queen at (row, col), record:

column: col
diagonal: row - col
anti-diagonal: row + col

Consider the failed prefix:

(0, 0)
(1, 2)

After (0, 0), the markers are:

column:   0
diagonal: 0 - 0 = 0
anti:     0 + 0 = 0

After (1, 2):

columns:   {0, 2}
diagonals: {0, -1}
anti:      {0, 3}

Now test row 2:

Candidate	Reason
(2, 0)	Column 0 is occupied
(2, 1)	2 - 1 is clear, but 2 + 1 = 3 is occupied
(2, 2)	Column 2 is occupied
(2, 3)	2 - 3 = -1 is occupied

The branch ends immediately. The recursive calls return in reverse order:

1. Undo (1, 2): remove column 2, diagonal -1, and anti-diagonal 3.
2. Undo (0, 0): remove column 0, diagonal 0, and anti-diagonal 0.

Now consider the successful sequence:

[1, 3, 0, 2]

Its placements are:

Cell	Column	row - col	row + col
(0, 1)	1	-1	1
(1, 3)	3	-2	4
(2, 0)	0	2	2
(3, 2)	2	1	5

Every value within each constraint category is distinct, so the board is valid:

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

The same values must be removed during backtracking. A diagonal marker left behind after this branch can incorrectly block a later branch, creating a bug that appears only when the search has multiple sibling solutions.

Implement the N-Queens solution in Python

The implementation keeps the derivation visible:

• board stores the mutable rendering.
• used_columns enforces column uniqueness.
• used_diagonals enforces row - col uniqueness.
• used_anti_diagonals enforces row + col uniqueness.
• dfs(row) supplies the row decision.

from typing import List


def solve_n_queens(n: int) -> List[List[str]]:
    board = [["."] * n for _ in range(n)]
    used_columns = set()
    used_diagonals = set()       # row - col
    used_anti_diagonals = set()  # row + col
    solutions = []

    def dfs(row: int) -> None:
        if row == n:
            # Copy the current state into independent row strings.
            solutions.append(["".join(current_row) for current_row in board])
            return

        for col in range(n):
            diagonal = row - col
            anti_diagonal = row + col

            if (
                col in used_columns
                or diagonal in used_diagonals
                or anti_diagonal in used_anti_diagonals
            ):
                continue

            # Place.
            board[row][col] = "Q"
            used_columns.add(col)
            used_diagonals.add(diagonal)
            used_anti_diagonals.add(anti_diagonal)

            dfs(row + 1)

            # Undo exactly what this frame changed.
            board[row][col] = "."
            used_columns.remove(col)
            used_diagonals.remove(diagonal)
            used_anti_diagonals.remove(anti_diagonal)

    dfs(0)
    return solutions

The mutation ownership is local: the frame that adds a marker also removes it. That makes the undo list easy to audit.

For the stated input range, sets are the clearest primary implementation. They expose the diagonal equations and avoid offset arithmetic. Bitmasks can compress the same three occupancy sets into integer bits, but they do not change the search or its proof. Treat bitmasks as an optimization after the set-based version is correct, not as a substitute for deriving the state.

Analyze search work and output cost

At depth k, ignoring diagonal constraints, the row-by-row search has at most:

n · (n - 1) · ... · (n - k + 1)

partial assignments. Across all depths, this produces factorial-shaped search work. Diagonal pruning reduces the actual number of visited nodes, but the implementation still loops over up to n columns at each visited node.

For this direct implementation:

• Set membership, insertion, and removal are O(1) average.
• The search has a coarse upper bound of O(n · n!), accounting for the column loop at each search node.
• This is an upper bound, not an exact count of explored nodes; diagonal pruning determines how many branches survive.
• If S is the number of solutions, rendering one board costs O(n²).
• Materializing all returned boards costs O(S · n²) additional work and result space.

State the two costs separately:

search work + output materialization

Returning every board necessarily carries an output-sized cost. That term is not an implementation accident; it is imposed by the contract.

Auxiliary space excludes the returned answers:

• mutable board: O(n²)
• recursion depth: O(n)
• three occupancy sets: O(n)

Therefore auxiliary space is O(n²), dominated by the board. Including the required output, total space is:

O(n² + S · n²)

Check edge cases and common failures

The recursion needs no special-case branches for these valid inputs:

• n = 1: one board, ["Q"]
• n = 2: no valid boards, []
• n = 3: no valid boards, []
• n = 4: two valid boards

Check the structure rather than patching symptoms:

1. Base case: use row == n, so the final row is included.
2. Snapshot: join each row into a new string before appending.
3. Undo: remove the cell and all three markers after recursion returns.
4. Matching formulas: use row - col and row + col consistently during both insertion and removal.
5. One decision per row: never skip a row or place multiple queens in one row.
6. Enumerate all branches: do not return after the first complete board.

For debugging, independently validate every stored board:

• it has n rows,
• every row has length n,
• every symbol is "Q" or ".",
• column positions are unique,
• row - col values are unique,
• row + col values are unique.

When the result is wrong, inspect state before inspecting syntax:

Which marker was added? Which marker should have been removed? Which sibling branch saw stale state?

Symmetry pruning and bitmasks are reasonable extensions, but they add proof obligations. First make the row decision, constraint sets, invariant, and undo sequence correct. Compress a working model; do not optimize a model you have not finished deriving.

The transferable pattern

N-Queens is a strong signal for constraint-pruned enumeration:

• the answer is built one decision at a time,
• each recursion level owns one variable or position,
• partial assignments can be rejected incrementally,
• constraints fit compact state,
• every candidate branch must be restored before the next one.

When you see that shape, do not begin with the board or a clever optimization. Begin with the state invariant:

What does one recursion level decide, what constraints must be checked, and what exactly must be undone?

Then write the branch in four verbs:

check -> place -> recurse -> undo

That is the reusable N-Queens solution. The board is only the output surface. The algorithm lives in the decisions, the constraint state, and the discipline of restoration.