N-Queens II

The key change from N-Queens is the output contract: you need one integer, so the search should retain only reversible constraints and count valid leaves.

Read the Counting Contract

The task is to return the number of distinct placements of n queens on an n x n board, where no two queens share:

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

The input satisfies 1 <= n <= 9.

The important distinction is between generating solutions and counting solutions:

• N-Queens generates board layouts, so it must build and copy each valid board.
• N-Queens II only needs the total, so it can discard a placement after exploring its descendants.

That immediately suggests a row-by-row search:

1. Process rows from top to bottom.
2. Try every column in the current row.
3. Reject columns that conflict with earlier queens.
4. Recurse to the next row.
5. Add one when all n rows have been assigned.

The board itself is unnecessary. The search state only needs to answer three questions:

• Is this column occupied?
• Is this descending diagonal occupied?
• Is this ascending diagonal occupied?

The row constraint is handled by the recursion structure: dfs(row) places exactly one queen in row, then advances to row + 1.

Turn Constraints Into Search State

Represent a queen at (row, col) using three identifiers.

Columns

Two queens attack vertically when their columns match, so track:

col

If col_used[col] is true, the candidate is illegal.

Diagonals

For one diagonal family, every cell has the same row + col value.

For example:

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

Those cells lie on the same diagonal.

For the other diagonal family, every cell has the same row - col value.

Because row - col can be negative, shift it by n before using it as an array index:

negative_diagonal = row - col + n

For 0 <= row, col < n, this produces indices from 1 through 2n - 1. An array of length 2 * n is therefore sufficient. Allocating 2 * n + 1 is also harmless and makes the boundary less easy to misread.

The state has a direct mapping to the rules:

State	Question it answers
columns[col]	Does another queen occupy this column?
positive_diagonals[row + col]	Does another queen occupy this diagonal?
negative_diagonals[row - col + n]	Does another queen occupy this diagonal?

This is the core design move. Every mutable field should correspond to a named constraint. If a field has no obligation behind it, it probably does not belong in the search state.

Define the Counting Search

Let dfs(row) mean:

Count all valid completions for rows row through n - 1, assuming rows before row already contain one valid queen each.

For the current row, try every column:

if column or either diagonal is occupied:
    skip this column

mark the column and both diagonals
dfs(row + 1)
unmark the column and both diagonals

The base case is:

if row == n:
    count += 1

At that point, every row has received one queen. The constraint checks guaranteed that no two selected positions share a column or diagonal. Therefore, the current root-to-leaf path represents one valid board.

The count is not computed by adding partial possibilities together in advance. It is accumulated exactly where a complete valid assignment is reached.

Counting versus materializing

A board-generating version might maintain:

board = [
    "...Q",
    "Q...",
    "..Q.",
    "....",
]

At a successful leaf, it would convert or copy that board and append it to a result list.

That work is meaningful when the caller needs the layouts. It is wasted when the caller needs only the number. For N-Queens II, the useful state is:

• current row,
• occupied columns,
• occupied diagonals,
• one scalar count.

The search tree stays the same. The output operation changes.

Correctness: Why Every Leaf Counts Once

The cleanest proof uses an invariant.

At the start of dfs(row), every earlier row contains exactly one queen, the three tracking structures describe those queens exactly, and no earlier placement violates a column or diagonal constraint.

Soundness

Suppose the search reaches row == n.

Every row from 0 through n - 1 received exactly one queen because recursion advances one row at a time. A candidate was placed only when its column and both diagonal identifiers were unoccupied.

Therefore:

• no two queens share a row,
• no two queens share a column,
• no two queens share either diagonal.

The leaf is a valid placement, so adding one is correct.

Completeness

Take any valid board.

Because the algorithm processes rows in order, the board determines one column choice for row 0, one for row 1, and so on. Since the board is valid, each of those choices passes the column and diagonal checks.

The algorithm therefore follows that board's choices all the way to row == n. Every valid board reaches a counted leaf.

Uniqueness

A board has exactly one sequence of column choices under fixed row order:

column chosen for row 0
column chosen for row 1
...
column chosen for row n - 1

