难度: Hard
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
提示：
1 <= n <= 9运行时间: 120 ms
内存: 15.4 MB
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
board = [['.']*n for _ in range(n)]
def is_valid(row, col):
n = len(board)
for i in range(n):
if board[i][col] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
if board[i][j] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 'Q':
return False
return True
def backtrack(i):
if i == n:
ans.append(["".join(line) for line in board])
return
for j in range(n):
if not is_valid(i, j):
continue
board[i][j] = 'Q'
backtrack(i+1)
board[i][j] = '.'
backtrack(0)
return ans
这个题解使用回溯算法来解决 N 皇后问题。基本思路是：从第一行开始，尝试在每一列放置皇后。放置之前，需要检查当前位置是否会被之前放置的皇后攻击到。如果当前位置合法，就将皇后放在当前位置，然后递归到下一行继续放置皇后。如果当前行的所有列都尝试完毕，就回溯到上一行，将上一行的皇后挪到下一列，然后继续尝试。当所有行都放置了皇后，就找到了一个合法的解，将当前棋盘状态记录到答案中。
时间复杂度: O(n^n)
空间复杂度: O(n!)
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
board = [['.']*n for _ in range(n)] # 初始化空棋盘
def is_valid(row, col):
n = len(board)
# 检查当前列是否有皇后冲突
for i in range(n):
if board[i][col] == 'Q':
return False
# 检查右上方是否有皇后冲突
for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
if board[i][j] == 'Q':
return False
# 检查左上方是否有皇后冲突
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 'Q':
return False
return True
def backtrack(i):
if i == n: # 找到一个合法解
ans.append(["".join(line) for line in board])
return
for j in range(n):
if not is_valid(i, j): # 当前位置不合法，跳过
continue
board[i][j] = 'Q' # 放置皇后
backtrack(i+1) # 递归到下一行
board[i][j] = '.' # 回溯，撤销皇后
backtrack(0) # 从第一行开始放置皇后
return ans
在回溯过程中，算法是逐行放置皇后的，每次放置皇后时都是在新的一行。因此，当尝试在某一行放置皇后时，该行上还没有其他皇后，所以不需要检查当前行是否存在冲突。
函数`is_valid`中只检查了右上方和左上方的冲突，是因为算法是从第一行到最后一行逐行放置皇后的。当放置到某一行的某一列时，该位置下方的行还没有放置皇后，因此不需要检查右下方和左下方的冲突。只有之前已经放置的行的皇后位置可能会对当前位置产生影响，所以只检查了上方和两个对角线方向的上半部分。
尽管在找到一个合法的解之后可以记录下这个解，但我们的目标是找到所有可能的解决方案。回溯操作使得算法可以撤销当前行的皇后放置，回到上一行尝试其他可能的列位置，从而探索所有可能的棋盘配置。如果直接终止递归，那么就只能找到一个解，无法完成寻找所有解的目标。
如果在某一行中所有列都不合法，那么函数`backtrack`会通过所有的列循环而不进行任何操作（因为所有的`is_valid`调用都会返回`False`），然后函数自然结束，控制权返回到上一层递归。在上一层递归中，会继续尝试下一个可能的列位置（即进行回溯），如果上一行也没有合法的位置，这种回溯将继续向上递归，直到找到一个可以改变的位置，或者所有可能都尝试完毕。