如何做黑彩网站,购买域名有什么用,晋江市建设局网站,怎么打开wordpress后台本文目录 1 中文题目2 求解方法#xff1a;递归回溯法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
编写一个程序#xff0c;通过填充空格来解决数独问题。数独的解法需 遵循如下规则#xff1a;
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只… 本文目录 1 中文题目2 求解方法递归回溯法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
编写一个程序通过填充空格来解决数独问题。数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图数独部分空格内已填入了数字空白格用 ‘.’ 表示。
示例
输入board [[5,3,.,.,7,.,.,.,.],[6,.,.,1,9,5,.,.,.],[.,9,8,.,.,.,.,6,.],[8,.,.,.,6,.,.,.,3],[4,.,.,8,.,3,.,.,1],[7,.,.,.,2,.,.,.,6],[.,6,.,.,.,.,2,8,.],[.,.,.,4,1,9,.,.,5],[.,.,.,.,8,.,.,7,9]]
输出[[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]
解释输入的数独如上图所示唯一有效的解决方案如下所示提示
board.length 9board[i].length 9board[i][j] 是一位数字或者 ‘.’题目数据 保证 输入数独仅有一个解 2 求解方法递归回溯法
2.1 方法思路
方法核心
使用回溯算法解决数独问题使用三个二维数组记录数字使用情况采用逐个位置填写的策略通过位置编号简化行列索引计算。
实现步骤
1初始化阶段
创建三个二维数组记录每行、每列和每个3x3方块中数字的使用情况遍历数独板标记已有数字的使用情况将问题转化为填写空位的问题
2回溯过程
使用位置编号0-80表示当前填写位置通过整除和取余计算行列索引如果当前位置已有数字继续下一个位置。否则尝试填入1-9的数字
3验证过程
检查当前数字是否可以在行中使用检查当前数字是否可以在列中使用检查当前数字是否可以在3x3方块中使用所有检查都通过才能填入数字
方法示例
输入数独板示例
[[5,3,.,.,7,.,.,.,.],[6,.,.,1,9,5,.,.,.],[.,9,8,.,.,.,.,6,.],[8,.,.,.,6,.,.,.,3],[4,.,.,8,.,3,.,.,1],[7,.,.,.,2,.,.,.,6],[.,6,.,.,.,.,2,8,.],[.,.,.,4,1,9,.,.,5],[.,.,.,.,8,.,.,7,9]
]执行过程示例以填写第一个空位为例1. 定位第一个空位- 位置 (0,2)- box_index (0 // 3) * 3 2 // 3 02. 尝试填入数字- 检查数字1已在同行/列/方块使用- 检查数字2已在同行/列/方块使用- 检查数字4可以使用- 填入数字4并继续递归3. 如果后续填写失败- 回溯到当前位置- 清除数字4- 尝试下一个可能的数字4. 递归和回溯过程继续直到找到完整解答2.2 Python代码
class Solution:def solveSudoku(self, board: List[List[str]]) - None:Do not return anything, modify board in-place instead.# 初始化三个二维数组分别记录行、列和3x3方块中数字的使用情况rows [[False] * 9 for _ in range(9)]cols [[False] * 9 for _ in range(9)]boxes [[False] * 9 for _ in range(9)]# 遍历整个数独板记录已有数字的使用情况for i in range(9):for j in range(9):if board[i][j] ! .:num int(board[i][j]) - 1 # 转换为0-8的索引box_index (i // 3) * 3 j // 3rows[i][num] Truecols[j][num] Trueboxes[box_index][num] Truedef backtrack(pos: int) - bool:# 如果已经填完所有位置返回Trueif pos 81:return True# 计算当前位置的行列索引row, col pos // 9, pos % 9# 如果当前位置已有数字尝试填写下一个位置if board[row][col] ! .:return backtrack(pos 1)# 计算当前位置所在的3x3方块索引box_index (row // 3) * 3 col // 3# 尝试填入1-9的数字for num in range(9):# 检查当前数字是否可以填入if not (rows[row][num] or cols[col][num] or boxes[box_index][num]):# 标记数字使用情况rows[row][num] cols[col][num] boxes[box_index][num] Trueboard[row][col] str(num 1)# 递归尝试填写下一个位置if backtrack(pos 1):return True# 回溯恢复标记和数独板rows[row][num] cols[col][num] boxes[box_index][num] Falseboard[row][col] .# 当前位置无法填入任何数字return False# 从第一个位置开始解数独backtrack(0)2.3 复杂度分析
时间复杂度O(9^m)m是空格的数量 每个空格最多尝试9个数字实际运行时间因剪枝而大大减少 空间复杂度O(m)m是空格的数量递归栈深度 三个固定大小的二维数组81个布尔值 3 题目总结
题目难度困难 数据结构矩阵 应用算法回溯、递归