No other search branch represents the same sequence. So each valid board reaches exactly one leaf, and each leaf contributes exactly one count.

Restoration

The undo operations are part of the proof, not cleanup added afterward.

After exploring (row, col), the search must restore:

columns[col] = False
positive_diagonals[row + col] = False
negative_diagonals[row - col + n] = False

That returns the state to exactly what it was before the candidate was tried. Sibling branches can then be evaluated independently.

A missed undo creates state leakage: a queen from one branch appears to exist in another branch. The code may still look plausible, but the count becomes too small because legal candidates are incorrectly pruned.

Dry-Run: n = 4

Consider a branch that starts with these choices:

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

After placing (0, 0):

occupied columns:        {0}
row + col diagonals:     {0}
row - col + n diagonals: {4}

For (1, 2):

column:                  2
row + col:               3
row - col + n:           3

The candidate is legal, so the state becomes:

occupied columns:        {0, 2}
row + col diagonals:     {0, 3}
row - col + n diagonals: {4, 3}

Now consider row 2.

• Column 0 is occupied.
• Column 2 is occupied.
• Column 1 has row + col = 3, already occupied.
• Column 3 has row - col + n = 3, already occupied.

There is no legal column. This branch returns without increasing the count. The search then undoes (1, 2), restoring the state from after (0, 0), and tries the next candidate for row 1.

That restoration is what makes the next branch trustworthy.

For n = 4, exactly two complete placements survive the search. The algorithm does not store either arrangement. It reaches each valid leaf and increments the scalar count once:

answer = 2

The trace also exposes why checking only columns is insufficient. A candidate can use a free column and still collide diagonally. The diagonal identifiers turn that geometric condition into constant-time state lookup.

Python Implementation

The following uses boolean arrays rather than sets. Both are valid choices:

• Sets make the identifiers explicit and are difficult to size incorrectly.
• Boolean arrays use bounded integer indices and make each lookup, mark, and undo direct.

For this problem's small constraint, I prefer the arrays because the indexing relationship is visible in the code.

class Solution:
    def totalNQueens(self, n: int) -> int:
        columns = [False] * n

        # row + col ranges from 0 to 2n - 2.
        positive_diagonals = [False] * (2 * n)

        # row - col + n ranges from 1 to 2n - 1.
        negative_diagonals = [False] * (2 * n)

        answer = 0

        def dfs(row: int) -> None:
            nonlocal answer

            # Every row has received one queen.
            if row == n:
                answer += 1
                return

            for col in range(n):
                positive_diagonal = row + col
                negative_diagonal = row - col + n

                if (
                    columns[col]
                    or positive_diagonals[positive_diagonal]
                    or negative_diagonals[negative_diagonal]
                ):
                    continue

                columns[col] = True
                positive_diagonals[positive_diagonal] = True
                negative_diagonals[negative_diagonal] = True

                dfs(row + 1)

                # Restore all state changed by this candidate.
                columns[col] = False
                positive_diagonals[positive_diagonal] = False
                negative_diagonals[negative_diagonal] = False

        dfs(0)
        return answer

The recursive function has one responsibility: resolve one row.

It does not scan the board. It does not rebuild strings. It does not ask a separate helper to search for attacks. The three arrays already contain the exact information needed for the candidate decision.

That narrow responsibility is valuable during an interview because every mutation has a visible owner:

1. compute identifiers,
2. reject conflicts,
3. mark state,
4. recurse,
5. undo state.

Read the error. Trace the state. Fix the assumption.

Common implementation failures

Forgetting one diagonal family

Tracking columns alone prevents vertical collisions but allows diagonal attacks. Tracking only one diagonal family fails for the same reason.

A queen has three independent attack obligations here: column, row + col, and row - col.

Using inconsistent diagonal indices

The expression used during marking must be identical to the expression used during removal:

negative_diagonal = row - col + n

Do not mark with row - col + n and undo with row - col. That leaves the wrong slot occupied and corrupts later branches.

Undoing before recursion returns

