Problem Description

The n-queens puzzle asks you to place n queens on an n x n chessboard such that no two queens can attack each other.

In chess, a queen can attack any piece that is:

• In the same row
• In the same column
• On the same diagonal (both main diagonal and anti-diagonal)

Given an integer n, you need to find all possible valid arrangements of n queens on the board.

Each solution should be represented as a list of strings where:

• Each string represents one row of the chessboard
• 'Q' indicates a queen's position
• '.' indicates an empty square

For example, if n = 4, one valid solution would be:

[".Q..",
 "...Q",
 "Q...",
 "..Q."]

This represents a 4x4 board where queens are placed at positions (0,1), (1,3), (2,0), and (3,2), and no two queens can attack each other.

The function should return all distinct valid board configurations. The order of solutions doesn't matter.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves placing queens on a chessboard, not traversing nodes and edges in a graph structure.

Need to solve for kth smallest/largest?

• No: We're not looking for the kth smallest or largest element. We need to find all valid board configurations.

Involves Linked Lists?

• No: The problem uses a 2D board representation, not linked list data structures.

Does the problem have small constraints?

• Yes: The n-queens problem typically has small constraints (n is usually ≤ 15 in most cases). The problem requires exploring all possible queen placements, which grows exponentially with n. For small values of n, this is manageable.

Brute force / Backtracking?

• Yes: We need to systematically explore all possible queen placements. Backtracking is perfect here because:
  • We place queens one by one
  • If a placement leads to a conflict, we backtrack and try a different position
  • We need to find ALL valid solutions, not just one
  • The problem involves making choices (where to place each queen) and undoing them if they don't work

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This makes sense because we need to:

1. Try placing a queen in each possible position
2. Check if the placement is valid (no conflicts with other queens)
3. If valid, recursively place the next queen
4. If we reach a dead end, backtrack by removing the queen and trying the next position
5. Collect all valid complete board configurations

Intuition

When we think about placing queens on a chessboard, we need to ensure no two queens can attack each other. Since we need to place n queens on an n x n board, and queens can attack any piece in their row, we know that each row must contain exactly one queen.

This observation immediately simplifies our problem - instead of considering all possible positions on the board, we can process the board row by row, deciding which column to place the queen in for each row.

The key insight is that when we place a queen at position (i, j), it "blocks" certain positions for future queens:

• Column j is blocked for all subsequent rows
• The diagonal going through (i, j) is blocked
• The anti-diagonal going through (i, j) is blocked

To track these constraints efficiently, we can use a clever indexing trick:

• For columns: simply use index j
• For diagonals: cells on the same diagonal share the same value of i + j
• For anti-diagonals: cells on the same anti-diagonal share the same value of n - i + j (or i - j + n - 1)

This means we can use three arrays to mark which columns and diagonals are already occupied by queens.

The backtracking approach naturally emerges from this:

1. Start with row 0
2. Try placing a queen in each column of the current row
3. Check if the position is safe (column and both diagonals are free)
4. If safe, mark the position as occupied and move to the next row
5. If we successfully place queens in all rows, we found a solution
6. If we can't place a queen in any column of the current row, backtrack to the previous row and try the next column

The beauty of this approach is that by processing row by row, we automatically ensure no two queens are in the same row, and our tracking arrays ensure no conflicts in columns or diagonals.

Learn more about Backtracking patterns.

Solution Approach

The implementation uses a depth-first search (DFS) with backtracking to systematically explore all valid queen placements.

Data Structures Used:

• g: A 2D list representing the chessboard, initialized with all '.' (empty squares)
• col: An array of size n to track which columns have queens (col[j] = 1 if column j has a queen)
• dg: An array of size 2n for diagonal tracking (using index i + j)
• udg: An array of size 2n for anti-diagonal tracking (using index n - i + j)
• ans: List to store all valid board configurations

Core Algorithm - DFS Function:

The dfs(i) function places queens starting from row i:

1. Base Case: If i == n, we've successfully placed all n queens. Convert the current board state g into the required string format and add it to ans.

