算法训练营day25 回溯算法④ 补充联系题目 332.重新安排行程、51. N皇后、37. 解数独

        这组题目相对都复杂一些，初次练习，争取把思路学会

332.重新安排行程

        暂略

51. N皇后

        按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

        如何抽象为问题模型，本题是回溯算法的经典题目，组合排列进行判断

回溯过程

• 递归函数参数

        依然是定义全局变量二维数组result来记录最终结果。参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。

• 递归终止条件

        到达叶子节点返回

• 单层搜索的逻辑

        递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。

        每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

• 验证棋盘是否合法

按照如下标准去重：

1. 不能同行
2. 不能同列
3. 不能同斜线 （45度和135度角）

代码实现

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[:])return# 自上向下for 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:# row 行 、col 列# 自上向下# 理解数组中[row][col]的位置 for i in range(row): # 检查列if chessboard[i][col] == 'Q':return Falsei, j = row - 1, col - 1 # 45°while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return Falsei -= 1j -= 1i, j = row - 1, col + 1 # 135°while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return Falsei -= 1j += 1return True

37. 解数独

        和上一题棋盘问题一样，可以使用回溯算法递归实现，树状图部分如下：可见树范围扩大，同时结构存在差异

回溯过程：

• 递归函数以及参数

        递归函数的返回值需要是bool类型，因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。

• 递归终止条件

        本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止

• 递归单层搜索逻辑

        在树形图中可以看出我们需要的是一个二维的递归 （一行一列）：一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！

        注意这里return false的地方

判断棋盘是否合法

判断棋盘是否合法有如下三个维度：

• 同行是否重复
• 同列是否重复
• 9宫格里是否重复

代码实现

通过递归的方式传递不同位置的True，二维部分

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""row_used = [set() for _ in range(9)]col_used = [set() for _ in range(9)]box_used = [set() for _ in range(9)]for row in range(9):for col in range(9):num = board[row][col]if num == ".":continuerow_used[row].add(num)col_used[col].add(num)box_used[(row // 3) * 3 + col // 3].add(num)self.backtracking(0, 0, board, row_used, col_used, box_used)def backtracking(self,row: int,col: int,board: List[List[str]],row_used: List[List[int]],col_used: List[List[int]],box_used: List[List[int]],) -> bool:if row == 9:return Truenext_row, next_col = (row, col + 1) if col < 8 else (row + 1, 0)if board[row][col] != ".":return self.backtracking(next_row, next_col, board, row_used, col_used, box_used)for num in map(str, range(1, 10)):if (num not in row_used[row]and num not in col_used[col]and num not in box_used[(row // 3) * 3 + col // 3]):board[row][col] = numrow_used[row].add(num)col_used[col].add(num)box_used[(row // 3) * 3 + col // 3].add(num)if self.backtracking(next_row, next_col, board, row_used, col_used, box_used):return Trueboard[row][col] = "."row_used[row].remove(num)col_used[col].remove(num)box_used[(row // 3) * 3 + col // 3].remove(num)return False
# 注意这里return false的地方，这里放return false 是有讲究的。
# 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
# 那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！