The candidate must remain marked while descendants search. If you undo immediately after marking, deeper rows will fail to see the queen and accept invalid placements.

Returning the wrong base-case value

This is a counting search, so the base case contributes one:

answer += 1

It should not return a board, a partial count for an incomplete row, or a value based on how many columns were tried.

Scanning the board for every candidate

A board scan can verify safety, but it repeats work that the constraint state already represents. With three indexed structures, conflict checks remain constant time and the invariant is easier to inspect.

Complexity and the Counting Tradeoff

At row 0, there are at most n choices. Later rows have fewer available columns, even before diagonal pruning. If diagonals were ignored, the row assignments would be bounded by permutations:

n * (n - 1) * ... * 1 = n!

Diagonal checks prune that tree further. So O(n!) is a useful factorial-style description of the search, but it is not an exact count of recursive calls. The actual number depends on how many partial placements survive diagonal pruning.

There is also a small accounting detail: the implementation loops through all n columns at each visited search node. A conservative bound that includes those candidate checks is:

O(n · n!)

Interview discussions often report this as O(n!) because the dominant structure is the factorial search tree and n <= 9. The important point is to avoid claiming that every permutation is explored: diagonal pruning removes many branches.

Each candidate check, mark, and undo is O(1) with boolean arrays.

Auxiliary space is O(n):

• recursion depth is at most n,
• the column array has size n,
• each diagonal array has size O(n).

The scalar answer is O(1) additional output state.

A board-generating N-Queens solution has another cost: every valid layout must be represented and copied. N-Queens II avoids that materialization cost. The search still explores possible placements, but a successful leaf collapses into one integer increment instead of a stored configuration.

That is the practical decision boundary:

• Need the arrangements? Materialize them.
• Need only how many arrangements exist? Count valid leaves.
• Need both? You cannot avoid the output cost for the layouts you actually return.

Bitmasks can compress the same column and diagonal state into integers and reduce constant factors. They do not change the derivation. You still process one row, test three constraints, recurse, and restore or pass updated state. For n <= 9, the readable array version is usually the better interview choice unless optimization is explicitly requested.

Edge Cases and Reliability Checks

Test the boundaries that exercise the state machine, not only the happy path.

n = 1

The first call is dfs(0). One column is available, the queen is placed, and dfs(1) reaches the base case.

Expected result:

1

n = 4

Expected result:

2

This case is especially useful because it contains both dead branches and complete solutions. It tests pruning and restoration together.

Diagonal boundaries

Check the extreme cells:

row = 0, col = n - 1
row - col + n = 1

and:

row = n - 1, col = 0
row - col + n = 2 * n - 1

Those values confirm the shifted diagonal array has enough capacity.

Base-case timing

The count should increase only when row == n, after every row has been assigned. A locally safe placement in the final row is not itself the base case until recursion advances beyond it.

State restoration

When debugging a wrong count, inspect the state immediately before and after each recursive call. Every True assignment must have a matching False assignment for the same index after recursion returns.

If you test outside the stated contract, small unsatisfiable boards are useful for exposing restoration bugs. They force the search to traverse dead branches without producing successful leaves.

Recognize the Count-Valid-Leaves Pattern

The reusable pattern is:

1. Choose the next decision in a fixed order.
2. Reject partial assignments that already violate constraints.
3. Mutate compact state to record the choice.
4. Recurse.
5. Undo the mutation.
6. Add one at every valid terminal state.

For N-Queens II, the fixed decision is the column selected for each row. The constraints are column occupancy and the two diagonal identifiers. The terminal state is row == n.

When the output is a collection, retain each valid leaf. When the output is only a total, let the leaf disappear into a counter. The proof stays the same because the search still enumerates the same valid root-to-leaf assignments.

My interview checklist is short:

• What decision does one recursion level make?
• Which constraint does each state field represent?
• What invariant holds at the start of recursion?
• Which condition defines a complete solution?
• What exactly changes during placement?
• Does every change have a matching undo?

Derive the state from the constraints. Let recursion enumerate complete assignments. Count only valid leaves. That is the N-Queens II solution—and the broader backtracking move worth carrying to the next problem.