#51

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

N-Queens

Solve the N-Queens problem using backtracking with pruning, exploring all valid board placements while avoiding conflicts efficiently.

array backtracking

Problem Statement

The N-Queens problem requires placing n queens on an n x n chessboard such that no two queens threaten each other. Each queen occupies a unique row, column, and diagonal.

Given an integer n, return all distinct board configurations representing valid N-Queens placements. Each configuration uses 'Q' for a queen and '.' for empty spaces, in any order.

Examples

Example 1

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2

Input: n = 1

Output: [["Q"]]

Example details omitted.

Constraints

1 <= n <= 9

Solution Approach

Backtracking with Row-by-Row Placement

Place queens row by row and recursively attempt placements in valid columns. If a conflict is detected, backtrack immediately to prune the search space.

Track Column and Diagonal Conflicts

Maintain sets for columns, diagonals, and anti-diagonals to detect conflicts in O(1). This ensures invalid placements are skipped quickly, preventing wasted recursion.

Construct and Collect Board Configurations

Once a valid placement reaches the last row, convert the positions into a board of strings and append to results. Repeat until all possibilities are explored.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity grows exponentially with n due to backtracking, approximately O(n!), but pruning reduces unnecessary recursive calls. Space complexity is O(n) for tracking columns and diagonals plus O(n) per board for storing solutions.

What Interviewers Usually Probe

Check if the candidate prunes branches early using column and diagonal tracking.
Look for clean recursion and backtracking structure without redundant iterations.
Confirm candidate can generate all distinct board arrangements correctly.

Common Pitfalls or Variants

Common pitfalls

Not handling diagonal conflicts correctly, leading to invalid placements.
Modifying the board in place without restoring state during backtracking.
Failing to return results in the required board string format with 'Q' and '.'.

Follow-up variants

Return only the count of N-Queens solutions instead of full board configurations.
Solve for N-Queens II with restricted pre-placed queens in some rows.
Adapt the solution to k-Queens on an m x n board with k <= min(m,n).

FAQ

What is the N-Queens problem pattern used in GhostInterview?

It is a backtracking search with pruning, placing queens row by row while tracking columns and diagonals to skip invalid paths.

How does GhostInterview handle large n values?

It efficiently prunes invalid paths using column and diagonal sets, but practical performance is best for n up to 9 due to exponential growth.

Can the solution return the board in any order?

Yes, GhostInterview generates all valid configurations, and the order of solutions does not affect correctness.

Why is backtracking necessary for N-Queens?

Backtracking systematically explores possibilities while pruning invalid paths, avoiding redundant or conflicting queen placements.

What common mistakes should I avoid when coding N-Queens?

Avoid missing diagonal checks, failing to restore board state during recursion, and returning incorrectly formatted board strings.

terminal

Solution

Solution 1: DFS (Backtracking)

We define three arrays $col$, $dg$, and $udg$ to represent whether there is a queen in the column, the main diagonal, and the anti-diagonal, respectively. If there is a queen at position $(i, j)$, then $col[j]$, $dg[i + j]$, and $udg[n - i + j]$ are all $1$. In addition, we use an array $g$ to record the current state of the chessboard, where all elements in $g$ are initially `'.'`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def dfs(i: int):
            if i == n:
                ans.append(["".join(row) for row in g])
                return
            for j in range(n):
                if col[j] + dg[i + j] + udg[n - i + j] == 0:
                    g[i][j] = "Q"
                    col[j] = dg[i + j] = udg[n - i + j] = 1
                    dfs(i + 1)
                    col[j] = dg[i + j] = udg[n - i + j] = 0
                    g[i][j] = "."

        ans = []
        g = [["."] * n for _ in range(n)]
        col = [0] * n
        dg = [0] * (n << 1)
        udg = [0] * (n << 1)
        dfs(0)
        return ans

Continue Practicing

#47 permutations ii #46 permutations #40 combination sum ii