N-Queens II

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

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)

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

• Invariant: all queens placed in earlier rows do not attack each other.
• Each recursive step extends a valid partial solution.
• Backtracking explores all possible choices without duplication.
• Thus every valid solution is found and recorded.

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).

Complexity

• Time: exponential; n <= 9 keeps it manageable.
• Extra space: O(n) for recursion and tracking arrays.

Implementation notes (Go)

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