按照國際象棋的規則，皇後可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
n 皇後問題 研究的是如何將 n 個皇後放置在 n×n 的棋盤上，並且使皇後彼此之間不能相互攻擊。
給你一個整數 n ，返回所有不同的 n 皇後問題 的解決方案。
每一種解法包含一個不同的 n 皇後問題 的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇後和空位。
示例 1：
輸入：n = 4
輸出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解釋：如上圖所示，4 皇後問題存在兩個不同的解法。
為了判斷一個位置所在的列和兩條斜線上是否已經有皇後，使用三個集合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) 在同一條方向二的斜線上。因此使用行下標與列下標之和即可明確表示每一條方向二的斜線。
每次放置皇後時，對於每個位置判斷其是否在三個集合中，如果三個集合都不包含當前位置，則當前位置是可以放置皇後的位置。
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
