回溯——12.N皇后

力扣题目链接

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

解题思路

1. 回溯法：这是一个典型的回溯问题，我们需要尝试在棋盘上放置皇后，并不断尝试不同的放置方式，如果发现当前放置不合法，则回退（回溯）到上一步，继续尝试其他可能的放置方式。
2. 合法性检查：为了确保皇后之间不互相攻击，每次放置新的皇后时，需要检查该位置是否与之前放置的皇后冲突。主要检查三个方向：同一列、左上对角线和右上对角线。

完整代码如下：

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:result = []  # 存储最终结果的二维字符串数组chessboard = ['.' * n for _ in range(n)]  # 初始化棋盘self.backtracking(n, 0, chessboard, result)  # 回溯求解return [[''.join(row) for row in solution] for solution in result]  # 返回结果集def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:if row == n:result.append(chessboard[:])  # 棋盘填满，将当前解加入结果集returnfor col in range(n):if self.isValid(row, col, chessboard):chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]  # 放置皇后self.backtracking(n, row + 1, chessboard, result)  # 递归到下一行chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]  # 回溯，撤销当前位置的皇后def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:# 检查列for i in range(row):if chessboard[i][col] == 'Q':return False  # 当前列已经存在皇后，不合法# 检查 45 度角是否有皇后i, j = row - 1, col - 1while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return False  # 左上方向已经存在皇后，不合法i -= 1j -= 1# 检查 135 度角是否有皇后i, j = row - 1, col + 1while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return False  # 右上方向已经存在皇后，不合法i -= 1j += 1return True  # 当前位置合法

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:result = []  # 存储最终结果的二维字符串数组chessboard = ['.' * n for _ in range(n)]  # 初始化棋盘self.backtracking(n, 0, chessboard, result)  # 回溯求解return [[''.join(row) for row in solution] for solution in result]  # 返回结果集

• result：用于存储所有可能的N皇后解法。
• chessboard：初始化棋盘，大小为n x n，使用.表示空位。
• self.backtracking(n, 0, chessboard, result)：调用回溯函数从第0行开始尝试放置皇后。
• [[''.join(row) for row in solution] for solution in result]：格式化并返回所有解，每个解由二维字符数组转化为字符串列表。

    def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:if row == n:result.append(chessboard[:])  # 棋盘填满，将当前解加入结果集returnfor col in range(n):if self.isValid(row, col, chessboard):chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]  # 放置皇后self.backtracking(n, row + 1, chessboard, result)  # 递归到下一行chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]  # 回溯，撤销当前位置的皇后

• row == n：如果所有n行都放置完皇后，说明找到一个解，添加到结果集中。
• for col in range(n)：遍历当前行的每一列，尝试放置皇后。
• self.isValid(row, col, chessboard)：检查在当前位置(row, col)放置皇后是否合法。
• chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]：在合法的位置放置皇后，使用字符串操作将'Q'放在对应位置。
• self.backtracking(n, row + 1, chessboard, result)：递归地尝试在下一行放置皇后。
• chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]：撤销放置的皇后（回溯），继续尝试其他可能的位置。

    def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:# 检查列for i in range(row):if chessboard[i][col] == 'Q':return False  # 当前列已经存在皇后，不合法# 检查 45 度角是否有皇后i, j = row - 1, col - 1while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return False  # 左上方向已经存在皇后，不合法i -= 1j -= 1# 检查 135 度角是否有皇后i, j = row - 1, col + 1while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return False  # 右上方向已经存在皇后，不合法i -= 1j += 1return True  # 当前位置合法

• 列检查：检查当前列是否存在其他皇后。如果存在，则当前位置不合法。
• 45度角检查（左上对角线）：从当前位置向左上角遍历，检查是否存在皇后。如果存在，则当前位置不合法。
• 135度角检查（右上对角线）：从当前位置向右上角遍历，检查是否存在皇后。如果存在，则当前位置不合法。
• 如果所有检查都通过，返回True，表示当前位置合法。