NUHMAN.com

Introduction

LeetCode 52: N-Queens II is a variation of the classic N-Queens problem. Instead of returning all valid board configurations, this version simply asks you to return the number of distinct solutions.

This makes it a perfect candidate for an optimized backtracking approach, where we prune paths as early as possible and avoid the overhead of storing full board states.

Problem Statement

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

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

Example:

go

Input: n = 4
Output: 2

Explanation: There are 2 solutions to the 4-queens puzzle.

Constraints

• 1 <= n <= 9

Approach: Backtracking with Attack Zone Tracking

Instead of constructing the actual boards, we count each valid configuration. We still use:

• A map for columns to track used columns
• A map for diagonals:
• row + col for positive diagonals
• row - col for negative diagonals

Every time we place a queen, we:

1. Mark the column and diagonals as used.
2. Recurse to the next row.
3. After the recursion, unmark them (backtrack).

Go Implementation

go

func totalNQueens(n int) int {
    cols := make(map[int]bool)
    posDiags := make(map[int]bool) // row + col
    negDiags := make(map[int]bool) // row - col
    count := 0

    var backtrack func(row int)
    backtrack = func(row int) {
        if row == n {
            count++
            return
        }

        for col := 0; col < n; col++ {
            if cols[col] || posDiags[row+col] || negDiags[row-col] {
                continue
            }

            cols[col], posDiags[row+col], negDiags[row-col] = true, true, true
            backtrack(row + 1)
            cols[col], posDiags[row+col], negDiags[row-col] = false, false, false
        }
    }

    backtrack(0)
    return count
}

Example Walkthrough (n = 4)

1. Try queen at each column of row 0.
2. For each valid placement, go to row 1 and try valid columns.
3. Repeat until all rows are filled → count as a valid solution.
4. Backtrack and try the next configuration.
5. Finally return the total count of valid solutions.

Time and Space Complexity

MetricComplexityTime ComplexityO(n!)Space ComplexityO(n)

• Time: Factorial due to branching at each row.
• Space: O(n) for recursion and column/diagonal maps.

Optimized Version (Bitmask)

If you'd like a faster version (especially for larger n), bitmasking can be used to reduce space and make it extremely efficient. Let me know if you want that version!

Edge Cases

• n = 1: Returns 1
• n = 2 or n = 3: Returns 0 (no valid arrangement)
• n = 9: Still handles efficiently

Key Takeaways

• This is the counting version of the N-Queens problem.
• Backtracking works great with careful pruning using column and diagonal tracking.
• You can extend this logic to use bitmasks for even better performance on larger inputs.