2. Recursive Case: For the current row i, try placing a queen in each column j from 0 to n-1:

   • Check if position is safe: Verify that col[j] + dg[i + j] + udg[n - i + j] == 0

     • This clever check ensures the column, diagonal, and anti-diagonal are all free (all values are 0)

   • Place the queen: If safe, update the board and tracking arrays:

     g[i][j] = "Q"
     col[j] = dg[i + j] = udg[n - i + j] = 1

   • Recurse: Call dfs(i + 1) to place queens in the next row

   • Backtrack: After recursion returns, restore the original state:

     col[j] = dg[i + j] = udg[n - i + j] = 0
     g[i][j] = "."

Why the Diagonal Indexing Works:

• Main diagonal (i + j): Points on the same diagonal from top-left to bottom-right have the same sum of coordinates. Range is [0, 2n-2].
• Anti-diagonal (n - i + j): Points on the same diagonal from top-right to bottom-left can be indexed this way. Adding n ensures all indices are positive, range is [1, 2n-1].

Time Complexity: O(n!) - In the worst case, we explore all possible placements. The first queen has n choices, the second has at most n-2, and so on.

Space Complexity: O(n) for the recursion stack depth, plus O(n²) for storing the board state.

The solution elegantly combines the constraint tracking with backtracking to efficiently find all valid n-queens configurations without redundant checks.

Example Walkthrough

Let's walk through solving the 4-queens problem step by step.

We start with a 4×4 board and need to place 4 queens. Our tracking arrays are:

• col[4] = [0,0,0,0] (tracks columns)
• dg[8] = [0,0,0,0,0,0,0,0] (tracks diagonals using i+j)
• udg[8] = [0,0,0,0,0,0,0,0] (tracks anti-diagonals using n-i+j)

Step 1: Row 0, Try column 0

• Check position (0,0): col[0]=0, dg[0+0]=0, udg[4-0+0]=0 ✓ All clear!
• Place queen at (0,0): Set col[0]=1, dg[0]=1, udg[4]=1
• Board state: Q...
• Move to row 1

Step 2: Row 1, Try columns

• Column 0: col[0]=1 ✗ (blocked by queen at row 0)
• Column 1: col[1]=0, dg[1+1]=0, udg[4-1+1]=1 ✗ (anti-diagonal blocked)
• Column 2: col[2]=0, dg[1+2]=0, udg[4-1+2]=0 ✓ All clear!
• Place queen at (1,2): Set col[2]=1, dg[3]=1, udg[5]=1
• Board state: Q... / ..Q.
• Move to row 2

Step 3: Row 2, Try columns

• Column 0: col[0]=1 ✗ (blocked)
• Column 1: col[1]=0, dg[2+1]=1 ✗ (diagonal blocked by queen at (1,2))
• Column 2: col[2]=1 ✗ (blocked)
• Column 3: col[3]=0, dg[2+3]=1 ✗ (diagonal blocked by queen at (1,2))
• No valid position! Backtrack to row 1

Step 4: Back to Row 1, continue from column 3

• Remove queen from (1,2): Reset col[2]=0, dg[3]=0, udg[5]=0
• Column 3: col[3]=0, dg[1+3]=0, udg[4-1+3]=0 ✓ All clear!
• Place queen at (1,3): Set col[3]=1, dg[4]=1, udg[6]=1
• Board state: Q... / ...Q

Step 5: Row 2, Try columns

• Column 0: col[0]=1 ✗
• Column 1: col[1]=0, dg[2+1]=0, udg[4-2+1]=0 ✓ All clear!
• Place queen at (2,1): Set col[1]=1, dg[3]=1, udg[3]=1
• Board state: Q... / ...Q / .Q..

Step 6: Row 3, Try columns

• Column 0: col[0]=1 ✗
• Column 1: col[1]=1 ✗
• Column 2: col[2]=0, dg[3+2]=0, udg[4-3+2]=1 ✗ (anti-diagonal blocked)
• Column 3: col[3]=1 ✗
• No valid position! Backtrack to row 2

This process continues, exploring different combinations through backtracking. Eventually, we find a valid solution when:

• Queen at (0,1): col[1]=1, dg[1]=1, udg[5]=1
• Queen at (1,3): col[3]=1, dg[4]=1, udg[6]=1
• Queen at (2,0): col[0]=1, dg[2]=1, udg[2]=1
• Queen at (3,2): col[2]=1, dg[5]=1, udg[3]=1

Final solution:

.Q..
...Q
Q...
..Q.

