⚡Flashcard Drill➔
NeetCode #519LC-52HardBacktrackingNC 250
← Back to All Problems

#519 · #52 · N-Queens II(N 皇后 II)

📌 Problem Statement & Constraints

The n-queens puzzle places n queens on an n x n board so that no two attack each other. Given n, return the number of distinct solutions. Constraints: 1 <= n <= 9.

💡 Core Algorithmic Approaches

  1. The same backtracking as N-Queens, but only counting solutions instead of materialising boards.
  2. Tracking three sets (columns and the two diagonals) makes each validity check O(1).
  3. No board is needed, which saves O(n^2) memory.
  4. The count can also be expressed with bitmasks, which is faster but less readable.

💻 Benchmark Python3 Implementation

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.count = 0
        cols = set()
        diag1 = set()                      # r - c
        diag2 = set()                      # r + c

        def dfs(r: int) -> None:
            if r == n:
                self.count += 1            # a complete placement
                return
            for c in range(n):
                if c in cols or (r - c) in diag1 or (r + c) in diag2:
                    continue
                cols.add(c); diag1.add(r - c); diag2.add(r + c)
                dfs(r + 1)
                cols.discard(c); diag1.discard(r - c); diag2.discard(r + c)

        dfs(0)
        return self.count

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n!) with pruning.
💾 Space Complexity
O(n) for the sets and the recursion depth (no board needed).

⚠️ Interview Pitfalls & Follow-ups

  • Building the board strings just to count: unnecessary allocation.
  • Using r + c for both diagonals: they have distinct invariants.
  • Forgetting the backtracking removals: later branches would be blocked.
  • Assuming n = 1 has no solutions: a single queen on a 1x1 board is a valid solution.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems