NeetCode #518LC-51HardBacktrackingNC 150NC 250
← Back to All Problems#518 · #51 · N-Queens(N 皇后)
📌 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 all distinct solutions, each as a list of strings. Constraints: 1 <= n <= 9.💡 Core Algorithmic Approaches
- Place queens one row at a time, so no two can share a row.
- Track the occupied columns, and the two diagonals:
r - cis constant on one diagonal andr + con the other. - Sets for those three constraints make the validity check O(1).
- Backtrack by removing the queen and the three set entries.
💻 Benchmark Python3 Implementation
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
cols = set()
diag1 = set() # r - c
diag2 = set() # r + c
board = [["."] * n for _ in range(n)]
def dfs(r: int) -> None:
if r == n:
res.append(["".join(row) for row in board])
return
for c in range(n):
if c in cols or (r - c) in diag1 or (r + c) in diag2:
continue # attacked
cols.add(c); diag1.add(r - c); diag2.add(r + c)
board[r][c] = "Q"
dfs(r + 1)
board[r][c] = "." # backtrack
cols.discard(c); diag1.discard(r - c); diag2.discard(r + c)
dfs(0)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n!) with heavy pruning: far fewer than n^n placements are actually explored.
💾 Space Complexity
O(n) for the sets and the recursion depth, plus O(n^2) for the board.
⚠️ Interview Pitfalls & Follow-ups
- Using
r + cfor both diagonals: the two diagonals have different invariants --r - candr + c. - Forgetting to remove the set entries on backtrack: subsequent branches would see phantom attacks.
- Checking the whole board for conflicts: O(n) per placement; the three sets make it O(1).
- Placing queens column by column instead of row by row: either works, but row-by-row is the conventional formulation.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.