The algorithm continues this backtracking process until all possibilities are explored, finding both solutions for the 4-queens problem.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × n!)

The algorithm uses backtracking to explore all possible queen placements. For each valid solution found, there are several operations:

• The recursive function dfs explores at most n! valid board configurations (upper bound on the number of ways to place n queens)
• At each recursive level i, we iterate through n columns to try placing a queen
• When a complete solution is found (i == n), we construct the answer by iterating through the n × n board, which takes O(n²) time
• The total time complexity is O(n × n!) for exploring all configurations, but since we need O(n²) time to construct each solution, the overall complexity becomes O(n² × n!)

Space Complexity: O(n)

The space usage consists of:

• The recursion stack depth is at most n (one recursive call per row): O(n)
• The col array of size n: O(n)
• The dg (diagonal) array of size 2n: O(n)
• The udg (anti-diagonal) array of size 2n: O(n)
• The board g is n × n: O(n²)
• The answer list ans stores the solutions but is not counted in auxiliary space complexity

While the board g takes O(n²) space, the reference answer considers O(n) as the space complexity, likely focusing on the auxiliary space used by the recursion stack and tracking arrays, excluding the space needed to store the input/output representation.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Diagonal Indexing Formula

Pitfall: One of the most common mistakes is using incorrect formulas for diagonal indexing, such as:

• Using row - col for diagonals (which can produce negative indices)
• Using row + col + n for anti-diagonals (which wastes array space)
• Mixing up the formulas for diagonals and anti-diagonals

Why it happens: The diagonal indexing is counterintuitive. Without understanding why row + col and n - row + col work, developers often guess at formulas.

Solution:

• For main diagonals (↘): Use row + col. Points on the same diagonal have the same sum.
• For anti-diagonals (↙): Use n - row + col or row - col + n - 1. The offset ensures all indices are non-negative.
• Draw a small grid and verify your indexing manually before coding.

2. Forgetting to Backtrack Properly

Pitfall: Failing to reset the state after exploring a branch:

# Incorrect - forgetting to reset the board
board[row][col] = "Q"
columns_used[col] = 1
diagonals_used[row + col] = 1
anti_diagonals_used[n - row + col] = 1
backtrack(row + 1)
# Missing the backtrack step!

Why it happens: It's easy to focus on the forward recursion and forget that backtracking requires undoing changes.

Solution: Always ensure every state change has a corresponding reset:

# Place queen
board[row][col] = "Q"
columns_used[col] = 1
diagonals_used[row + col] = 1
anti_diagonals_used[n - row + col] = 1

# Explore
backtrack(row + 1)

# Backtrack - undo all changes in reverse order
anti_diagonals_used[n - row + col] = 0
diagonals_used[row + col] = 0
columns_used[col] = 0
board[row][col] = "."

3. Creating Board Representation Incorrectly

Pitfall: Creating the board with shared references:

# Incorrect - all rows reference the same list!
board = [["."] * n] * n

# When you modify board[0][0], all board[i][0] change

Why it happens: Python's list multiplication creates references, not copies, for mutable objects.

Solution: Use list comprehension to create independent rows:

# Correct - each row is a separate list
board = [["."] * n for _ in range(n)]

4. Converting Board to Output Format Incorrectly

Pitfall: Forgetting to create a deep copy of the board state when saving solutions:

# Incorrect - appending references to the same board
if row == n:
    results.append(board)  # This saves a reference, not a copy!

Why it happens: The board array is reused throughout the recursion. Saving references means all solutions will show the final board state.

Solution: Convert the board to strings immediately when saving:

# Correct - create new string representations
if row == n:
    solution = ["".join(row_chars) for row_chars in board]
    results.append(solution)

5. Off-by-One Errors in Array Sizing

Pitfall: Incorrectly sizing the tracking arrays:

# Incorrect - too small for diagonal tracking
diagonals_used = [0] * n  # Should be 2*n
anti_diagonals_used = [0] * n  # Should be 2*n

Why it happens: Not calculating the maximum possible index values. For an n×n board:

• row + col ranges from 0 to 2n-2
• n - row + col ranges from 1 to 2n-1

Solution: Always allocate 2*n elements for diagonal tracking arrays to safely cover all possible indices:

diagonals_used = [0] * (2 * n)
anti_diagonals_used = [0] * (2 * n)