LeetCode 52: N-Queens II Solution in Python Explained

Problem Statement

LeetCode 52, N-Queens II, is a hard-level problem where you’re given an integer n. Your task is to determine the total number of distinct ways to place n queens on an (n \times n) chessboard such that no two queens threaten each other—no two queens can share the same row, column, or diagonal. Unlike LeetCode 51, you only need to return the count of solutions, not the actual board configurations.

Constraints

  • 1 <= n <= 9: Board size is between 1 and 9.

Example

Input: n = 4
Output: 2
Explanation: There are 2 distinct ways to place 4 queens:
.Q..  ..Q.
...Q  Q...
Q...  ...Q
..Q.  .Q..

Input: n = 1
Output: 1
Explanation: One way to place 1 queen on a 1x1 board.

Input: n = 2
Output: 0
Explanation: No way to place 2 queens on a 2x2 board without conflict.

Understanding the Problem

How do you solve LeetCode 52: N-Queens II in Python? For n = 4, count the number of valid ways to place 4 queens on a 4x4 board without any two attacking each other—here, there are 2 solutions. We need the count, not the boards, so we can optimize by avoiding board construction. We’ll explore two approaches: a Backtracking with Sets Solution (optimal and primary) and an Alternative with Bit Manipulation (efficient and compact). The backtracking method tracks conflicts row by row and increments a counter for valid placements.

Solution 1: Backtracking with Sets Approach (Primary)

Explanation

Use backtracking to place queens row by row, tracking occupied columns and diagonals with sets. For each row, try placing a queen in each column, check for conflicts, and recurse if valid. Increment a counter when a full placement is found, avoiding the need to store boards.

Here’s a flow for (n = 4):

Row 0: Try col 1
Row 1: Try col 3
Row 2: Try col 0
Row 3: Try col 2 -> Valid, count += 1
Backtrack, try other paths -> Find 2nd solution
  1. Initialize Counter and Sets.
  • Counter for solutions, sets for columns and diagonals.
  1. Backtrack.
  • Place queens, check conflicts, recurse.
  1. Base Case.
  • When row = n, increment counter.
  1. Return Count.

Step-by-Step Example

Example 1: n = 4

We need 2.

  • Goal: Count valid 4-queen placements.
  • Result for Reference: 2.
  • Start: n = 4, count = 0, cols = set(), pos_diag = set(), neg_diag = set().
  • Step 1: Row 0.
    • Try col 1: cols = {1}, pos_diag = {1}, neg_diag = {-1}.
  • Step 2: Row 1.
    • Try col 3: cols = {1,3}, pos_diag = {1,4}, neg_diag = {-1,-2}.
  • Step 3: Row 2.
    • Try col 0: cols = {1,3,0}, pos_diag = {1,4,2}, neg_diag = {-1,-2,-2}.
  • Step 4: Row 3.
    • Try col 2: cols = {1,3,0,2}, pos_diag = {1,4,2,5}, neg_diag = {-1,-2,0}.
    • Valid, count += 1 (now 1).
  • Step 5: Backtrack, explore other paths.
    • Row 0, col 2 → Row 1, col 0 → Row 2, col 3 → Row 3, col 1.
    • Valid, count += 1 (now 2).
  • Step 6: No more valid paths.
  • Finish: Return 2.

Example 2: n = 1

We need 1.

  • Start: n = 1, count = 0.
  • Step 1: Row 0, col 0, no conflicts, count += 1.
  • Finish: Return 1.

How the Code Works (Backtracking with Sets)

Here’s the Python code with line-by-line explanation:

def totalNQueens(n: int) -> int:
    # Line 1: Initialize counter and tracking sets
    count = [0]  # Use list to modify in closure
    cols = set()
    pos_diag = set()  # row + col
    neg_diag = set()  # row - col

    # Line 2: Backtracking helper
    def backtrack(row: int) -> None:
        # Line 3: Base case: all queens placed
        if row == n:
            count[0] += 1
            return

        # Line 4: Try each column in current row
        for col in range(n):
            if (col not in cols and 
                (row + col) not in pos_diag and 
                (row - col) not in neg_diag):
                # Line 5: Place queen
                cols.add(col)
                pos_diag.add(row + col)
                neg_diag.add(row - col)
                # Line 6: Recurse
                backtrack(row + 1)
                # Line 7: Backtrack
                cols.remove(col)
                pos_diag.remove(row + col)
                neg_diag.remove(row - col)

    # Line 8: Start backtracking
    backtrack(0)
    # Line 9: Return total count
    return count[0]

