0052. N 皇后 II #
- 标签:回溯
- 难度:困难
题目大意 #
描述:给定一个整数 n
。
要求:返回「n
皇后问题」不同解决方案的数量。
说明:
- n 皇后问题:将
n
个皇后放置在n * n
的棋盘上,并且使得皇后彼此之间不能攻击。 - 皇后彼此不能相互攻击:指的是任何两个皇后都不能处于同一条横线、纵线或者斜线上。
- $1 \le n \le 9$。
示例:
- 示例 1:
|
|
解题思路 #
思路 1:回溯算法 #
和「 51. N 皇后 - 力扣」做法一致。区别在于「 51. N 皇后 - 力扣」需要返回所有解决方案,而这道题只需要得到所有解决方案的数量即可。下面来说一下这道题的解题思路。
我们可以按照行序来放置皇后,也就是先放第一行,再放第二行 …… 一直放到最后一行。
对于 n * n
的棋盘来说,每一行有 n
列,也就有 n
种放法可供选择。我们可以尝试选择其中一列,查看是否与之前放置的皇后有冲突,如果没有冲突,则继续在下一行放置皇后。依次类推,直到放置完所有皇后,并且都不发生冲突时,就得到了一个合理的解。
并且在放置完之后,通过回溯的方式尝试其他可能的分支。
下面我们根据回溯算法三步走,写出对应的回溯算法。
-
明确所有选择:根据棋盘中当前行的所有列位置上是否选择放置皇后,画出决策树,如下图所示。
-
-
明确终止条件:
- 当遍历到决策树的叶子节点时,就终止了。也就是在最后一行放置完皇后时,递归终止。
-
将决策树和终止条件翻译成代码:
-
定义回溯函数:
- 首先我们先使用一个
n * n
大小的二维矩阵chessboard
来表示当前棋盘,chessboard
中的字符Q
代表皇后,.
代表空位,初始都为.
。 - 然后定义回溯函数
backtrack(chessboard, row):
函数的传入参数是chessboard
(棋盘数组)和row
(代表当前正在考虑放置第row
行皇后),全局变量是ans
(所有可行方案的数量)。 backtrack(chessboard, row):
函数代表的含义是:在放置好第row
行皇后的情况下,递归放置剩下行的皇后。
- 首先我们先使用一个
-
书写回溯函数主体(给出选择元素、递归搜索、撤销选择部分)。
- 枚举出当前行所有的列。对于每一列位置:
- 约束条件:定义一个判断方法,先判断一下当前位置是否与之前棋盘上放置的皇后发生冲突,如果不发生冲突则继续放置,否则则继续向后遍历判断。
- 选择元素:选择
row, col
位置放置皇后,将其棋盘对应位置设置为Q
。 - 递归搜索:在该位置放置皇后的情况下,继续递归考虑下一行。
- 撤销选择:将棋盘上
row, col
位置设置为.
。
- 枚举出当前行所有的列。对于每一列位置:
-
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n!)$,其中 $n$ 是皇后数量。
- 空间复杂度:$O(n^2)$,其中 $n$ 是皇后数量。递归调用层数不会超过 $n$,每个棋盘的空间复杂度为 $O(n^2)$,所以空间复杂度为 $O(n^2)$。