LeetCode 51: N-Queens Solution in Python Explained

Problem Statement

LeetCode 51, N-Queens, is a hard-level problem where you’re given an integer n. Your task is to place n queens on an (n \times n) chessboard such that no two queens threaten each other, meaning no two queens can share the same row, column, or diagonal. Return all distinct solutions as a list of boards, where each board is a list of strings with 'Q' for queens and '.' for empty cells.

Constraints

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

Example

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: Two distinct ways to place 4 queens on a 4x4 board:
.Q..  ..Q.
...Q  Q...
Q...  ...Q
..Q.  .Q..

Input: n = 1
Output: [["Q"]]
Explanation: One queen on a 1x1 board.

Understanding the Problem

How do you solve LeetCode 51: N-Queens in Python? For n = 4, place 4 queens on a 4x4 board so they don’t attack each other, returning all valid configurations. Queens threaten along rows, columns, and diagonals, so we need a systematic way to explore placements. We’ll explore two approaches: a Backtracking with Sets Solution (optimal and primary) and an Alternative with Bit Manipulation (efficient but complex). The backtracking method uses sets to track conflicts and builds solutions row by row.

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, checking conflicts, and recurse if valid. Convert the final board to the required string format.

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

Row 0: Place Q at col 1 -> [.Q..]
Row 1: Place Q at col 3 -> [.Q..,...Q]
Row 2: Place Q at col 0 -> [.Q..,Q...,...Q]
Row 3: Place Q at col 2 -> [.Q..,Q...,...Q,..Q.]
  1. Initialize Tracking Sets.
  • Sets for columns, positive diagonals (row + col), negative diagonals (row - col).
  1. Backtrack.
  • Try each column per row, check conflicts, recurse.
  1. Base Case.
  • When all rows are filled, add board to result.
  1. Format Result.
  • Convert board to list of strings.

Step-by-Step Example

Example 1: n = 4

We need [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]].

  • Goal: Find all valid 4-queen placements.
  • Result for Reference: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]].
  • Start: n = 4, result = [], board = [], cols = set(), pos_diag = set(), neg_diag = set().
  • Step 1: Row 0.
    • Try col 1: cols = {1}, pos_diag = {1}, neg_diag = {-1}, board = [(0,1)].
  • Step 2: Row 1.
    • Try col 3: cols = {1,3}, pos_diag = {1,4}, neg_diag = {-1,-2}, board = [(0,1),(1,3)].
  • Step 3: Row 2.
    • Try col 0: cols = {1,3,0}, pos_diag = {1,4,2}, neg_diag = {-1,-2,-2}, board = [(0,1),(1,3),(2,0)].
  • Step 4: Row 3.
    • Try col 2: cols = {1,3,0,2}, pos_diag = {1,4,2,5}, neg_diag = {-1,-2,0}, board = [(0,1),(1,3),(2,0),(3,2)].
    • Valid, add [".Q..","...Q","Q...","..Q."].
  • Step 5: Backtrack, explore other options, find ["..Q.","Q...","...Q",".Q.."].
  • Finish: Return both solutions.

Example 2: n = 1

We need [["Q"]].

  • Start: n = 1.
  • Step 1: Row 0, col 0, board = [(0,0)], add ["Q"].
  • Finish: Return [["Q"]].

How the Code Works (Backtracking with Sets)

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

def solveNQueens(n: int) -> list[list[str]]:
    # Line 1: Initialize result and tracking sets
    result = []
    cols = set()
    pos_diag = set()  # row + col
    neg_diag = set()  # row - col

    # Line 2: Backtracking helper
    def backtrack(row: int, board: list[tuple[int, int]]) -> None:
        # Line 3: Base case: all queens placed
        if row == n:
            # Line 4: Convert to string format
            grid = [['.'] * n for _ in range(n)]
            for r, c in board:
                grid[r][c] = 'Q'
            result.append([''.join(row) for row in grid])
            return

        # Line 5: 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 6: Place queen
                cols.add(col)
                pos_diag.add(row + col)
                neg_diag.add(row - col)
                board.append((row, col))
                # Line 7: Recurse
                backtrack(row + 1, board)
                # Line 8: Backtrack
                cols.remove(col)
                pos_diag.remove(row + col)
                neg_diag.remove(row - col)
                board.pop()

    # Line 9: Start backtracking
    backtrack(0, [])
    # Line 10: Return all solutions
    return result

Alternative: Backtracking with Bit Manipulation

Explanation

Use bit manipulation to track conflicts efficiently. Represent columns and diagonals as bitmasks, where a 1 indicates an occupied position. Backtrack row by row, updating bitmasks to check validity.

  1. Initialize Bitmasks.
  2. Backtrack with Bits.
  • Use bitwise operations to place queens.

3. Format Result.

Step-by-Step Example (Alternative)

For (n = 4):

  • Start: cols = 0, pos_diag = 0, neg_diag = 0, board = [].
  • Step 1: Row 0, try col 2 (0010).
    • cols = 0010, pos_diag = 0010, neg_diag = 0010, board = [(0,2)].
  • Step 2: Row 1, try col 0 (0001).
    • cols = 0011, pos_diag = 0011, neg_diag = 0011, board = [(0,2),(1,0)].
  • Step 3: Continue, build solution.
  • Finish: Generate both configurations.

How the Code Works (Bit Manipulation)

def solveNQueensBit(n: int) -> list[list[str]]:
    # Line 1: Initialize result
    result = []

    # Line 2: Backtracking helper
    def backtrack(row: int, cols: int, pos_diag: int, neg_diag: int, board: list[tuple[int, int]]) -> None:
        if row == n:
            grid = [['.'] * n for _ in range(n)]
            for r, c in board:
                grid[r][c] = 'Q'
            result.append([''.join(row) for row in grid])
            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
            board.append((row, col))
            # Line 6: Recurse
            backtrack(row + 1, cols, pos_diag, neg_diag, board)
            # Line 7: Backtrack
            cols &= ~bit
            pos_diag = (pos_diag >> 1) & ~bit
            neg_diag = (neg_diag << 1) & ~bit
            board.pop()
            available &= available - 1

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

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) – Bitmasks and board.

Efficiency Notes

Both are O(n!) time due to the combinatorial nature, but Sets is more readable and practical for LeetCode 51. Bit Manipulation is faster for small (n) (bit operations) but less intuitive.

Key Insights

Tips to master LeetCode 51:

  • Conflict Tracking: Use sets or bits for rows, cols, diagonals.
  • Row-by-Row: Build solutions incrementally.
  • Diagonal Logic: row+col and row-col identify diagonals.

Additional Example

For (n = 2):

  • Goal: [] (no solution).
  • Backtracking: No valid placement, return [].
  • Result: [].

Edge Cases

  • \(n = 1\): [["Q"]].
  • \(n = 2\) or \(n = 3\): [] (no solutions).
  • \(n = 4\): Two solutions.

Final Thoughts

The Backtracking with Sets solution is a stellar choice for LeetCode 51 in Python—clear, efficient, and perfect for N-Queens. For a related challenge, try LeetCode 50: Pow(x, n) to switch gears with math! Ready to place some queens? Solve LeetCode 51 on LeetCode now and test it with (n = 4) or (n = 5) to master backtracking. Dive in and rule the board!