N-Queens II — Solution

Problem

Place n queens on an n × n chessboard so that no two queens share a row, column, or diagonal. Return the total number of distinct valid arrangements — you don't need to reconstruct the boards, just count them.

• Input: n = 4
• Output: 2
• Explanation: exactly two configurations exist where no queen can capture another.

For n = 1 the answer is 1; for n = 2 and n = 3 the answer is 0 — no valid arrangement exists.

Intuition

Place exactly one queen per row, working top to bottom. The only question at each row is which column to use. A column is forbidden if an earlier queen already sits in it, or if it lies on the same diagonal. A queen at (row, col) owns diagonal family row - col (the / diagonals) and row + col (the \ diagonals) — values that stay constant as you move along each diagonal. Track these three families in sets for O(1) conflict checks, and backtrack as soon as any column violates a constraint.

Solution — Backtracking with Constraint Sets

Recurse one row at a time. At each row try every column; skip immediately if it conflicts with any tracked set; place the queen, recurse, then undo before trying the next column.

1. Maintain three sets: used_cols, used_left_diag (keyed by row - col), used_right_diag (keyed by row + col).
2. Call backtrack(row=0).
3. Base case: row == n means all queens placed — return 1.
4. For each col in 0..n-1, skip if any of the three sets contains the corresponding key.
5. Add all three keys, recurse to row + 1, accumulate the returned count, then remove all three keys.
6. Return the accumulated count.

1def totalNQueens(n: int) -> int:
2    used_cols: set[int] = set()
3    used_left_diag: set[int] = set()   # row - col is constant along a / diagonal
4    used_right_diag: set[int] = set()  # row + col is constant along a \ diagonal
5
6    def backtrack(row: int) -> int:
7        if row == n:
8            return 1  # every row filled without conflict
9
10        solutions = 0
11        for col in range(n):
12            if col in used_cols:
13                continue
14            if (row - col) in used_left_diag:
15                continue
16            if (row + col) in used_right_diag:
17                continue
18
19            used_cols.add(col)
20            used_left_diag.add(row - col)
21            used_right_diag.add(row + col)
22
23            solutions += backtrack(row + 1)
24
25            used_cols.remove(col)            # undo so siblings can reuse this column
26            used_left_diag.remove(row - col)
27            used_right_diag.remove(row + col)
28
29        return solutions
30
31    return backtrack(0)

Time: O(n!) — at most n choices for row 0, n−1 for row 1, and so on; diagonal pruning eliminates many branches in practice.

Space: O(n) — recursion depth n plus three sets each holding at most n entries.

Complexity Summary

Common Mistakes

• Tracking only columns, not both diagonal families — queens in different columns can still attack diagonally; omitting either set causes overcounting by allowing conflicting placements.
• Confusing row - col with row + col — row - col is constant along / diagonals (top-right to bottom-left) and row + col along \ diagonals; swapping them incorrectly rejects valid placements on one family while missing conflicts on the other.
• Forgetting to remove values from the sets after recursing — without the three remove calls, constraints from one column choice bleed into sibling branches and block valid configurations.
• Off-by-one in the base case — using row == n - 1 returns 1 as soon as the last row is reached, before placing a queen there; the correct base case is row == n, meaning all n rows have already been filled.
• Returning n instead of 1 at the base case — a common slip when adapting from a loop-based skeleton; each complete arrangement counts as exactly one solution, not n.

Related Problems

• N-Queens — same algorithm, but returns the actual board configurations instead of a count
• Sudoku Solver — backtracking with three simultaneous constraint sets (rows, columns, 3×3 boxes), structurally identical pattern
• Permutations — backtracking with a single "used index" set, simpler cousin of this problem
• Word Search — grid backtracking that tracks visited cells rather than queen-attack zones
• Letter Combinations of a Phone Number — introductory backtracking with no conflict constraints, good warm-up before tackling N-Queens