Skip to main content

52 - N-Queens II

Difficulty: Hard | Pattern: Backtracking | Company tags: Amazon, Google, Microsoft

Problem Statement​

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2

Example 2:

Input: n = 1
Output: 1

Solution: Backtracking with Sets — O(n!), O(n)​

Key insight: A queen attacks along its column, and two diagonals. Track:

  • cols: set of occupied columns
  • diag1: set of occupied (row - col) diagonals (top-left to bottom-right)
  • diag2: set of occupied (row + col) diagonals (top-right to bottom-left)
def totalNQueens(n: int) -> int:
    count = 0
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    
    def backtrack(row):
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0)
    return count

Algorithm Flow​

Dry Run (n=4)​

Row 0: try col 0,1,2,3

  • col=1: place at (0,1); row 1 try col 3 → (1,3); row 2 try col 0 → (2,0); row 3 try col 2 → (3,2) ✓ solution 1
  • col=2: place at (0,2); row 1 try col 0 → (1,0); row 2 try col 3 → (2,3); row 3 try col 1 → (3,1) ✓ solution 2

Result: 2 ✓

Difference from N-Queens I (LC 51)​

LC 51 returns all board configurations. LC 52 only returns the count, so we avoid building the board representation — just increment count.

Complexity​

  • Time: O(n!) — each queen eliminates options for the next row
  • Space: O(n) — sets and recursion stack

Key Terms​

TermDefinition
BacktrackingIncrementally build a candidate placement and abandon (undo) a branch as soon as it violates a constraint.
Diagonal conflict trackingEvery cell on the same \ diagonal shares row - col; every cell on the same / diagonal shares row + col, letting conflicts be checked in O(1).
State-space pruningSkipping columns already marked unsafe avoids exploring branches that can never yield a valid solution.
Bitmasking (optimization)Represent cols, diag1, diag2 as integers and use bitwise AND/OR to find and mark available columns in O(1) per row, faster than sets in practice.
Symmetry pruningSolutions for columns 0..n/2 mirror solutions for n/2..n, so only half the first row needs to be searched (with special handling for odd n's middle column).

FAQ​

Q1: Why does LC 52 avoid building the board while LC 51 does? LC 52 only needs a count, so allocating and copying an n x n board per solution would be wasted work; a single integer counter suffices.

Q2: Why use row - col and row + col instead of tracking full diagonal coordinates? Every cell on the same anti-diagonal or main diagonal shares one of these two invariants, so a single set membership check replaces an O(n) diagonal scan.

Q3: Can this be solved faster than O(n!) in the worst case? Not asymptotically — the search space is inherently combinatorial — but bitmasking and symmetry pruning cut the constant factor significantly, which matters for larger n in interviews and benchmarks.

Q4: What's the base case and why does it return without placing anything? row == n means all n rows have valid queens placed, so the recursion increments count and returns — there's nothing left to place.

Q5: How would you extend this solution to also return one example board instead of just the count? Track a board list of column choices per row, and when row == n, convert it into the LC 51 string-grid format and return/store it instead of (or alongside) incrementing a counter.

Quick Revision​

  • Problem: count valid ways to place n non-attacking queens on an n x n board.
  • Pattern: backtracking, one queen per row, try each column.
  • Track conflicts in O(1) using three sets: cols, diag1 (row-col), diag2 (row+col).
  • Place a queen, recurse to the next row, then undo (remove) before trying the next column.
  • Base case: row == n means a full valid placement — increment count.
  • No board construction needed since only the count is required (unlike LC 51).
  • Time: O(n!); Space: O(n) for sets and recursion depth.
  • Optimization: replace sets with bitmasks for column/diagonal availability to speed up constant factors.
  • n=4 gives 2 solutions; n=1 gives 1; n=2 and n=3 give 0 (no valid arrangement exists).
  • 51 - N-Queens — same constraint-satisfaction setup, but returns the actual board configurations instead of just the count.
  • Sudoku Solver — another classic backtracking-with-constraint-sets problem (row/col/box conflict tracking).
  • Combination Sum / Permutations — simpler backtracking templates that build up the same "choose, recurse, undo" pattern used here.