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
- The same backtracking as N-Queens, but only counting solutions instead of materialising boards.
- Tracking three sets (columns and the two diagonals) makes each validity check O(1).
- No board is needed, which saves O(n^2) memory.
- 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 + cfor both diagonals: they have distinct invariants. - Forgetting the backtracking removals: later branches would be blocked.
- Assuming
n = 1has 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.