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
