⚡Flashcard Drill➔
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

  1. Place queens one row at a time, so no two can share a row.
  2. Track the occupied columns, and the two diagonals: r - c is constant on one diagonal and r + c on the other.
  3. Sets for those three constraints make the validity check O(1).
  4. 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 + c for both diagonals: the two diagonals have different invariants -- r - c and r + 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems