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.]
- Initialize Tracking Sets.
- Sets for columns, positive diagonals (row + col), negative diagonals (row - col).
- Backtrack.
- Try each column per row, check conflicts, recurse.
- Base Case.
- When all rows are filled, add board to result.
- 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.
- Initialize Bitmasks.
- 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!