N-Queens II

Return the number of distinct solutions to the n-queens puzzle.

Why this is worth learning

Placing exactly one queen per row removes one dimension of choice. Columns and the two diagonal identifiers summarize every conflict with earlier rows.

Before coding: one-minute experiment

Why do queens at (0,1) and (2,3) conflict even though they share neither a row nor a column?

Function signature

func TotalNQueens(n int) int

Inputs / outputs

• n: size of the board (n x n).
• Return: count of valid queen placements.

Example

n = 4
Output: 2

Constraints

• 1 <= n <= 9

Core idea (near-solution)

Choosing n arbitrary board cells creates repeated placements and many row conflicts. Place one queen per row in row order instead. A permutation of columns would remove column conflicts, but still postpone diagonal rejection. Columns plus the two diagonal identifiers summarize all conflicts with earlier rows, letting the next row reject an attacking placement immediately. Row count also proves recursive progress.

Backtrack row by row while tracking which columns and diagonals are already occupied.

Invariant: all queens placed in earlier rows do not attack each other.

Algorithm (step-by-step)

1. Use three boolean arrays/sets: cols, diag1 (r-c), diag2 (r+c).
2. DFS on row:
   • If row == n, increment count.
   • For each col in 0..n-1:
     • If col, diag1, or diag2 is used, skip.
     • Mark them, recurse to row+1, then unmark.
3. Return count.

Correctness sketch

Before placing row r, rows 0..r-1 each contain one queen and the occupied-column and diagonal arrays describe exactly those queens. A candidate column is legal precisely when its column, r-c offset, and r+c sum are unoccupied. Marking those three lines and recursing maintains non-attacking placement. Unmarking restores the earlier-row state for another candidate. Reaching row n gives one complete placement; every valid placement has one unique row-by-row column sequence, so the traversal counts it once and omits none. Offset r-c by n to use nonnegative array indices.

Trace (hand walkthrough)

Example input:
n = 4
Output: 2

Walk:
- solution 1: (r0,c1),(r1,c3),(r2,c0),(r3,c2)
- solution 2: (r0,c2),(r1,c0),(r2,c3),(r3,c1)
- total = 2

Pitfalls to avoid

• Forgetting to unmark on backtrack.
• Incorrect diagonal indexing (r-c must be offset to non-negative indices).

Debugging lens

Undo all three markers, not only the column. Test n=1,2,3,4: their counts are 1,0,0,2. Do not divide by rotations/reflections; the contract counts distinct placements separately.

Complexity

A safe coarse time bound for this column-loop implementation is O(n*n!), with substantial diagonal pruning in practice. Tracking arrays and recursion use O(n) auxiliary space; only a count is returned.

Implementation notes (Go)

• Use slices of bool sized n, 2*n, 2*n for cols/diagonals.

Reconstruction checkpoint

Why do queens at (0,1) and (2,3) conflict even though they share neither a row nor a column?

Return to Backtracking · Module quiz