N-Queens II: Counting Solutions with Backtracking

Given an integer n, return the number of distinct solutions to the n-queens puzzle. You must place n queens on an n x n chessboard so that no two queens attack each other. Instead of returning the board configurations, just return the count.

This is LeetCode 52: N-Queens II, and it is the counting variant of N-Queens (LeetCode 51). The backtracking logic is identical. The only difference is what you do when you find a valid configuration: instead of building a board and appending it to a results list, you increment a counter. That simplification makes the code shorter and eliminates the O(n^2) cost of constructing each solution, but the search itself does not change.

Solution 1

Solution 2

Why this problem matters

N-Queens II reinforces the same constraint-based backtracking you learned in N-Queens, but it strips away the board-building distraction. With no need to construct string representations or manage a 2D board, you can focus entirely on the backtracking skeleton and the three constraint sets. This makes it a good second pass: if you solved N-Queens by understanding the concepts, N-Queens II tests whether you can reproduce the core algorithm without the scaffolding of board construction.

It also teaches an important interview instinct. When a problem says "count how many" instead of "list all," check whether the enumeration logic stays the same and only the collection step changes. If so, swapping result.append(...) for count += 1 is all you need. That awareness saves time and avoids overcomplicating the solution.

The key insight

Since each row must contain exactly one queen, place queens row by row. At each row, try every column from 0 to n - 1. Before placing, check three constraints:

1. Column: is column c already occupied?
2. Main diagonal (top-left to bottom-right): every cell on the same main diagonal has the same value of row - col.
3. Anti-diagonal (top-right to bottom-left): every cell on the same anti-diagonal has the same value of row + col.

Track these with three sets: cols, diags (for row - col), and anti_diags (for row + col). If any of the three lookups hits, skip that column. If all three are clear, place the queen, recurse to the next row, then undo. When row == n, you have placed all queens successfully, so increment the counter.

The solution

def total_n_queens(n: int) -> int:
    cols = set()
    diags = set()
    anti_diags = set()
    count = 0

    def backtrack(row):
        nonlocal count
        if row == n:
            count += 1
            return

        for col in range(n):
            if col in cols:
                continue
            if row - col in diags:
                continue
            if row + col in anti_diags:
                continue

            cols.add(col)
            diags.add(row - col)
            anti_diags.add(row + col)

            backtrack(row + 1)

            cols.remove(col)
            diags.remove(row - col)
            anti_diags.remove(row + col)

    backtrack(0)
    return count

Compare this to the N-Queens solution. The board array is gone. The result list is gone. There is no string conversion. Just the three constraint sets, the backtracking loop, and a counter that increments at the base case. Every other line is the same: the constraint guard clauses, the choose step that adds to three sets, the recursive call, and the unchoose step that removes from three sets.

The nonlocal count declaration lets the nested backtrack function modify the count variable defined in the enclosing scope. Without it, Python treats count += 1 as a local assignment and raises an UnboundLocalError.

Visual walkthrough

Let's trace the algorithm on n = 4. The two valid solutions are the boards shown above. Watch how the counter increments each time the recursion reaches row == n.

The critical point is that the search tree is exactly the same as in N-Queens. The algorithm explores the same branches, backtracks at the same dead ends, and finds the same valid configurations. The only difference is what happens at the leaf: count += 1 instead of building a board string. This is why the time complexity does not improve. You still visit every valid path through the decision tree.

Complexity analysis

Time is O(n!) by the same argument as N-Queens. At row 0 you have n column choices. At row 1, at least one column is taken, leaving at most n - 1. At row 2, at most n - 2, and so on. The upper bound is n * (n - 1) * (n - 2) * ... * 1 = n!. Diagonal constraints prune even more aggressively in practice, but n! is the standard interview answer.

Space drops to O(n) because you no longer store the board or the list of solutions. The three constraint sets hold at most n elements each (one per row that has a queen placed). The recursion stack goes n levels deep. That gives O(n) total working space, which is better than the O(n^2) of N-Queens where you maintain a 2D board.

Edge cases

Before submitting, check these:

• n = 1: one queen on a 1x1 board. Return 1.
• n = 2: no valid placement exists (the two queens always share a diagonal or column). Return 0.
• n = 3: also impossible. Return 0.
• n = 4: exactly 2 solutions. Good test case for verifying your diagonal tracking.
• n = 8: the classic version. 92 solutions. If your count is wrong, double-check that you are tracking both row - col and row + col.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently.

1. Constraint-based backtracking

The pattern of checking constraints before committing to a choice:

for candidate in choices:
    if violates_constraint(candidate):
        continue

    apply(candidate)
    explore()
    undo(candidate)

In N-Queens II, the constraints are the three set lookups (cols, diags, anti_diags). In Sudoku Solver, the constraints check row, column, and 3x3 box. The shape is always the same: guard clauses at the top of the loop reject invalid candidates before you commit. The constraint check is what makes the algorithm fast enough to be practical. Without it, you would brute-force every arrangement and only validate at the end.

2. Diagonal tracking with row - col and row + col

Every cell on the same main diagonal shares the same row - col value. Every cell on the same anti-diagonal shares the same row + col value. Two sets. Two formulas. O(1) checks.

This trick shows up in any grid problem where diagonal relationships matter. Once you internalize the formulas, you can apply them to N-Queens, N-Queens II, or any custom constraint problem that involves diagonal conflict detection.

From understanding to recall

You understand how the three sets track constraints. You see how row - col and row + col map to diagonals, and how incrementing a counter replaces the board-building step from N-Queens. But can you write the constraint validation and diagonal tracking from scratch in an interview?

That is the hard part. The details are small but easy to mix up under pressure: which formula is the main diagonal vs. the anti-diagonal, remembering to undo all three sets, using nonlocal for the counter. These are not conceptual issues. They are recall problems.

Spaced repetition fixes recall. You practice writing the constraint checking and counter logic from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "count valid configurations" and the code flows out without hesitation.

The constraint-validation and diagonal-tracking patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• N-Queens - The full version that returns board configurations. Compare the two solutions to see that the only difference is the base case: result.append(board) vs. count += 1.
• Sudoku Solver - Another constraint-based backtracking problem with the same choose-explore-unchoose skeleton. Sudoku uses row, column, and box sets instead of column and diagonal sets.

CodeBricks breaks N-Queens II into its constraint-validation and diagonal-tracking building blocks, then drills them independently with spaced repetition. You type the backtracking constraints from scratch until the pattern is automatic. When a counting problem shows up in your interview, you do not think about it. You just write it.