标签: 回溯
难度: Hard
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 9
Submission
运行时间: 120 ms
内存: 15.3 MB
class Solution:
def totalNQueens(self, n: int) -> int:
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 len(ans)
Explain
这道题使用回溯算法求解。从第一行开始，尝试在每一列放置皇后，并检查是否与已经放置的皇后冲突。如果当前放置的皇后不与之前的皇后冲突，则继续放置下一行的皇后；否则，回溯到上一行，尝试将皇后放置在其他列。当所有的皇后都成功放置时，将当前的棋盘状态加入答案数组。最后返回答案数组的长度即为不同的解决方案的数量。
时间复杂度: O(n^(n+1))
空间复杂度: O(n)
```python
class Solution:
def totalNQueens(self, n: int) -> int:
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: # 如果已经放置了 n 个皇后，将当前棋盘状态加入答案数组
ans.append([".".join(line) for line in board])
return
for j in range(n): # 尝试在第 i 行的每一列放置皇后
if not is_valid(i, j): # 如果当前位置不合法，跳过
continue
board[i][j] = 'Q' # 在当前位置放置皇后
backtrack(i+1) # 递归放置下一行的皇后
board[i][j] = '.' # 回溯，撤销当前位置的皇后
backtrack(0) # 从第 0 行开始放置皇后
return len(ans) # 返回解的数量
```
Explore
在N皇后问题的解法中，通过维护棋盘状态和对棋盘的检查来确定哪些列和对角线已被攻击。具体方法是，对于要放置新的皇后的每个位置，通过遍历棋盘之前的行来检查三个方向：1. 列方向：向上遍历每一行同列的位置，看是否已有皇后；2. 左上对角线：从当前位置开始，向左上方向检查每个对角线位置是否有皇后；3. 右上对角线：从当前位置开始，向右上方向检查每个对角线位置是否有皇后。这三个方向的检查确保了任何新放置的皇后不会与已放置的皇后在同一列或对角线上。
在N皇后问题的回溯解法中，皇后是从棋盘的第一行开始依次向下放置的，因此在放置每一行的皇后时，其下方的行还没有放置任何皇后，所以不需要检查下方及左下、右下对角线的冲突。这是因为冲突只可能发生在已经放置了皇后的行的上方，包括直线和对角线方向。
在递归函数`backtrack`中，参数`i`代表当前正在尝试放置皇后的行号。当`i == n`时，意味着已经成功地在棋盘的前`n`行每一行都放置了一个皇后，并且所有皇后互不冲突。这时递归到达退出条件，因为已经没有更多的行需要放置皇后，表示找到了一个有效的解决方案。此时递归回溯，寻找可能的其他解决方案。