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 board def 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] = col columns.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, ['.'] * n columns, diagonal1, diagonal2 = set(), set(), set() backtrack(0) return solutions

复杂度分析

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

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

Alex 007 认证博客专家 机器学习 NLP TensorFlow 我是 Alex 007，一个热爱计算机编程和硬件设计的小白。为啥是007呢？因为叫 Alex 的人太多了，再加上每天007的生活，Alex 007就诞生了。如果你喜欢我的文章的话，给个三连吧！