#52

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

N-Queens II

Solve the N-Queens II problem using backtracking with pruning to efficiently count all valid placements for n queens on a chessboard.

backtracking

Problem Statement

The N-Queens II problem involves placing n queens on an n x n chessboard so that no two queens threaten each other. You must return the number of distinct solutions where each solution consists of n queens positioned on the board.

The challenge is to find all possible ways to place the queens such that no two queens share the same row, column, or diagonal. For example, when n = 4, there are two distinct solutions. Your task is to determine the number of solutions for any value of n within the constraint 1 <= n <= 9.

Examples

Example 1

Input: n = 4

Output: 2

There are two distinct solutions to the 4-queens puzzle as shown.

Example 2

Input: n = 1

Output: 1

Example details omitted.

Constraints

1 <= n <= 9

Solution Approach

Backtracking with Pruning

To solve the problem, use backtracking to place queens row by row. At each step, check whether placing a queen in a particular position is safe by ensuring that no other queen is in the same column or diagonal. Prune invalid paths early by skipping placements that violate the constraints.

Column, Diagonal Tracking

Utilize additional data structures to track which columns and diagonals are under attack. This allows for constant-time checks when placing a queen, ensuring that you don't revisit invalid solutions. This tracking minimizes unnecessary re-evaluations, making the backtracking process more efficient.

Iterative Search and Count

As you place queens on the board, continue the search recursively. Each time a valid configuration is found (i.e., all queens are placed safely), increment the count of solutions. Once all rows are filled, a valid configuration is found, and the search backtracks to explore other possibilities.

Complexity Analysis

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

The time complexity depends on the implementation and the pruning effectiveness, but it is generally exponential with respect to n. The space complexity depends on the data structures used for tracking columns and diagonals, but it can be managed to O(n). The pruning optimizations help reduce the number of recursive calls made during the backtracking process, improving the overall efficiency.

What Interviewers Usually Probe

Does the candidate show an understanding of the backtracking approach and pruning?
Can they efficiently explain the significance of using tracking arrays for columns and diagonals?
Are they aware of the time complexity implications of backtracking solutions?

Common Pitfalls or Variants

Common pitfalls

Failing to prune invalid solutions early, leading to unnecessary exploration of invalid configurations.
Overcomplicating the tracking of columns and diagonals, which can slow down the backtracking process.
Not accounting for all possible board configurations and missing edge cases, such as n = 1.

Follow-up variants

Increasing the board size beyond n = 9 introduces more computational complexity.
Changing the problem to return all solutions instead of just counting them requires storing all valid configurations.
Allowing some queens to attack others (modified constraint) would change the approach significantly.

FAQ

How do I solve N-Queens II efficiently?

Use backtracking combined with pruning to reduce unnecessary checks. Track columns and diagonals to ensure each queen placement is valid.

What is the time complexity of the N-Queens II problem?

The time complexity is exponential, typically O(n!), but can be improved with pruning and efficient tracking of attacked columns and diagonals.

What should I avoid when solving N-Queens II?

Avoid unnecessary recursive calls by pruning invalid configurations early. Also, ensure that you manage column and diagonal tracking properly.

What is the primary pattern for solving N-Queens II?

The primary pattern is backtracking with pruning, where invalid configurations are pruned early to minimize unnecessary computations.

Can I apply N-Queens II to larger board sizes?

While the problem is solvable for n up to 9, larger board sizes increase computational complexity significantly. Efficient backtracking and pruning are essential to managing this growth.

terminal

Solution

Solution 1: Backtracking

We design a function $dfs(i)$, which represents starting the search from the $i$th row, and the results of the search are added to the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def totalNQueens(self, n: int) -> int:
        def dfs(i: int):
            if i == n:
                nonlocal ans
                ans += 1
                return
            for j in range(n):
                a, b = i + j, i - j + n
                if cols[j] or dg[a] or udg[b]:
                    continue
                cols[j] = dg[a] = udg[b] = True
                dfs(i + 1)
                cols[j] = dg[a] = udg[b] = False

        cols = [False] * 10
        dg = [False] * 20
        udg = [False] * 20
        ans = 0
        dfs(0)
        return ans

Continue Practicing

#51 n queens #47 permutations ii #46 permutations