LeetCode-Go 题解 37Sudoku Solver数独求解器DFS 回溯枚举实现详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中 0037.Sudoku-Solver 题解文档 为骨架结合 核心源码 与 单元测试完整讲解第 37 题「Sudoku Solver」的题目约束、DFS 暴力回溯枚举解法、逐函数代码剖析、正确性验证与复杂度分析。读完本文你将掌握如何在 9x9 棋盘上用 Go 从零实现一个可运行、可测试的数独求解器并理解回溯算法尝试—校验—回退的完整闭环。一、题目编写程序自动填充数独空格第 37 题要求编写一个程序通过填充空格来求解数独谜题。一个合法的数独解必须同时满足以下全部规则数字1-9在每一行只能出现一次数字1-9在每一列只能出现一次数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。空白格用字符.表示。题目同时给出三条重要约束见 题解文档给定的棋盘只包含数字1-9和字符.可以假定给定的数独谜题有且仅有一个唯一解棋盘大小恒为9x9。输入输出形态函数直接修改传入的[][]byte二维棋盘在.处原地填入答案数字没有返回值。这与 LeetCode 的接口签名func solveSudoku(board [][]byte)保持一致。二、解题思路DFS 暴力回溯枚举数独的规则决定了数字不得重复必须同时作用在三个维度每横行、每竖行、每个 3x3 九宫格。因此最直接、也最可靠的策略就是DFS 暴力回溯枚举思路见 题解文档 的 Solution Approach 一节先扫描棋盘把所有空白格.的位置收集起来得到一个待填充位置的列表从第一个空白格开始依次尝试数字1到9每放入一个数字之前都要在行、列、3x3 宫三处做一次合法性校验全部通过才落子递归进入下一个空白格若某格所有候选数字都无法通过校验则回溯到上一个格子撤销刚才的数字重新填回.换下一个数字继续尝试一旦找到一组完整解不再继续回溯直接返回这是保证性能的关键剪枝。这种遇到死路就回头换一条路的策略本质上就是深度优先搜索加回溯Backtracking。本题要求的唯一解特性使得找到即返回的剪枝完全成立。三、核心源码逐函数剖析仓库中的完整实现位于 37. Sudoku Solver.go共拆分为三个职责清晰的函数solveSudoku入口、putSudoku回溯递归与checkSudoku三路合法性校验。3.1 辅助结构体 positiontype position struct { x int y int }position用于记录一个空白格的行号x与列号y是整个回溯过程的状态载体。3.2 入口函数 solveSudoku收集空白格并启动回溯func solveSudoku(board [][]byte) { pos, find : []position{}, false for i : 0; i len(board); i { for j : 0; j len(board[0]); j { if board[i][j] . { pos append(pos, position{x: i, y: j}) } } } putSudoku(board, pos, 0, find) }入口函数做两件事收集空白格双重循环扫描整个 9x9 棋盘把每个值为.的单元格坐标压入pos切片。这一步决定了后续回溯的推进顺序——按行优先、自左向右逐个填充。启动递归调用putSudoku从pos的索引0第一个空白格开始尝试填数同时传入一个find标志初始为false用于标记是否已经找到完整解。值得注意的一个实现细节board以*[][]byte指针方式传入递归find也以*bool指针传递保证递归各层之间共享同一份棋盘状态与已找到解的标志。3.3 递归函数 putSudoku尝试、落子、回退func putSudoku(board *[][]byte, pos []position, index int, succ *bool) { if *succ true { return } if index len(pos) { *succ true return } for i : 1; i 10; i { if checkSudoku(board, pos[index], i) !*succ { (*board)[pos[index].x][pos[index].y] byte(i) 0 putSudoku(board, pos, index1, succ) if *succ true { return } (*board)[pos[index].x][pos[index].y] . } } }该函数是整个算法的引擎逻辑分四层全局剪枝递归一开始就检查*succ一旦某条分支已经找到完整解立即终止后续所有分支的探索对应文档中找到一组解以后就不需要再继续回溯了直接返回即可的优化。递归出口index len(pos)表示所有空白格都已成功填完此时将*succ置为true标志着找到完整解。枚举候选数字for i : 1; i 10; i依次尝试数字1到9先经过checkSudoku三路校验通过且尚未找到解!*succ时才把数字写入棋盘byte(i) 0把整数转换为对应的 ASCII 字符。落子与回退写入后递归进入下一个空白格index1若递归返回后发现已找到解直接返回不再尝试否则说明当前数字导致死路回退——把该格重新写成.继续尝试下一个数字。这里的回退backtrack正是回溯算法区别于普通 DFS 的核心棋盘状态在递归返回后必须恢复到尝试前的样子保证兄弟分支的校验不受污染。3.4 校验函数 checkSudoku行、列、宫三路检查func checkSudoku(board *[][]byte, pos position, val int) bool { // 判断横行是否有重复数字 for i : 0; i len((*board)[0]); i { if (*board)[pos.x][i] ! . int((*board)[pos.x][i]-0) val { return false } } // 判断竖行是否有重复数字 for i : 0; i len((*board)); i { if (*board)[i][pos.y] ! . int((*board)[i][pos.y]-0) val { return false } } // 判断九宫格是否有重复数字 posx, posy : pos.x-pos.x%3, pos.y-pos.y%3 for i : posx; i posx3; i { for j : posy; j posy3; j { if (*board)[i][j] ! . int((*board)[i][j]-0) val { return false } } } return true }checkSudoku在(pos.x, pos.y)处尝试放入val前必须确认三处均无冲突任意一处重复即返回false行检查固定行号pos.x遍历整行 9 列跳过.若存在等于val的数字则冲突列检查固定列号pos.y遍历整列 9 行规则同上宫检查这是最巧妙的一步。通过pos.x - pos.x%3与pos.y - pos.y%3将当前坐标对齐到所在 3x3 宫的左上角再以双重循环遍历该宫 3x3 共 9 个单元格逐一比对。取模运算让任意坐标都能快速映射到其所属九宫格是本题的关键几何技巧。只有三路检查全部通过val才被允许写入棋盘。该函数在 核心源码 中有明确的注释标注三段检查的职责。四、测试用例与运行验证仓库为本题提供了完整的单测位于 37. Sudoku Solver_test.go包含两方面验证4.1 LeetCode 官方示例用例测试构造了 LeetCode 官方给出的数独谜题para37.s调用solveSudoku原地求解后与标准答案ans37.s对比para37{[][]byte{ {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}}4.2 分支覆盖测试测试文件还专门覆盖了putSudoku中*succ已为true时的提前返回分支见测试文件第 62-71 行的注释与代码构造一个already : true的初始标志调用putSudoku后断言already保持为true从而验证全局剪枝逻辑没有副作用。4.3 运行测试本仓库采用gotest.sh脚本统一执行全量测试并生成覆盖率报告见 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只针对本题目录运行go test -v ./leetcode/0037.Sudoku-Solver/项目模块声明为github.com/halfrost/LeetCode-Go见 go.mod测试代码与题解代码同属leetcode包直接复用仓库内的structures等辅助模块即可编译运行。五、复杂度分析从源码结构推断从代码实现可以推断出如下复杂度特征时间方面最坏情况下需要对每个空白格尝试 9 个数字每次尝试都要进行行、列、宫共 27 次比较理论最坏复杂度为指数级O(9^m)m为空白格数量但由于唯一解 找到即返回的剪枝实际求解速度远快于最坏情形LeetCode 官方案例几乎瞬间完成。空间方面递归深度等于空白格数量m最多 81辅助切片pos也最多容纳 81 个坐标因此空间复杂度为O(m)其中m为空格数。可优化方向基于本实现的扩展思考可以引入每行/每列/每宫候选数字位图bitmask把校验从线性扫描降为常数时间也可以采用 MRVMinimum Remaining Values优先填充候选数最少的格子启发式进一步加速——但就本题数据规模而言当前的简洁实现已经足够。六、小结通过本题可以完整掌握回溯算法的标准四步法约束定义行/列/宫不重复→ 状态收集空白格列表→ 递归尝试1-9 枚举 三路校验→ 失败回退恢复.。仓库实现用三个短小精悍的函数完成了从入口收集、递归求解到合法性校验的全部逻辑配合官方用例与分支覆盖测试是一份可直接运行、可直接复用的数独求解器参考实现。相关文档与代码路径汇总如下题解文档英文版website/content.en/ChapterFour/0001~0099/0037.Sudoku-Solver.md题解文档中文版leetcode/0037.Sudoku-Solver/README.md核心实现37. Sudoku Solver.go单元测试37. Sudoku Solver_test.go【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 37：Sudoku Solver（数独求解器）DFS 回溯枚举实现详解
LeetCode-Go 题解 37Sudoku Solver数独求解器DFS 回溯枚举实现详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中 0037.Sudoku-Solver 题解文档 为骨架结合 核心源码 与 单元测试完整讲解第 37 题「Sudoku Solver」的题目约束、DFS 暴力回溯枚举解法、逐函数代码剖析、正确性验证与复杂度分析。读完本文你将掌握如何在 9x9 棋盘上用 Go 从零实现一个可运行、可测试的数独求解器并理解回溯算法尝试—校验—回退的完整闭环。一、题目编写程序自动填充数独空格第 37 题要求编写一个程序通过填充空格来求解数独谜题。一个合法的数独解必须同时满足以下全部规则数字1-9在每一行只能出现一次数字1-9在每一列只能出现一次数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。空白格用字符.表示。题目同时给出三条重要约束见 题解文档给定的棋盘只包含数字1-9和字符.可以假定给定的数独谜题有且仅有一个唯一解棋盘大小恒为9x9。输入输出形态函数直接修改传入的[][]byte二维棋盘在.处原地填入答案数字没有返回值。这与 LeetCode 的接口签名func solveSudoku(board [][]byte)保持一致。二、解题思路DFS 暴力回溯枚举数独的规则决定了数字不得重复必须同时作用在三个维度每横行、每竖行、每个 3x3 九宫格。因此最直接、也最可靠的策略就是DFS 暴力回溯枚举思路见 题解文档 的 Solution Approach 一节先扫描棋盘把所有空白格.的位置收集起来得到一个待填充位置的列表从第一个空白格开始依次尝试数字1到9每放入一个数字之前都要在行、列、3x3 宫三处做一次合法性校验全部通过才落子递归进入下一个空白格若某格所有候选数字都无法通过校验则回溯到上一个格子撤销刚才的数字重新填回.换下一个数字继续尝试一旦找到一组完整解不再继续回溯直接返回这是保证性能的关键剪枝。这种遇到死路就回头换一条路的策略本质上就是深度优先搜索加回溯Backtracking。本题要求的唯一解特性使得找到即返回的剪枝完全成立。三、核心源码逐函数剖析仓库中的完整实现位于 37. Sudoku Solver.go共拆分为三个职责清晰的函数solveSudoku入口、putSudoku回溯递归与checkSudoku三路合法性校验。3.1 辅助结构体 positiontype position struct { x int y int }position用于记录一个空白格的行号x与列号y是整个回溯过程的状态载体。3.2 入口函数 solveSudoku收集空白格并启动回溯func solveSudoku(board [][]byte) { pos, find : []position{}, false for i : 0; i len(board); i { for j : 0; j len(board[0]); j { if board[i][j] . { pos append(pos, position{x: i, y: j}) } } } putSudoku(board, pos, 0, find) }入口函数做两件事收集空白格双重循环扫描整个 9x9 棋盘把每个值为.的单元格坐标压入pos切片。这一步决定了后续回溯的推进顺序——按行优先、自左向右逐个填充。启动递归调用putSudoku从pos的索引0第一个空白格开始尝试填数同时传入一个find标志初始为false用于标记是否已经找到完整解。值得注意的一个实现细节board以*[][]byte指针方式传入递归find也以*bool指针传递保证递归各层之间共享同一份棋盘状态与已找到解的标志。3.3 递归函数 putSudoku尝试、落子、回退func putSudoku(board *[][]byte, pos []position, index int, succ *bool) { if *succ true { return } if index len(pos) { *succ true return } for i : 1; i 10; i { if checkSudoku(board, pos[index], i) !*succ { (*board)[pos[index].x][pos[index].y] byte(i) 0 putSudoku(board, pos, index1, succ) if *succ true { return } (*board)[pos[index].x][pos[index].y] . } } }该函数是整个算法的引擎逻辑分四层全局剪枝递归一开始就检查*succ一旦某条分支已经找到完整解立即终止后续所有分支的探索对应文档中找到一组解以后就不需要再继续回溯了直接返回即可的优化。递归出口index len(pos)表示所有空白格都已成功填完此时将*succ置为true标志着找到完整解。枚举候选数字for i : 1; i 10; i依次尝试数字1到9先经过checkSudoku三路校验通过且尚未找到解!*succ时才把数字写入棋盘byte(i) 0把整数转换为对应的 ASCII 字符。落子与回退写入后递归进入下一个空白格index1若递归返回后发现已找到解直接返回不再尝试否则说明当前数字导致死路回退——把该格重新写成.继续尝试下一个数字。这里的回退backtrack正是回溯算法区别于普通 DFS 的核心棋盘状态在递归返回后必须恢复到尝试前的样子保证兄弟分支的校验不受污染。3.4 校验函数 checkSudoku行、列、宫三路检查func checkSudoku(board *[][]byte, pos position, val int) bool { // 判断横行是否有重复数字 for i : 0; i len((*board)[0]); i { if (*board)[pos.x][i] ! . int((*board)[pos.x][i]-0) val { return false } } // 判断竖行是否有重复数字 for i : 0; i len((*board)); i { if (*board)[i][pos.y] ! . int((*board)[i][pos.y]-0) val { return false } } // 判断九宫格是否有重复数字 posx, posy : pos.x-pos.x%3, pos.y-pos.y%3 for i : posx; i posx3; i { for j : posy; j posy3; j { if (*board)[i][j] ! . int((*board)[i][j]-0) val { return false } } } return true }checkSudoku在(pos.x, pos.y)处尝试放入val前必须确认三处均无冲突任意一处重复即返回false行检查固定行号pos.x遍历整行 9 列跳过.若存在等于val的数字则冲突列检查固定列号pos.y遍历整列 9 行规则同上宫检查这是最巧妙的一步。通过pos.x - pos.x%3与pos.y - pos.y%3将当前坐标对齐到所在 3x3 宫的左上角再以双重循环遍历该宫 3x3 共 9 个单元格逐一比对。取模运算让任意坐标都能快速映射到其所属九宫格是本题的关键几何技巧。只有三路检查全部通过val才被允许写入棋盘。该函数在 核心源码 中有明确的注释标注三段检查的职责。四、测试用例与运行验证仓库为本题提供了完整的单测位于 37. Sudoku Solver_test.go包含两方面验证4.1 LeetCode 官方示例用例测试构造了 LeetCode 官方给出的数独谜题para37.s调用solveSudoku原地求解后与标准答案ans37.s对比para37{[][]byte{ {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}}4.2 分支覆盖测试测试文件还专门覆盖了putSudoku中*succ已为true时的提前返回分支见测试文件第 62-71 行的注释与代码构造一个already : true的初始标志调用putSudoku后断言already保持为true从而验证全局剪枝逻辑没有副作用。4.3 运行测试本仓库采用gotest.sh脚本统一执行全量测试并生成覆盖率报告见 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只针对本题目录运行go test -v ./leetcode/0037.Sudoku-Solver/项目模块声明为github.com/halfrost/LeetCode-Go见 go.mod测试代码与题解代码同属leetcode包直接复用仓库内的structures等辅助模块即可编译运行。五、复杂度分析从源码结构推断从代码实现可以推断出如下复杂度特征时间方面最坏情况下需要对每个空白格尝试 9 个数字每次尝试都要进行行、列、宫共 27 次比较理论最坏复杂度为指数级O(9^m)m为空白格数量但由于唯一解 找到即返回的剪枝实际求解速度远快于最坏情形LeetCode 官方案例几乎瞬间完成。空间方面递归深度等于空白格数量m最多 81辅助切片pos也最多容纳 81 个坐标因此空间复杂度为O(m)其中m为空格数。可优化方向基于本实现的扩展思考可以引入每行/每列/每宫候选数字位图bitmask把校验从线性扫描降为常数时间也可以采用 MRVMinimum Remaining Values优先填充候选数最少的格子启发式进一步加速——但就本题数据规模而言当前的简洁实现已经足够。六、小结通过本题可以完整掌握回溯算法的标准四步法约束定义行/列/宫不重复→ 状态收集空白格列表→ 递归尝试1-9 枚举 三路校验→ 失败回退恢复.。仓库实现用三个短小精悍的函数完成了从入口收集、递归求解到合法性校验的全部逻辑配合官方用例与分支覆盖测试是一份可直接运行、可直接复用的数独求解器参考实现。相关文档与代码路径汇总如下题解文档英文版website/content.en/ChapterFour/0001~0099/0037.Sudoku-Solver.md题解文档中文版leetcode/0037.Sudoku-Solver/README.md核心实现37. Sudoku Solver.go单元测试37. Sudoku Solver_test.go【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考