Problem Statement

N-Queens II

Picture a chessboard that is n squares wide and n squares tall. A queen is a piece that can attack along its row, its column, and both diagonals. We want to place n queens so that no two of them can attack each other. In this version of the puzzle we do not need to draw the finished boards, we only need to count how many different safe arrangements exist. So instead of saving each board we just keep a number and add one every time we finish a full safe placement. That saves memory, since we never store a board at all.

hardBacktrackingBacktrackingTime: O(n!) · Space: O(n)

Signals to notice

count N-Queens solutionssame as N-Queens I but count onlyno board construction needed

Brute force first

Same backtracking as N-Queens I.

The key insight

Same backtracking but increment counter instead of building boards. Slightly faster — no string construction. O(n!).

Trace it on `n=4`

row0: try col0 -> place. cols={0}, diags={0}, anti={0}. recurse row1
row1: col0/col1 blocked; col2 ok -> place. cols={0,2}, diags={0,-1}, anti={0,3}. recurse row2
row2: every col blocked (col1 anti=3, others on col/diag) -> dead end, backtrack
row1: try col3 -> place. cols={0,3}, diags={0,-2}, anti={0,4}. recurse row2
row2: col1 ok -> place. cols={0,3,1}, recurse row3; row3: col... no valid -> back; col1 also dead -> backtrack up to row0
row0: try col1 -> place -> leads to full valid board (row3==n) -> count=1
row0: try col2 (mirror of col1) -> full valid board -> count=2; col3 -> dead. return count=2

What must stay true

Same constraint checking: columns, positive diag, negative diag. Just count valid complete placements.

Shape of the loop

backtrack(row):
  if row == n: count += 1; return
  for col in 0..n-1:
    if col in cols or (row-col) in diags or (row+col) in antiDiags: continue
    add col, row-col, row+col to the three sets
    backtrack(row + 1)
    remove col, row-col, row+col   // undo for next col

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Building board strings — unnecessary for counting. Just count.

Backtracking Pattern