【LeetCode 刷题】回溯算法(5)-棋盘问题

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为回溯算法棋盘问题相关的题目解析。

51. N皇后

题目链接

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:board = [['.' for _ in range(n)] for _ in range(n)]res = []def check(x: int, y: int) -> bool:for i in range(x):if board[i][y] == 'Q':  # 列return Falseif y - (x - i) >= 0 and board[i][y-(x-i)] == 'Q':  # 45对角线return Falseif y + (x - i) < n and board[i][y+(x-i)] == 'Q':  # -45对角线return Falsereturn Truedef dfs(row: int) -> None:if row == n:res.append([''.join(row) for row in board])returnfor col in range(n):if check(row, col):board[row][col] = 'Q'dfs(row + 1)board[row][col] = '.'dfs(0)return res

• dfs 函数的参数为行号，即“第 row 行选哪一列放皇后”构成递归树的一层
• 判断合法性时，不需要判断行是否合法，因为上述解法递归的逻辑即为每一行选择一列去放皇后，所以行约束肯定满足；且判断时只需要判断当前行 x 以上的合法性，因为下面的行还没有放皇后，肯定不会冲突

37. 解数独

题目链接

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""def check(x: int, y: int, num: str) -> bool:for i in range(9):if board[i][y] == num:return Falsefor i in range(9):if board[x][i] == num:return Falserow_s, col_s = x // 3 * 3, y // 3 * 3for i in range(3):for j in range(3):if board[row_s+i][col_s+j] == num:return Falsereturn Truedef dfs() -> bool:for i in range(9):for j in range(9):if board[i][j] == '.':for num in range(1, 10):if check(i, j, str(num)):board[i][j] = str(num)if dfs(): return Trueboard[i][j] = '.'return Falsereturn Truedfs()return

• 数独的 check 函数需要检查整个棋盘，而非当前行列之前的内容
• 当找到一个解时，直接返回 True，之前的递归也不再进行回溯；如果当前位置 1-9 全部遍历也没找到解，则返回 False

332.重新安排行程

题目链接

class Solution:def findItinerary(self, tickets: List[List[str]]) -> List[str]:tickets = sorted(tickets, key=lambda x: (x[0], x[1]))graph = {}for u, v in tickets:if u in graph:graph[u].append(v)else:graph[u] = [v]path = ['JFK']def dfs(u, num):if num == 0:return Trueif u not in graph or not graph[u]:return Falseaims = graph[u].copy()for v in aims:graph[u].pop(graph[u].index(v))path.append(v)if dfs(v, num - 1):return Truepath.pop()graph[u].append(v)return Falsedfs("JFK", len(tickets))return path

• dfs 函数的参数分别为：当前站点，以及还有几站到达终点
• 首先需要将 tickets 转换为有向图的形式，之后遍历当前点所有可能的下一站点列表，每处理一个站点，从原始列表中移除，回溯时再将站点添加回列表
• 由于最开始按照字典序升序排列，因此一旦找到一条合法行程，即为满足题目要求的字典序最小的行程，递归函数即可返回；如果当前处理的站点不存在合法的下一站，则回溯。