0052. N皇后 II

0052. N皇后 II #

  • 标签:回溯
  • 难度:困难

题目大意 #

描述:给定一个整数 n

要求:返回「n 皇后问题」不同解决方案的数量。

说明

  • n 皇后问题:将 n 个皇后放置在 n * n 的棋盘上,并且使得皇后彼此之间不能攻击。
  • 皇后彼此不能相互攻击:指的是任何两个皇后都不能处于同一条横线、纵线或者斜线上。
  • $1 \le n \le 9$。

示例

1
2
3
输入n = 4
输出2
解释如下图所示4 皇后问题存在两个不同的解法

解题思路 #

思路 1:回溯算法 #

和「 51. N 皇后 - 力扣」做法一致。区别在于「 51. N 皇后 - 力扣」需要返回所有解决方案,而这道题只需要得到所有解决方案的数量即可。下面来说一下这道题的解题思路。

我们可以按照行序来放置皇后,也就是先放第一行,再放第二行 …… 一直放到最后一行。

对于 n * n 的棋盘来说,每一行有 n 列,也就有 n 种放法可供选择。我们可以尝试选择其中一列,查看是否与之前放置的皇后有冲突,如果没有冲突,则继续在下一行放置皇后。依次类推,直到放置完所有皇后,并且都不发生冲突时,就得到了一个合理的解。

并且在放置完之后,通过回溯的方式尝试其他可能的分支。

下面我们根据回溯算法三步走,写出对应的回溯算法。

  1. 明确所有选择:根据棋盘中当前行的所有列位置上是否选择放置皇后,画出决策树,如下图所示。

  2. 明确终止条件

    • 当遍历到决策树的叶子节点时,就终止了。也就是在最后一行放置完皇后时,递归终止。
  3. 将决策树和终止条件翻译成代码:

    1. 定义回溯函数:

      • 首先我们先使用一个 n * n 大小的二维矩阵 chessboard 来表示当前棋盘,chessboard 中的字符 Q 代表皇后,. 代表空位,初始都为 .
      • 然后定义回溯函数 backtrack(chessboard, row): 函数的传入参数是 chessboard(棋盘数组)和 row(代表当前正在考虑放置第 row 行皇后),全局变量是 ans(所有可行方案的数量)。
      • backtrack(chessboard, row): 函数代表的含义是:在放置好第 row 行皇后的情况下,递归放置剩下行的皇后。
    2. 书写回溯函数主体(给出选择元素、递归搜索、撤销选择部分)。

      • 枚举出当前行所有的列。对于每一列位置:
        • 约束条件:定义一个判断方法,先判断一下当前位置是否与之前棋盘上放置的皇后发生冲突,如果不发生冲突则继续放置,否则则继续向后遍历判断。
        • 选择元素:选择 row, col 位置放置皇后,将其棋盘对应位置设置为 Q
        • 递归搜索:在该位置放置皇后的情况下,继续递归考虑下一行。
        • 撤销选择:将棋盘上 row, col 位置设置为 .

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    # 判断当前位置 row, col 是否与之前放置的皇后发生冲突
    def isValid(self, n: int, row: int, col: int, chessboard: List[List[str]]):
        for i in range(row):
            if chessboard[i][col] == 'Q':
                return False

        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if chessboard[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if chessboard[i][j] == 'Q':
                return False
            i -= 1
            j += 1

        return True

    def totalNQueens(self, n: int) -> int:
        chessboard = [['.' for _ in range(n)] for _ in range(n)]    # 棋盘初始化
        
        ans = 0
        def backtrack(chessboard: List[List[str]], row: int):                     # 正在考虑放置第 row 行的皇后
            if row == n:                                    # 遇到终止条件
                nonlocal ans
                ans += 1
                return

            for col in range(n):                            # 枚举可放置皇后的列
                if self.isValid(n, row, col, chessboard):   # 如果该位置与之前放置的皇后不发生冲突
                    chessboard[row][col] = 'Q'              # 选择 row, col 位置放置皇后
                    backtrack(chessboard, row + 1)          # 递归放置 row + 1 行之后的皇后
                    chessboard[row][col] = '.'              # 撤销选择 row, col 位置

        backtrack(chessboard, 0)

        return ans

思路 1:复杂度分析 #

  • 时间复杂度:$O(n!)$,其中 $n$ 是皇后数量。
  • 空间复杂度:$O(n^2)$,其中 $n$ 是皇后数量。递归调用层数不会超过 $n$,每个棋盘的空间复杂度为 $O(n^2)$,所以空间复杂度为 $O(n^2)$。
本站总访问量  次  |  您是本站第  位访问者