教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」中 LeetCode 0037 解数独Sudoku Solver 题解的深度展开围绕「回溯算法」这一核心方法从题目约束、三重循环枚举、有效性校验到复杂度分析逐层拆解。读完本文你将掌握用「选择 - 递归 - 回溯」三步法求解 9×9 数独的完整套路并理解它与 有效的数独、N 皇后等经典回溯题的异同。一、题目概述题目链接题号0037 解数独Sudoku Solver力扣困难题标签数组、哈希表、回溯、矩阵难度困难题目大意给定一个用二维字符数组board表示的数独棋盘数字1 ~ 9表示该位置已经填入了数字字符.表示该位置还没有填入数字。要求编写程序通过填充空格的方式解决数独问题。最终不需要返回答案只需将题目给定的board原地in-place修改为可行方案即可。题目说明数独解法必须遵循如下三条规则规则内容行约束数字1 ~ 9在每一行只能出现一次列约束数字1 ~ 9在每一列只能出现一次宫格约束数字1 ~ 9在每一个以粗直线分隔的3 × 3宫格内只能出现一次同时题目保证board.length 9board[i].length 9board[i][j]是一位数字或者.题目数据保证输入数独仅有一个解这是回溯法可行的前提一旦找到可行解即可直接返回。示例输入棋盘.表示待填空格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]]解出后的棋盘board [[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]]二、前置知识回溯算法回顾回溯算法是本题的灵魂。手册在 07_algorithm/07_04_backtracking_algorithm.md 中对其作了系统讲解回溯算法是一种通过递归和试错系统地搜索所有可能解的算法核心思想是「走不通就退回换条路再试」。回溯算法的通用模板如下摘自 回溯算法章节def backtrack(参数): if 终止条件: 处理结果 return for 选择 in 可选列表: if 满足约束: 做选择 backtrack(新参数) 撤销选择把模板落地需要三个步骤明确所有选择画出决策树理清每一步有哪些可选项明确终止条件通常是递归到某一深度、遍历完所有元素或满足题目要求将决策树与终止条件转化为代码定义回溯函数、书写「选择 - 递归 - 撤销选择」主体、明确递归终止及结果处理。解数独正是这个模板的「困难模式」可选项是每个空位上的1 ~ 9约束条件升级为「行 / 列 / 宫格三重唯一性」终止条件是 81 个格子全部被合法填满。三、解题思路回溯算法3.1 思路框架对于每一行、每一列、每一个数字都需要一重for循环来遍历这样整体就是三重for循环第一重循环遍历行i第二重循环遍历列j第三重循环当board[i][j]是空位时遍历数字k1 ~ 9尝试填入。对于第i行、第j列的元素来说如果当前位置是空位则尝试将数字k置于此处并调用校验函数判断数独是否仍然有效如果有效则继续递归遍历下一个空位直到遍历完所有空位得到可行方案或某条分支全部失败而结束遍历完下一个空位递归返回之后再将此位置**回退回溯**置为.以尝试数字k1或其他位置的其他选择。3.2 校验函数 isValid 详解isValid(row, col, val, board)负责在尝试把数字val放到(row, col)之前快速判断是否违背三条约束它包含三个独立检查def isValid(self, row: int, col: int, val: int, board: List[List[str]]) - bool: # 1. 行检查第 row 行是否已出现过 val for i in range(0, 9): if board[row][i] str(val): return False # 2. 列检查第 col 列是否已出现过 val for j in range(0, 9): if board[j][col] str(val): return False # 3. 宫格检查(row, col) 所在的 3×3 宫格内是否已出现过 val start_row (row // 3) * 3 start_col (col // 3) * 3 for i in range(start_row, start_row 3): for j in range(start_col, start_col 3): if board[i][j] str(val): return False return True三个检查点分别对应题目说明中的行、列、宫格三条规则行检查固定row扫描第row行的 9 个格子列检查固定col扫描第col列的 9 个格子宫格检查关键在宫格定位。(row // 3) * 3得到宫格的起始行(col // 3) * 3得到宫格的起始列再遍历3 × 3的 9 个格子。例如row 5, col 7时start_row 3, start_col 6检查的是第 3~5 行、第 6~8 列组成的右下宫格。注意这里每尝试一个数字都要做一次O(9 9 9) O(27)的线性扫描属于常数级开销胜在实现简单直观。3.3 回溯主函数def backtrack(self, board: List[List[str]]): for i in range(len(board)): # 第一重循环遍历行 for j in range(len(board[0])): # 第二重循环遍历列 if board[i][j] ! .: # 已填数字的位置直接跳过 continue for k in range(1, 10): # 第三重循环尝试数字 1 ~ 9 if self.isValid(i, j, k, board): # 约束校验 board[i][j] str(k) # 做选择填入数字 if self.backtrack(board): # 递归继续填下一个空位 return True # 找到可行解逐层返回 board[i][j] . # 撤销选择回溯 return False # 当前空位 1~9 都失败向上返回 False return True # 所有空位填满得到可行解逐步拆解这段递归逻辑定位空位双重循环从左到右、从上到下扫描棋盘跳过已填数字的位置尝试候选对每个空位依次尝试1 ~ 9用isValid过滤掉违反三条规则的候选做选择把合法候选写入board[i][j]注意题目用字符数组需str(k)转换递归深入带着新状态继续调用backtrack去填下一个空位早停返回一旦某次递归返回True说明后续所有空格都已被合法填满直接一路返回True不再回溯撤销选择如果递归返回False说明当前候选无法导向可行解把位置恢复为.尝试下一个候选穷尽分支如果1 ~ 9全部失败返回False让上层尝试其他数字。整个搜索过程可以用一棵决策树描述树的每一层对应一个空位每个节点的分支对应1 ~ 9的候选数字isValid是分支的过滤阀找到叶子节点即找到一个完整解。这正是 回溯算法章节 中「决策树 终止条件 递归模板」三步走的直接体现。四、完整代码将上述两部分合并得到完整的可运行解法保留题目要求的原地修改语义class Solution: def backtrack(self, board: List[List[str]]): for i in range(len(board)): for j in range(len(board[0])): if board[i][j] ! .: continue for k in range(1, 10): if self.isValid(i, j, k, board): board[i][j] str(k) if self.backtrack(board): return True board[i][j] . return False return True def isValid(self, row: int, col: int, val: int, board: List[List[str]]) - bool: for i in range(0, 9): if board[row][i] str(val): return False for j in range(0, 9): if board[j][col] str(val): return False start_row (row // 3) * 3 start_col (col // 3) * 3 for i in range(start_row, start_row 3): for j in range(start_col, start_col 3): if board[i][j] str(val): return False return True def solveSudoku(self, board: List[List[str]]) - None: self.backtrack(board) Do not return anything, modify board in-place instead. 运行方式与边界入口是solveSudoku(board)它直接调用backtrack(board)原地修改棋盘无返回值与 LeetCode 题目签名一致输入必须是标准的9 × 9字符数组数字以字符串形式存储空位用.题目保证输入数独仅有一个解因此第一个完整解即可返回无需收集所有解。五、复杂度分析时间复杂度O(9^m)设棋盘中.的数量为m空位个数每个空位最多尝试9个候选数字因此最坏情况下搜索空间是9^m个状态每个状态还要做常数级的isValid校验扫描行、列、宫格共 27 个格子这部分开销是常数因此整体时间复杂度为O(9^m)其中m是棋盘中.的数量。当棋盘几乎全空时m接近 81最坏情况是指数级爆炸而实际数独题目的空位数量与初始给定数字共同决定了运行时间。空间复杂度O(9^2)递归调用栈的最大深度取决于空位数量m但棋盘本身是固定9 × 9校验与回溯均只使用常数规模的额外空间因此空间复杂度为O(9^2)即常数级81 个格子的棋盘规模。关于复杂度记号的含义可以参考手册中的 算法复杂度章节大 O 表示渐近上界反映最坏情况下的增长趋势。六、进阶讨论剪枝与优化方向原始回溯解法胜在正确性与可读性但O(9^m)的最坏复杂度意味着当空位较多时搜索会非常慢。从算法层面可以推断以下优化方向属于通用算法知识读者可在理解本题后自行尝试位运算状态压缩用 9 个 bit 的整数分别记录每行、每列、每个宫格中已出现的数字把isValid的线性扫描降为O(1)的位运算判断同时做「填数 - 恢复」时也只需异或操作最少候选优先MRV每次递归前扫描所有空位优先填充候选数字最少的格子而不是简单从左到右可以大幅剪枝、显著减少搜索树规模提前校验在填数前用「只出现一次的候选」启发式或先跑一遍 0036 有效的数独 的思路确认初始盘面合法避免在非法盘面上做无用搜索。需要注意的是本仓库题解文档以「回溯 线性校验」的标准做法为准以上优化属于对该主题的延伸思考适合作为后续练习方向。七、与其他题目的关联7.1 与 0036 有效的数独的关系0036 有效的数独 只要求验证已填入的数字是否满足规则用 3 个哈希表分别记录行、列、宫格不要求求解而本题要求求解完整数独。两者共用同一条规则体系可以把 0036 看成解数独的「合法性验证子问题」——isValid检查的就是局部版本的「有效数独」。7.2 回溯家族题目在手册的 回溯算法题目列表 中0037 解数独与以下题目同属回溯专题推荐按难度递进练习0051 N 皇后困难同样是「逐位置尝试 合法性校验 回溯」结构区别是约束为行、列、斜线0046 全排列中等回溯入门题体会「选择 - 递归 - 回溯」最小模板0078 子集中等每个元素「选 / 不选」两种分支0039 组合总和中等在候选集合上做组合式回溯0079 单词搜索中等在二维网格上做 DFS 式回溯0093 复原 IP 地址中等对字符串做分段式回溯。其中 N 皇后 与解数独在结构上最为接近两者都是「在网格上逐格/逐行做选择用校验函数过滤冲突冲突则回溯」可以对照阅读进一步巩固回溯算法的「决策树 剪枝」思维。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 37. Sudoku Solver 题解用 Go 实现 DFS 回溯求解数独LeetCode 37. Sudoku Solver 题解用 Go 实现 DFS 回溯求解数独 本篇以 leetcode/0037.Sudoku Solver示例工程CHIPSEC配置系统完全解析从XML配置到平台检测的完整流程CHIPSEC配置系统完全解析从XML配置到平台检测的完整流程 CHIPSEC作为Platform Security Assessment Framework应用安全渗透测试LeetCode数独求解回溯算法剪枝优化终极指南LeetCode数独求解回溯算法剪枝优化终极指南 数独作为经典的逻辑推理游戏其求解算法一直是LeetCode热门面试题。本文将深入探讨回溯法在数独求解中的应示例工程教程上一篇深度解析3Dmigoto游戏渲染修复工具的架构设计与高级定制下一篇Kata Containers终极故障排除指南10个常见问题及解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 0037 解数独（Sudoku Solver）：AlgoNote 回溯算法实战解析
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」中 LeetCode 0037 解数独Sudoku Solver 题解的深度展开围绕「回溯算法」这一核心方法从题目约束、三重循环枚举、有效性校验到复杂度分析逐层拆解。读完本文你将掌握用「选择 - 递归 - 回溯」三步法求解 9×9 数独的完整套路并理解它与 有效的数独、N 皇后等经典回溯题的异同。一、题目概述题目链接题号0037 解数独Sudoku Solver力扣困难题标签数组、哈希表、回溯、矩阵难度困难题目大意给定一个用二维字符数组board表示的数独棋盘数字1 ~ 9表示该位置已经填入了数字字符.表示该位置还没有填入数字。要求编写程序通过填充空格的方式解决数独问题。最终不需要返回答案只需将题目给定的board原地in-place修改为可行方案即可。题目说明数独解法必须遵循如下三条规则规则内容行约束数字1 ~ 9在每一行只能出现一次列约束数字1 ~ 9在每一列只能出现一次宫格约束数字1 ~ 9在每一个以粗直线分隔的3 × 3宫格内只能出现一次同时题目保证board.length 9board[i].length 9board[i][j]是一位数字或者.题目数据保证输入数独仅有一个解这是回溯法可行的前提一旦找到可行解即可直接返回。示例输入棋盘.表示待填空格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]]解出后的棋盘board [[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]]二、前置知识回溯算法回顾回溯算法是本题的灵魂。手册在 07_algorithm/07_04_backtracking_algorithm.md 中对其作了系统讲解回溯算法是一种通过递归和试错系统地搜索所有可能解的算法核心思想是「走不通就退回换条路再试」。回溯算法的通用模板如下摘自 回溯算法章节def backtrack(参数): if 终止条件: 处理结果 return for 选择 in 可选列表: if 满足约束: 做选择 backtrack(新参数) 撤销选择把模板落地需要三个步骤明确所有选择画出决策树理清每一步有哪些可选项明确终止条件通常是递归到某一深度、遍历完所有元素或满足题目要求将决策树与终止条件转化为代码定义回溯函数、书写「选择 - 递归 - 撤销选择」主体、明确递归终止及结果处理。解数独正是这个模板的「困难模式」可选项是每个空位上的1 ~ 9约束条件升级为「行 / 列 / 宫格三重唯一性」终止条件是 81 个格子全部被合法填满。三、解题思路回溯算法3.1 思路框架对于每一行、每一列、每一个数字都需要一重for循环来遍历这样整体就是三重for循环第一重循环遍历行i第二重循环遍历列j第三重循环当board[i][j]是空位时遍历数字k1 ~ 9尝试填入。对于第i行、第j列的元素来说如果当前位置是空位则尝试将数字k置于此处并调用校验函数判断数独是否仍然有效如果有效则继续递归遍历下一个空位直到遍历完所有空位得到可行方案或某条分支全部失败而结束遍历完下一个空位递归返回之后再将此位置**回退回溯**置为.以尝试数字k1或其他位置的其他选择。3.2 校验函数 isValid 详解isValid(row, col, val, board)负责在尝试把数字val放到(row, col)之前快速判断是否违背三条约束它包含三个独立检查def isValid(self, row: int, col: int, val: int, board: List[List[str]]) - bool: # 1. 行检查第 row 行是否已出现过 val for i in range(0, 9): if board[row][i] str(val): return False # 2. 列检查第 col 列是否已出现过 val for j in range(0, 9): if board[j][col] str(val): return False # 3. 宫格检查(row, col) 所在的 3×3 宫格内是否已出现过 val start_row (row // 3) * 3 start_col (col // 3) * 3 for i in range(start_row, start_row 3): for j in range(start_col, start_col 3): if board[i][j] str(val): return False return True三个检查点分别对应题目说明中的行、列、宫格三条规则行检查固定row扫描第row行的 9 个格子列检查固定col扫描第col列的 9 个格子宫格检查关键在宫格定位。(row // 3) * 3得到宫格的起始行(col // 3) * 3得到宫格的起始列再遍历3 × 3的 9 个格子。例如row 5, col 7时start_row 3, start_col 6检查的是第 3~5 行、第 6~8 列组成的右下宫格。注意这里每尝试一个数字都要做一次O(9 9 9) O(27)的线性扫描属于常数级开销胜在实现简单直观。3.3 回溯主函数def backtrack(self, board: List[List[str]]): for i in range(len(board)): # 第一重循环遍历行 for j in range(len(board[0])): # 第二重循环遍历列 if board[i][j] ! .: # 已填数字的位置直接跳过 continue for k in range(1, 10): # 第三重循环尝试数字 1 ~ 9 if self.isValid(i, j, k, board): # 约束校验 board[i][j] str(k) # 做选择填入数字 if self.backtrack(board): # 递归继续填下一个空位 return True # 找到可行解逐层返回 board[i][j] . # 撤销选择回溯 return False # 当前空位 1~9 都失败向上返回 False return True # 所有空位填满得到可行解逐步拆解这段递归逻辑定位空位双重循环从左到右、从上到下扫描棋盘跳过已填数字的位置尝试候选对每个空位依次尝试1 ~ 9用isValid过滤掉违反三条规则的候选做选择把合法候选写入board[i][j]注意题目用字符数组需str(k)转换递归深入带着新状态继续调用backtrack去填下一个空位早停返回一旦某次递归返回True说明后续所有空格都已被合法填满直接一路返回True不再回溯撤销选择如果递归返回False说明当前候选无法导向可行解把位置恢复为.尝试下一个候选穷尽分支如果1 ~ 9全部失败返回False让上层尝试其他数字。整个搜索过程可以用一棵决策树描述树的每一层对应一个空位每个节点的分支对应1 ~ 9的候选数字isValid是分支的过滤阀找到叶子节点即找到一个完整解。这正是 回溯算法章节 中「决策树 终止条件 递归模板」三步走的直接体现。四、完整代码将上述两部分合并得到完整的可运行解法保留题目要求的原地修改语义class Solution: def backtrack(self, board: List[List[str]]): for i in range(len(board)): for j in range(len(board[0])): if board[i][j] ! .: continue for k in range(1, 10): if self.isValid(i, j, k, board): board[i][j] str(k) if self.backtrack(board): return True board[i][j] . return False return True def isValid(self, row: int, col: int, val: int, board: List[List[str]]) - bool: for i in range(0, 9): if board[row][i] str(val): return False for j in range(0, 9): if board[j][col] str(val): return False start_row (row // 3) * 3 start_col (col // 3) * 3 for i in range(start_row, start_row 3): for j in range(start_col, start_col 3): if board[i][j] str(val): return False return True def solveSudoku(self, board: List[List[str]]) - None: self.backtrack(board) Do not return anything, modify board in-place instead. 运行方式与边界入口是solveSudoku(board)它直接调用backtrack(board)原地修改棋盘无返回值与 LeetCode 题目签名一致输入必须是标准的9 × 9字符数组数字以字符串形式存储空位用.题目保证输入数独仅有一个解因此第一个完整解即可返回无需收集所有解。五、复杂度分析时间复杂度O(9^m)设棋盘中.的数量为m空位个数每个空位最多尝试9个候选数字因此最坏情况下搜索空间是9^m个状态每个状态还要做常数级的isValid校验扫描行、列、宫格共 27 个格子这部分开销是常数因此整体时间复杂度为O(9^m)其中m是棋盘中.的数量。当棋盘几乎全空时m接近 81最坏情况是指数级爆炸而实际数独题目的空位数量与初始给定数字共同决定了运行时间。空间复杂度O(9^2)递归调用栈的最大深度取决于空位数量m但棋盘本身是固定9 × 9校验与回溯均只使用常数规模的额外空间因此空间复杂度为O(9^2)即常数级81 个格子的棋盘规模。关于复杂度记号的含义可以参考手册中的 算法复杂度章节大 O 表示渐近上界反映最坏情况下的增长趋势。六、进阶讨论剪枝与优化方向原始回溯解法胜在正确性与可读性但O(9^m)的最坏复杂度意味着当空位较多时搜索会非常慢。从算法层面可以推断以下优化方向属于通用算法知识读者可在理解本题后自行尝试位运算状态压缩用 9 个 bit 的整数分别记录每行、每列、每个宫格中已出现的数字把isValid的线性扫描降为O(1)的位运算判断同时做「填数 - 恢复」时也只需异或操作最少候选优先MRV每次递归前扫描所有空位优先填充候选数字最少的格子而不是简单从左到右可以大幅剪枝、显著减少搜索树规模提前校验在填数前用「只出现一次的候选」启发式或先跑一遍 0036 有效的数独 的思路确认初始盘面合法避免在非法盘面上做无用搜索。需要注意的是本仓库题解文档以「回溯 线性校验」的标准做法为准以上优化属于对该主题的延伸思考适合作为后续练习方向。七、与其他题目的关联7.1 与 0036 有效的数独的关系0036 有效的数独 只要求验证已填入的数字是否满足规则用 3 个哈希表分别记录行、列、宫格不要求求解而本题要求求解完整数独。两者共用同一条规则体系可以把 0036 看成解数独的「合法性验证子问题」——isValid检查的就是局部版本的「有效数独」。7.2 回溯家族题目在手册的 回溯算法题目列表 中0037 解数独与以下题目同属回溯专题推荐按难度递进练习0051 N 皇后困难同样是「逐位置尝试 合法性校验 回溯」结构区别是约束为行、列、斜线0046 全排列中等回溯入门题体会「选择 - 递归 - 回溯」最小模板0078 子集中等每个元素「选 / 不选」两种分支0039 组合总和中等在候选集合上做组合式回溯0079 单词搜索中等在二维网格上做 DFS 式回溯0093 复原 IP 地址中等对字符串做分段式回溯。其中 N 皇后 与解数独在结构上最为接近两者都是「在网格上逐格/逐行做选择用校验函数过滤冲突冲突则回溯」可以对照阅读进一步巩固回溯算法的「决策树 剪枝」思维。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 37. Sudoku Solver 题解用 Go 实现 DFS 回溯求解数独LeetCode 37. Sudoku Solver 题解用 Go 实现 DFS 回溯求解数独 本篇以 leetcode/0037.Sudoku Solver示例工程CHIPSEC配置系统完全解析从XML配置到平台检测的完整流程CHIPSEC配置系统完全解析从XML配置到平台检测的完整流程 CHIPSEC作为Platform Security Assessment Framework应用安全渗透测试LeetCode数独求解回溯算法剪枝优化终极指南LeetCode数独求解回溯算法剪枝优化终极指南 数独作为经典的逻辑推理游戏其求解算法一直是LeetCode热门面试题。本文将深入探讨回溯法在数独求解中的应示例工程教程上一篇深度解析3Dmigoto游戏渲染修复工具的架构设计与高级定制下一篇Kata Containers终极故障排除指南10个常见问题及解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考