Alternative: Backtracking with Bit Manipulation

Explanation

Use bit manipulation to track conflicts with bitmasks for columns and diagonals. Process row by row, using bitwise operations to identify available positions and update masks. Increment a counter for each valid solution.

  1. Initialize Counter and Bitmasks.
  2. Backtrack with Bits.
  • Use bits to place queens, update masks.

3. Base Case.

  • Increment count when \(n\) queens are placed.

Step-by-Step Example (Alternative)

For (n = 4):

  • Start: count = 0, cols = 0, pos_diag = 0, neg_diag = 0.
  • Step 1: Row 0, available = 1111, try col 2 (0100).
    • cols = 0100, pos_diag = 0100, neg_diag = 0100.
  • Step 2: Row 1, available = 1011, try col 0 (0001).
    • cols = 0101, pos_diag = 0011, neg_diag = 0011.
  • Step 3: Continue, find first solution, count = 1.
  • Step 4: Backtrack, find second solution, count = 2.
  • Finish: Return 2.

How the Code Works (Bit Manipulation)

def totalNQueensBit(n: int) -> int:
    # Line 1: Initialize counter
    count = [0]

    # Line 2: Backtracking helper
    def backtrack(row: int, cols: int, pos_diag: int, neg_diag: int) -> None:
        if row == n:
            count[0] += 1
            return

        # Line 3: Available positions
        available = ((1 << n) - 1) & ~(cols | pos_diag | neg_diag)
        while available:
            # Line 4: Pick rightmost 1
            bit = available & -available
            col = bit.bit_length() - 1
            # Line 5: Update bitmasks
            cols |= bit
            pos_diag = (pos_diag | bit) << 1
            neg_diag = (neg_diag | bit) >> 1
            # Line 6: Recurse
            backtrack(row + 1, cols, pos_diag, neg_diag)
            # Line 7: Backtrack
            cols &= ~bit
            pos_diag = (pos_diag >> 1) & ~bit
            neg_diag = (neg_diag << 1) & ~bit
            available &= available - 1

    # Line 8: Start backtracking
    backtrack(0, 0, 0, 0)
    # Line 9: Return total count
    return count[0]

Complexity

  • Backtracking with Sets:
    • Time: O(n!) – Explore all valid permutations, pruning reduces actual time.
    • Space: O(n) – Recursion stack and sets.
  • Bit Manipulation:
    • Time: O(n!) – Similar exploration.
    • Space: O(n) – Recursion stack, O(1) for bitmasks.

Efficiency Notes

Both are O(n!) time due to the combinatorial nature of N-Queens, but Sets is more readable and practical for LeetCode 52. Bit Manipulation is slightly faster (bit operations) and uses less memory for tracking, but it’s less intuitive.

Key Insights

Tips to master LeetCode 52:

  • Count Only: Skip board construction for efficiency.
  • Conflict Check: Track cols and diagonals precisely.
  • Backtrack Smartly: Explore all rows systematically.

Additional Example

For (n = 5):

  • Goal: 10.
  • Backtracking: Explore, count 10 valid placements.
  • Result: 10.

Edge Cases

  • \(n = 1\): 1 solution.
  • \(n = 2\) or \(n = 3\): 0 solutions.
  • \(n = 9\): 352 solutions.

Final Thoughts

The Backtracking with Sets solution is a top pick for LeetCode 52 in Python—clear, efficient, and tailored to counting solutions. For a related challenge, try LeetCode 51: N-Queens to see the full boards! Ready to count queens? Solve LeetCode 52 on LeetCode now and test it with (n = 4) or (n = 5) to sharpen your backtracking skills. Dive in and tally up the wins!