51. N-Queens N 皇后

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

上图为 8 皇后问题的一种解法。

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 

示例：

输入：4 输出：[[".Q..", // 解法 1"...Q","Q...","..Q."],["..Q.", // 解法 2"Q...","...Q",".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。

 

提示：

• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

基于集合的回溯

为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 $\text{columns}$、diagonals1\textit{diagonals}_1diagonals1​ 和 diagonals2\textit{diagonals}_2diagonals2​ 分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 $N$ 列，每一列的下标范围从 $0$ 到 $N-1$，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。

方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 $(0,0)$ 和 $(3,3)$ 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 $(3,0)$ 和 $(1,2)$ 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

Code

def solveNQueens(self, n: int) -> List[List[str]]:def generateBoard():board = list()for i in range(n):rows[queues[i]] = 'Q'board.append("".join(rows))rows[queues[i]] = '.'return boarddef backtrack(row: int):if row == n:board = generateBoard()solutions.append(board)else:for col in range(n):if not (col in columns or row - col in diagonal1 or row + col in diagonal2):queues[row] = colcolumns.add(col)diagonal1.add(row - col)diagonal2.add(row + col)backtrack(row + 1)columns.remove(col)diagonal1.remove(row - col)diagonal2.remove(row + col)solutions, queues, rows = list(), [-1] * n, ['.'] * ncolumns, diagonal1, diagonal2 = set(), set(), set()backtrack(0)return solutions

复杂度分析

• 时间复杂度：$O(N!)$，其中 $N$ 是皇后数量。

• 空间复杂度：$O(N)$，其中 $N$ 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 $N$，数组的长度为 $N$，每个集合的元素个数都不会超过 $N$。

总结

以上是生活随笔为你收集整理的51. N-Queens N 皇后的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。