企业官网建设流程全解析

LeetCode-Go 题解 37：Sudoku 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. 数字1-9在每一行只能出现一次；
2. 数字1-9在每一列只能出现一次；
3. 数字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 辅助结构体 position

type 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) }

入口函数做两件事：

1. 收集空白格：双重循环扫描整个 9x9 棋盘，把每个值为'.'的单元格坐标压入pos切片。这一步决定了后续回溯的推进顺序——按行优先、自左向右逐个填充。
2. 启动递归：调用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, index+1, succ) if *succ == true { return } (*board)[pos[index].x][pos[index].y] = '.' } } }

该函数是整个算法的引擎，逻辑分四层：

1. 全局剪枝：递归一开始就检查*succ，一旦某条分支已经找到完整解，立即终止后续所有分支的探索（对应文档中"找到一组解以后就不需要再继续回溯了，直接返回即可"的优化）。
2. 递归出口：index == len(pos)表示所有空白格都已成功填完，此时将*succ置为true，标志着找到完整解。
3. 枚举候选数字：for i := 1; i < 10; i++依次尝试数字1到9，先经过checkSudoku三路校验通过，且尚未找到解（!*succ）时，才把数字写入棋盘（byte(i) + '0'把整数转换为对应的 ASCII 字符）。
4. 落子与回退：写入后递归进入下一个空白格index+1；若递归返回后发现已找到解，直接返回不再尝试；否则说明当前数字导致死路，回退——把该格重新写成'.'，继续尝试下一个数字。

这里的"回退"（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 < posx+3; i++ { for j := posy; j < posy+3; j++ { if (*board)[i][j] != '.' && int((*board)[i][j]-'0') == val { return false } } } return true }

checkSudoku在(pos.x, pos.y)处尝试放入val前，必须确认三处均无冲突，任意一处重复即返回false：

1. 行检查：固定行号pos.x，遍历整行 9 列，跳过'.'，若存在等于val的数字则冲突；
2. 列检查：固定列号pos.y，遍历整列 9 行，规则同上；
3. 宫检查：这是最巧妙的一步。通过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.sh）：

go test -covermode=atomic -coverprofile=coverage.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）"把校验从线性扫描降为常数时间；也可以采用 MRV（Minimum 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