N-Queens II

Difficulty: Hard Source: NeetCode

Problem

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

Constraints:

• 1 <= n <= 9

Prerequisites

Before attempting this problem, you should be comfortable with:

• N-Queens (LeetCode 51) — this is the same problem; just count solutions instead of collecting boards
• Backtracking — row-by-row queen placement with conflict detection via sets

1. Brute Force (Count via N-Queens I)

Intuition

Reuse the full N-Queens solution from problem 15 and just count how many solutions it returns. This is correct but builds all the board strings unnecessarily — we only need the count.

Algorithm

1. Run solveNQueens(n) from N-Queens I.
2. Return len(result).

Solution

def totalNQueens_via_boards(n):
    result = []
    cols = set()
    diag = set()
    anti_diag = set()

    def backtrack(row):
        if row == n:
            result.append(True)  # just mark a solution found
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti_diag:
                continue
            cols.add(col)
            diag.add(row - col)
            anti_diag.add(row + col)
            backtrack(row + 1)
            cols.remove(col)
            diag.remove(row - col)
            anti_diag.remove(row + col)

    backtrack(0)
    return len(result)


print(totalNQueens_via_boards(4))  # 2
print(totalNQueens_via_boards(1))  # 1
print(totalNQueens_via_boards(8))  # 92

Complexity

• Time: O(n!) — explores all placements
• Space: O(n) — sets and recursion depth

2. Backtracking — Count Only

Intuition

Same backtracking as N-Queens I but we skip building the board entirely. Instead of appending a board to a result list, we increment a counter. This saves the O(n^2) cost of constructing and storing each board. The conflict detection logic is identical — sets for columns, diagonals, and anti-diagonals.

Algorithm

1. Initialize count = 0.
2. Define backtrack(row):
   • If row == n: increment count and return.
   • For each col in 0..n-1:
     • Skip if conflict.
     • Add to sets, recurse with row + 1, remove from sets.
3. Call backtrack(0) and return count.

Solution

def totalNQueens(n):
    count = 0
    cols = set()
    diag = set()      # row - col
    anti_diag = 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 diag or (row + col) in anti_diag:
                continue
            cols.add(col)
            diag.add(row - col)
            anti_diag.add(row + col)
            backtrack(row + 1)
            cols.remove(col)
            diag.remove(row - col)
            anti_diag.remove(row + col)

    backtrack(0)
    return count


print(totalNQueens(1))  # 1
print(totalNQueens(4))  # 2
print(totalNQueens(5))  # 10
print(totalNQueens(8))  # 92
print(totalNQueens(9))  # 352

Complexity

• Time: O(n!) — same tree traversal as N-Queens I
• Space: O(n) — recursion depth; sets hold at most n elements

Common Pitfalls

Forgetting nonlocal count. In Python 3, you can’t assign to a variable from an enclosing scope without declaring it nonlocal. Without this, count += 1 creates a local variable and the outer count is never updated. Alternatively, use a list count = [0] and increment count[0], which avoids the nonlocal keyword.

Building the board when you don’t need to. N-Queens II only asks for a count. Skip all board construction — no 2D arrays, no string joining. This makes the solution cleaner and avoids the O(n^2) board-building cost at each solution.

Reusing N-Queens I and calling len() on the result. This works but is wasteful — every board string is built and stored just to be counted. The dedicated count-only version here is both simpler and faster.