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.

#52

Hard

auto_awesome回溯·pruning

LeetCode 题解工作台

N 皇后 II

n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回 n 皇后问题不同的解决方案的数量。示例 1：输入： n = 4 输出： 2 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：输入： n = 1 输…

回溯

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 9

lightbulb

解题思路

方法一：回溯

我们设计一个函数 $dfs(i)$ ，表示从第 $i$ 行开始搜索，搜索到的结果累加到答案中。

在第 $i$ 行，我们枚举第 $i$ 行的每一列，如果当前列不与前面已经放置的皇后发生冲突，那么我们就可以放置一个皇后，然后继续搜索下一行，即调用 $dfs(i + 1)$ 。

如果发生冲突，那么我们就跳过当前列，继续枚举下一列。

判断是否发生冲突，我们需要用三个数组分别记录每一列、每一条正对角线、每一条反对角线是否已经放置了皇后。

具体地，我们用 $cols$ 数组记录每一列是否已经放置了皇后，用 $dg$ 数组记录每一条正对角线是否已经放置了皇后，用 $udg$ 数组记录每一条反对角线是否已经放置了皇后。

时间复杂度 $O(n!)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是皇后的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#51 N 皇后 #47 全排列 II #46 全排列