The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
Here’s the [Problem Link] to begin with.
Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [["Q"]]
Constraints:
1 <= n <= 9
Solution 1: Brute Force Approach (Check All Conflicts For Each Placement)
Intuition
Think of this like placing queens one by one on a chessboard, and every time you want to place a new queen, you look at the entire board to make sure it won’t be attacked by any existing queen! The brute force approach places queens column by column (to ensure no two queens are in the same column), and for each potential position, it checks all three attack directions: same row, upper-left diagonal, and lower-left diagonal. It’s like being a very careful chess player who double-checks every existing piece on the board before making a move.
Detailed Approach
- Column-by-Column Placement: Place queens one column at a time to ensure no column conflicts.
- Safety Check Function: For each potential position (row, col), check if it’s safe by scanning:
- Left Row: Check if any queen exists in the same row to the left
- Upper-Left Diagonal: Check upper-left diagonal for existing queens
- Lower-Left Diagonal: Check lower-left diagonal for existing queens
- Backtracking: If a position is safe, place the queen and recurse to next column. If not safe or no solution found, backtrack by removing the queen.
- Base Case: When all N columns are filled, we found a valid solution.
- String Manipulation: Build the board using string slicing for each placement/removal.
Code
class Solution:
def isSafe1(self, row, col, board, n):
duprow = row
dupcol = col
# Check upper-left diagonal
while row >= 0 and col >= 0:
if board[row][col] == "Q":
return False
row -= 1
col -= 1
# Reset and check left row
col = dupcol
row = duprow
while col >= 0:
if board[row][col] == "Q":
return False
col -= 1
# Reset and check lower-left diagonal
row = duprow
col = dupcol
while row < n and col >= 0:
if board[row][col] == "Q":
return False
row += 1
col -= 1
return True
def solve(self, col, board, ans, n):
# Base case: placed queens in all columns
if col == n:
ans.append(list(board)) # Make a copy of current board state
return
# Try placing queen in each row of current column
for row in range(n):
if self.isSafe1(row, col, board, n):
# Place queen: replace '.' with 'Q' at position (row, col)
board[row] = board[row][:col] + "Q" + board[row][col + 1 :]
# Recursively solve for next column
self.solve(col + 1, board, ans, n)
# Backtrack: remove queen by replacing 'Q' with '.'
board[row] = board[row][:col] + "." + board[row][col + 1 :]
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
board = ["." * n for _ in range(n)] # Initialize n×n board with dots
self.solve(0, board, ans, n) # Start from column 0
return ansCode Explanation
This brute force solution uses a comprehensive safety check for each queen placement. The isSafe1 function performs three separate scans: it checks the entire row to the left, the upper-left diagonal, and the lower-left diagonal. For each potential queen position, we scan these three directions completely to ensure no conflicts. The main backtracking happens in solve function, which tries placing a queen in each row of the current column, and if it’s safe, recursively solves for the next column. String slicing is used to place/remove queens from the board representation.
Dry Run
Let’s trace through: n = 4
graph TD
Root["solve(col=0, board=[...., ...., ...., ....], n=4)<br/>Place queens column by column"]
%% Level 0: col=0, try rows 0-3
Root --- A["Try row=0<br/>board=[Q..., ...., ...., ....]<br/>col=1"]
Root --- B["Try row=1<br/>board=[...., Q..., ...., ....]<br/>col=1"]
Root --- C["Try row=2<br/>board=[...., ...., Q..., ....]<br/>col=1"]
Root --- D["Try row=3<br/>board=[...., ...., ...., Q...]<br/>col=1"]
%% Level 1 from row=0: col=1, check safety for each row
A --- A1["Try row=0<br/>Unsafe: same row"]
A --- A2["Try row=1<br/>Unsafe: diagonal"]
A --- A3["Try row=2<br/>Safe!<br/>board=[Q..., ..Q., ...., ....]<br/>col=2"]
A --- A4["Try row=3<br/>Safe!<br/>board=[Q..., ...Q, ...., ....]<br/>col=2"]
%% Level 1 from row=1: col=1, check safety for each row
B --- B1["Try row=0<br/>Safe!<br/>board=[.Q.., Q..., ...., ....]<br/>col=2"]
B --- B2["Try row=1<br/>Unsafe: same row"]
B --- B3["Try row=2<br/>Unsafe: diagonal"]
B --- B4["Try row=3<br/>Safe!<br/>board=[...., Q..., ...., .Q..]<br/>col=2"]
%% Level 1 from row=2: col=1, similar pattern
C --- C1["Try row=0<br/>Safe!<br/>board=[.Q.., ...., Q..., ....]<br/>col=2"]
C --- C2["Try row=1<br/>Unsafe: diagonal"]
C --- C3["Try row=2<br/>Unsafe: same row"]
C --- C4["Try row=3<br/>Safe!<br/>board=[...., ...., Q..., .Q..]<br/>col=2"]
%% Level 1 from row=3: col=1, similar pattern
D --- D1["Try row=0<br/>Safe!<br/>board=[.Q.., ...., ...., Q...]<br/>col=2"]
D --- D2["Try row=1<br/>Safe!<br/>board=[...., .Q.., ...., Q...]<br/>col=2"]
D --- D3["Try row=2<br/>Unsafe: diagonal"]
D --- D4["Try row=3<br/>Unsafe: same row"]
%% Level 2 from A3: col=2, board=[Q..., ..Q., ...., ....]
A3 --- A3a["Try row=0<br/>Unsafe: same row as Q"]
A3 --- A3b["Try row=1<br/>Unsafe: diagonal conflict"]
A3 --- A3c["Try row=2<br/>Unsafe: same row as Q"]
A3 --- A3d["Try row=3<br/>Unsafe: diagonal conflict"]
A3d --- BacktrackA3["All unsafe - Backtrack"]
%% Level 2 from B1: col=2, board=[.Q.., Q..., ...., ....]
B1 --- B1a["Try row=0<br/>Unsafe: same row as Q"]
B1 --- B1b["Try row=1<br/>Unsafe: same row as Q"]
B1 --- B1c["Try row=2<br/>Unsafe: diagonal conflict"]
B1 --- B1d["Try row=3<br/>Safe!<br/>board=[.Q.., Q..., ..Q., ....]<br/>col=3"]
%% Level 2 from C1: col=2, board=[.Q.., ...., Q..., ....] - This leads to solution
C1 --- C1a["Try row=0<br/>Unsafe: same row as Q"]
C1 --- C1b["Try row=1<br/>Unsafe: diagonal conflict"]
C1 --- C1c["Try row=2<br/>Unsafe: same row as Q"]
C1d["Try row=3<br/>Safe!<br/>board=[.Q.., ...., Q..., ..Q.]<br/>col=3"]
C1 --- C1d
%% Level 3 from B1d: col=3, board=[.Q.., Q..., ..Q., ....]
B1d --- B1d1["Try row=0<br/>Safe!<br/>board=[.Q.., Q..., ..Q., ...Q]<br/>col=4"]
B1d --- B1d2["Try row=1<br/>Unsafe: same row as Q"]
B1d --- B1d3["Try row=2<br/>Unsafe: same row as Q"]
B1d --- B1d4["Try row=3<br/>Unsafe: diagonal conflict"]
%% Level 3 from C1d: col=3, board=[.Q.., ...., Q..., ..Q.]
C1d --- C1d1["Try row=0<br/>Unsafe: diagonal conflict"]
C1d --- C1d2["Try row=1<br/>Safe!<br/>board=[.Q.., .Q.., Q..., ..Q.]<br/>col=4"]
C1d --- C1d3["Try row=2<br/>Unsafe: same row as Q"]
C1d --- C1d4["Try row=3<br/>Unsafe: same row as Q"]
%% Base cases: col=4
B1d1 --- Fail1["col=4: Solution found but incorrect<br/>Actually conflicts - backtrack"]
C1d2 --- Success1["col=4 == n<br/>✅ Solution 1: ['.Q..', '...Q', 'Q...', '..Q.']"]
%% Continue exploring other paths for second solution
D1 --- D1Path["Similar exploration leads to<br/>✅ Solution 2: ['..Q.', 'Q...', '...Q', '.Q..']"]
%% Final result
Success1 --- Final["Final Result:<br/>[<br/> ['.Q..', '...Q', 'Q...', '..Q.'],<br/> ['..Q.', 'Q...', '...Q', '.Q..']<br/>]"]
D1Path --- Final
%% Styling
style Success1 fill:#90EE90
style D1Path fill:#90EE90
style Final fill:#90EE90
style A1 fill:#FFB6C1
style A2 fill:#FFB6C1
style B2 fill:#FFB6C1
style BacktrackA3 fill:#FFB6C1
style Fail1 fill:#FFB6C1
style A3 fill:#87CEEB
style B1 fill:#87CEEB
style C1 fill:#87CEEB
style B1d fill:#87CEEB
style C1d fill:#87CEEB
style Root fill:#E6E6FA
For detailed dry run [Click here]
Time and Space Complexity
- Time Complexity: O(N^N) – For each of the N^N possible ways to place N queens, we do O(N) safety checks
- Space Complexity: O(N^2) – Board storage plus O(N) recursion depth
Simplifying It
This approach is like being an extremely cautious chess player who, before placing each queen, carefully examines the entire board in all attack directions to make sure it’s completely safe. Very thorough, but time-consuming because you’re doing a lot of redundant checking.
Solution 2: Optimal Approach (Hash Sets for O(1) Conflict Detection)
Intuition
Instead of scanning the entire board every time we want to place a queen, what if we kept track of which rows and diagonals are already “occupied” by previous queens? It’s like having a smart notification system that instantly tells you if a position conflicts with existing queens, without having to look around the board. The key insight is that we can represent diagonals mathematically: upper-left to lower-right diagonals have the property that row - col is constant, while upper-right to lower-left diagonals have row + col constant.
Detailed Approach
- Use Hash Sets for Tracking: Maintain arrays/sets to track occupied:
- leftrow[row]: Track if row is occupied
- lowerDiagonal[row + col]: Track lower-left to upper-right diagonals
- upperDiagonal[n – 1 + col – row]: Track upper-left to lower-right diagonals
- Mathematical Diagonal Representation:
- Lower diagonal (↗): Points with same
row + colvalue are on same diagonal - Upper diagonal (↖): Points with same
row - colvalue are on same diagonal - Offset upper diagonal by
n-1to avoid negative indices
- Lower diagonal (↗): Points with same
- O(1) Safety Check: Just check if the three corresponding positions in our tracking arrays are free
- Update Tracking: When placing/removing queen, update all three tracking arrays
- Same Backtracking Structure: Column-by-column placement with backtracking
Code
class Solution:
def solve(self, col, board, ans, leftrow, upperDiagonal, lowerDiagonal, n):
# Base case: placed all queens successfully
if col == n:
ans.append(board[:]) # Make a copy of current board
return
# Try each row in current column
for row in range(n):
# O(1) safety check using our tracking arrays
if (
leftrow[row] == 0
and lowerDiagonal[row + col] == 0
and upperDiagonal[n - 1 + col - row] == 0
):
# Place queen and update all tracking arrays
board[row] = board[row][:col] + "Q" + board[row][col + 1 :]
leftrow[row] = 1
lowerDiagonal[row + col] = 1
upperDiagonal[n - 1 + col - row] = 1
# Recurse to next column
self.solve(
col + 1, board, ans, leftrow, upperDiagonal, lowerDiagonal, n
)
# Backtrack: remove queen and reset tracking arrays
board[row] = board[row][:col] + "." + board[row][col + 1 :]
leftrow[row] = 0
lowerDiagonal[row + col] = 0
upperDiagonal[n - 1 + col - row] = 0
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
board = ["." * n for _ in range(n)]
# Initialize tracking arrays
leftrow = [0] * n # Track occupied rows
upperDiagonal = [0] * (2 * n - 1) # Track upper diagonals
lowerDiagonal = [0] * (2 * n - 1) # Track lower diagonals
self.solve(0, board, ans, leftrow, upperDiagonal, lowerDiagonal, n)
return ansCode Explanation
This optimal solution eliminates the expensive O(N) safety checks by maintaining three tracking arrays. The clever part is the mathematical representation of diagonals: for any cell (row, col), row + col uniquely identifies its lower diagonal, and row - col (offset by n-1) uniquely identifies its upper diagonal. Before placing a queen, we just check three array positions in O(1) time. When placing/removing a queen, we update these arrays to reflect the new state. This transforms our expensive safety checks into simple array lookups.
Dry Run
Let’s trace through: n = 4
graph TD
Root["solve(col=0, board=[...., ...., ...., ....], n=4)<br/>leftrow=[0,0,0,0], upperDiag=[0,0,0,0,0,0,0], lowerDiag=[0,0,0,0,0,0,0]"]
%% Level 0: col=0, try rows 0-3
Root --- A["Try row=0<br/>Check: leftrow[0]=0 ✓, lowerDiag[0]=0 ✓, upperDiag[3]=0 ✓<br/>Place Q, mark arrays<br/>board=[Q..., ...., ...., ....]<br/>col=1"]
Root --- B["Try row=1<br/>Check: leftrow[1]=0 ✓, lowerDiag[1]=0 ✓, upperDiag[2]=0 ✓<br/>Place Q, mark arrays<br/>board=[...., Q..., ...., ....]<br/>col=1"]
Root --- C["Try row=2<br/>Check: leftrow[2]=0 ✓, lowerDiag[2]=0 ✓, upperDiag[1]=0 ✓<br/>Place Q, mark arrays<br/>board=[...., ...., Q..., ....]<br/>col=1"]
Root --- D["Try row=3<br/>Check: leftrow[3]=0 ✓, lowerDiag[3]=0 ✓, upperDiag[0]=0 ✓<br/>Place Q, mark arrays<br/>board=[...., ...., ...., Q...]<br/>col=1"]
%% Level 1 from row=0: col=1
A --- A1["Try row=0<br/>Check: leftrow[0]=1 ❌<br/>Skip - same row occupied"]
A --- A2["Try row=1<br/>Check: leftrow[1]=0 ✓, lowerDiag[2]=0 ✓, upperDiag[2]=0 ✓<br/>But upperDiag[2] conflicts with diagonal<br/>Actually safe! Place Q"]
A --- A3["Try row=2<br/>Check: leftrow[2]=0 ✓, lowerDiag[3]=0 ✓, upperDiag[1]=0 ✓<br/>Safe! board=[Q..., ..Q., ...., ....]<br/>col=2"]
A --- A4["Try row=3<br/>Check: leftrow[3]=0 ✓, lowerDiag[4]=0 ✓, upperDiag[0]=0 ✓<br/>Safe! board=[Q..., ...Q, ...., ....]<br/>col=2"]
%% Level 1 from row=1: col=1
B --- B1["Try row=0<br/>Check: leftrow[0]=0 ✓, lowerDiag[1]=0 ✓, upperDiag[4]=0 ✓<br/>Safe! board=[.Q.., Q..., ...., ....]<br/>col=2"]
B --- B2["Try row=1<br/>Check: leftrow[1]=1 ❌<br/>Skip - same row occupied"]
B --- B3["Try row=2<br/>Check: leftrow[2]=0 ✓, lowerDiag[3]=0 ✓, upperDiag[2]=0 ✓<br/>Skip - diagonal conflict"]
B --- B4["Try row=3<br/>Check: leftrow[3]=0 ✓, lowerDiag[4]=0 ✓, upperDiag[1]=0 ✓<br/>Safe! board=[...., Q..., ...., .Q..]<br/>col=2"]
%% Level 1 from row=2: col=1
C --- C1["Try row=0<br/>Check: leftrow[0]=0 ✓, lowerDiag[2]=0 ✓, upperDiag[5]=0 ✓<br/>Safe! board=[.Q.., ...., Q..., ....]<br/>col=2"]
C --- C2["Try row=1<br/>Check: leftrow[1]=0 ✓, lowerDiag[3]=0 ✓, upperDiag[4]=0 ✓<br/>Skip - diagonal conflict"]
C --- C3["Try row=2<br/>Check: leftrow[2]=1 ❌<br/>Skip - same row occupied"]
C --- C4["Try row=3<br/>Check: leftrow[3]=0 ✓, lowerDiag[5]=0 ✓, upperDiag[3]=0 ✓<br/>Skip - diagonal conflict"]
%% Level 1 from row=3: col=1
D --- D1["Try row=0<br/>Check: leftrow[0]=0 ✓, lowerDiag[3]=0 ✓, upperDiag[6]=0 ✓<br/>Safe! board=[.Q.., ...., ...., Q...]<br/>col=2"]
D --- D2["Try row=1<br/>Check: leftrow[1]=0 ✓, lowerDiag[4]=0 ✓, upperDiag[5]=0 ✓<br/>Safe! board=[...., .Q.., ...., Q...]<br/>col=2"]
D --- D3["Try row=2<br/>Check: leftrow[2]=0 ✓, lowerDiag[5]=0 ✓, upperDiag[4]=0 ✓<br/>Skip - diagonal conflict"]
D --- D4["Try row=3<br/>Check: leftrow[3]=1 ❌<br/>Skip - same row occupied"]
%% Level 2: Continue with valid paths
B1 --- B1_continue["Continue exploration...<br/>leads to path with conflicts"]
C1 --- C1d["Try row=3 at col=2<br/>Safe! board=[.Q.., ...., Q..., ..Q.]<br/>col=3"]
D1 --- D1_continue["Continue exploration...<br/>leads to first solution"]
%% Level 3 from C1d: col=3
C1d --- C1d2["Try row=1 at col=3<br/>Check all arrays - Safe!<br/>board=[.Q.., .Q.., Q..., ..Q.]<br/>col=4"]
D1_continue --- Solution1["col=4 == n<br/>✅ Solution 1: ['..Q.', 'Q...', '...Q', '.Q..']"]
%% Level 4 from C1d2: Base case
C1d2 --- Solution2["col=4 == n<br/>✅ Solution 2: ['.Q..', '...Q', 'Q...', '..Q.']"]
%% Final result
Solution1 --- Final["Final Result:<br/>[<br/> ['..Q.', 'Q...', '...Q', '.Q..'],<br/> ['.Q..', '...Q', 'Q...', '..Q.']<br/>]"]
Solution2 --- Final
%% Styling
style Solution1 fill:#90EE90
style Solution2 fill:#90EE90
style Final fill:#90EE90
style A1 fill:#FFB6C1
style B2 fill:#FFB6C1
style B3 fill:#FFB6C1
style C2 fill:#FFB6C1
style C3 fill:#FFB6C1
style C4 fill:#FFB6C1
style D3 fill:#FFB6C1
style D4 fill:#FFB6C1
style A3 fill:#87CEEB
style B1 fill:#87CEEB
style C1 fill:#87CEEB
style D1 fill:#87CEEB
style C1d fill:#87CEEB
style C1d2 fill:#87CEEB
style Root fill:#E6E6FA
For detailed dry run [Click here]
The tracking arrays instantly tell us conflicts without scanning the board!
Time and Space Complexity
- Time Complexity: O(N!) – Still exponential, but with much faster O(1) conflict detection
- Space Complexity: O(N) – Three tracking arrays plus O(N) recursion depth
Simplifying It
This approach is like having a smart assistant who keeps track of where all your queens are placed and can instantly tell you “Yes, that position is safe” or “No, that would create a conflict” without having to look at the board. The mathematical diagonal representation is the key insight that makes this instant lookup possible.
Summary
| Approach | Time | Space | Difficulty | Best For |
|---|---|---|---|---|
| Brute Force (Full Board Scan) | O(N^N) | O(N^2) | Medium | Understanding the problem |
| Optimal (Hash Set Tracking) | O(N!) | O(N) | Hard | Production code |
The optimal approach is dramatically better because it reduces conflict detection from O(N) to O(1), which compounds significantly over the exponential search space. The key insights are:
- Mathematical diagonal representation – Using
row ± colto uniquely identify diagonals - Constant-time conflict detection – Hash sets/arrays for O(1) lookups
- Smart state tracking – Update tracking arrays during backtracking
The N-Queens problem is a classic example of how the right data structures can transform an expensive operation (board scanning) into a cheap one (array lookup), leading to dramatic performance improvements in backtracking algorithms!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
