1 题目
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
2 解析
为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合columns、diagonals1 和diagonals 2，分别记录每一列以及两个方向的每条斜线上是否有皇后。列的表示法很直观，一共有 NN 列，每一列的下标范围从 00 到 N-1N−1，使用列的下标即可明确表示每一列。如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0)(0,0) 和 (3,3)(3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。
3 Python实现
class Solution: def solveNQueens(self, n: int) -> List[List[str]]: # 根据皇后的位置生成一行棋盘布局 # queens 保存的是皇后的位置 def generateBoard(): board = [] for i in range(n): row[queens[i]] = 'Q' board.append(''.join(row)) row[queens[i]]='.' return board def backtrack(row): # 一行一行的遍历，放置皇后，并生成一行的棋盘布局 if row==n: board = generateBoard() solutions.append(board) else: # 判断不是皇后位置的条件 for i in range(n): if i in columns or row-i in diagonal1 or row+i in diagonal2: continue # 记录可以放置皇后的位置 queens[row] = i # 记录一行 columns.add(i) # 记录东南斜方向 diagonal1.add(row-i) # 记录西南斜方向 diagonal2.add(row+i) backtrack(row+1) # 回溯 columns.remove(i) diagonal1.remove(row-i) diagonal2.remove(row+i) solutions = [] queens = [-1]*n columns = set() diagonal1 = set() diagonal2 = set() row = ['.']*n backtrack(0) return solutions
