示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载数独求解是回溯Backtracking算法最经典的应用场景之一。本文以 doocs/leetcode 开源仓库中 0037.Sudoku Solver 的题解为骨架完整讲解行、列、3x3 宫三重占用标记 空格列表驱动 DFS的解数独方案并逐语言拆解仓库内 Python、Java、C、Go、C#、PHP 六套实现让你掌握一套可复用的数独求解模板也能顺带理解「有效数独」判断与「求解数独」在数据结构上的承袭关系。读完本文你既能把算法讲清楚也能照着仓库代码写出任意语言的求解实现。题目背景与规则LeetCode 37「解数独」Sudoku Solver要求编写一个程序通过填充空格来解决一个9 x 9的数独问题。空白的格子用字符.表示填充后的数独必须同时满足以下三条规则数字1-9在每一行只能出现一次数字1-9在每一列只能出现一次数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。这与仓库中 0036. Valid Sudoku有效的数独 的判定规则完全一致区别在于36 题只要求判断已填入的数字是否冲突而 37 题要求求出完整解并把解直接写回传入的board。输入输出约定以原题给出的唯一示例为例输入一个9 x 9的字符数组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填充出完整解见上方唯一解盘面图。约束条件原题明确给出的约束如下board.length 9board[i].length 9board[i][j]是一位数字1-9或.题目数据保证输入数独仅有一个解仅有一个解这一保证非常关键它意味着搜索过程中一旦找到一个可行解就可以立即终止而不用继续枚举其他可能的填法。为什么必须用回溯而不是暴力枚举数独盘面最多有 81 个格子极端情况下空格数量可达八十余个每个空格有 9 种填法。如果直接枚举全部填法搜索空间的上界是 $9^{81}$ 量级完全不可行。因此搜索策略必须做到两点尽早剪枝一旦某个数字的填入违反了行、列、宫的约束立即放弃该分支不再向下探索按约束查找与其每填一个数字就重新扫描整张棋盘来检查冲突不如预先用布尔标记把哪些数字已经占用记录下来填数时 O(1) 判断。仓库文档的思考过程Thinking明确点出了这个思路与「有效的数独」相同反复扫描棋盘以检查某数字是否已用的代价较高所以先把已填数字记入row、col、block三张占用表再只对空格列表t做搜索。核心算法三重占用标记 空格列表驱动的 DFS整个算法可以拆成三个部分数据结构定义、棋盘初始化扫描、递归回溯搜索。以下分析均对应仓库中的实际实现如 Solution.py、Solution.java、Solution.cpp 等。1. 数据结构定义用三个布尔数组分别记录占用情况row[9][9]row[i][v] true表示数字v0 基索引对应字符1到9已经在第i行出现过col[9][9]col[j][v] true表示数字v已经在第j列出现过block[3][3][9]block[i/3][j/3][v] true表示数字v已经在格子(i, j)所在的 3x3 宫出现过。这里i // 3、j // 3把 9x9 棋盘折叠成 3x3 的宫索引是一个值得记住的取模技巧。此外还需要一个空格列表t按扫描顺序存放所有空白格子的坐标以及一个标志位ok用于在找到解后立即截断后续搜索。2. 初始化把已填数字写入占用表在递归开始前对棋盘做一次全量扫描若board[i][j] .把坐标(i, j)追加到空格列表t否则把该数字对应的 0 基索引v同步标记到row[i][v]、col[j][v]、block[i//3][j//3][v]三个位置。以 Python 实现为例与仓库 Solution.py 一致row [[False] * 9 for _ in range(9)] col [[False] * 9 for _ in range(9)] block [[[False] * 9 for _ in range(3)] for _ in range(3)] t [] ok False for i in range(9): for j in range(9): if board[i][j] .: t.append((i, j)) else: v int(board[i][j]) - 1 row[i][v] col[j][v] block[i // 3][j // 3][v] True这一步的妙处在于初始化时就把存量数字的占用信息一次性收集完毕后续搜索过程不再需要任何线性扫描。3. 递归回溯dfs(k)填第 k 个空格dfs(k)负责处理空格列表中的第k个空格递归逻辑如下终止条件若k len(t)说明所有空格都已填完置ok True并返回取出当前空格坐标(i, j) t[k]枚举候选数字v0..8对应1..9仅当row[i][v]、col[j][v]、block[i//3][j//3][v]三个位置都未被占用时才尝试填入写入并递归占用三处标记、把board[i][j]写成str(v 1)然后dfs(k 1)回溯恢复无论递归结果如何撤销三处占用标记把三处布尔值恢复为False截断递归返回后若ok True立即return不再尝试其他候选数字。用 Python 表述即为def dfs(k): nonlocal ok if k len(t): ok True return i, j t[k] for v in range(9): if row[i][v] col[j][v] block[i // 3][j // 3][v] False: row[i][v] col[j][v] block[i // 3][j // 3][v] True board[i][j] str(v 1) dfs(k 1) row[i][v] col[j][v] block[i // 3][j // 3][v] False if ok: return这里有三个细节值得强调为什么回溯时要恢复标记当前分支如果走不通或者虽然走通了但被截断必须把尝试过的状态撤销否则会影响兄弟分支的判断。文档明确指出回溯时恢复占用标记成功路径上棋盘中的数字予以保留——也就是说找到解的那条递归路径上写入的数字不会被撤销因为ok True后循环里不会再进入新的分支。为什么ok能起到截断作用在dfs(k)的 for 循环中一旦某个v的递归返回后ok为真说明完整解已找到立即退出循环并逐层向上返回避免无意义的继续枚举。为什么用空格列表而非按坐标遍历把搜索推进顺序固定为先扫到的空格先填配合k索引即可判断终止实现简洁且天然有序。多语言实现对照仓库为本题提供了 Python3、Java、C、Go、C#、PHP 六种语言的完整实现核心逻辑完全一致只是语法与字符处理方式不同。这里逐一列出与仓库文档及对应Solution.*文件一致。Java 实现Java 版本把空格坐标编码为i * 9 j存进ListInteger递归时用/ 9、% 9还原字符与数字的换算用board[i][j] - 1得到 0 基索引、用(char)(v 1)写回class Solution { private boolean ok; private char[][] board; private ListInteger t new ArrayList(); private boolean[][] row new boolean[9][9]; private boolean[][] col new boolean[9][9]; private boolean[][][] block new boolean[3][3][9]; public void solveSudoku(char[][] board) { this.board board; for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (board[i][j] .) { t.add(i * 9 j); } else { int v board[i][j] - 1; row[i][v] col[j][v] block[i / 3][j / 3][v] true; } } } dfs(0); } private void dfs(int k) { if (k t.size()) { ok true; return; } int i t.get(k) / 9, j t.get(k) % 9; for (int v 0; v 9; v) { if (!row[i][v] !col[j][v] !block[i / 3][j / 3][v]) { row[i][v] col[j][v] block[i / 3][j / 3][v] true; board[i][j] (char) (v 1); dfs(k 1); row[i][v] col[j][v] block[i / 3][j / 3][v] false; } if (ok) { return; } } } }C 实现C 版本使用栈上数组bool row[9][9]、bool block[3][3][9]与vectorpairint, int t递归用支持自引用的泛型 lambda 表达class Solution { public: void solveSudoku(vectorvectorchar board) { bool row[9][9] {false}; bool col[9][9] {false}; bool block[3][3][9] {false}; bool ok false; vectorpairint, int t; for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (board[i][j] .) { t.push_back({i, j}); } else { int v board[i][j] - 1; row[i][v] col[j][v] block[i / 3][j / 3][v] true; } } } auto dfs - void { if (k t.size()) { ok true; return; } int i t[k].first, j t[k].second; for (int v 0; v 9; v) { if (!row[i][v] !col[j][v] !block[i / 3][j / 3][v]) { row[i][v] col[j][v] block[i / 3][j / 3][v] true; board[i][j] v 1; dfs(k 1); row[i][v] col[j][v] block[i / 3][j / 3][v] false; } if (ok) { return; } } }; dfs(0); } };Go 实现Go 版本用var row, col [9][9]bool、var block [3][3][9]bool与var t [][2]int递归通过闭包var dfs func(int)自引用字节换算为int(board[i][j] - 1)与byte(v 1)func solveSudoku(board [][]byte) { var row, col [9][9]bool var block [3][3][9]bool var t [][2]int ok : false for i : 0; i 9; i { for j : 0; j 9; j { if board[i][j] . { t append(t, [2]int{i, j}) } else { v : int(board[i][j] - 1) row[i][v], col[j][v], block[i/3][j/3][v] true, true, true } } } var dfs func(int) dfs func(k int) { if k len(t) { ok true return } i, j : t[k][0], t[k][1] for v : 0; v 9; v { if !row[i][v] !col[j][v] !block[i/3][j/3][v] { row[i][v], col[j][v], block[i/3][j/3][v] true, true, true board[i][j] byte(v 1) dfs(k 1) row[i][v], col[j][v], block[i/3][j/3][v] false, false, false } if ok { return } } } dfs(0) }C# 实现C# 版本使用多维数组bool[,] row new bool[9, 9]、bool[,,] block new bool[3, 3, 9]空格列表为List(int, int)递归以局部函数void Dfs(int k)实现public class Solution { public void SolveSudoku(char[][] board) { bool[,] row new bool[9, 9]; bool[,] col new bool[9, 9]; bool[,,] block new bool[3, 3, 9]; bool ok false; var t new List(int, int)(); for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (board[i][j] .) { t.Add((i, j)); } else { int v board[i][j] - 1; row[i, v] col[j, v] block[i / 3, j / 3, v] true; } } } void Dfs(int k) { if (k t.Count) { ok true; return; } var (i, j) t[k]; for (int v 0; v 9; v) { if (!row[i, v] !col[j, v] !block[i / 3, j / 3, v]) { row[i, v] col[j, v] block[i / 3, j / 3, v] true; board[i][j] (char)(v 1); Dfs(k 1); if (ok) return; row[i, v] col[j, v] block[i / 3, j / 3, v] false; } } } Dfs(0); } }PHP 实现PHP 版本用array_fill构造三维占用表$dfs闭包通过use ($dfs, ...)引用传递共享状态字符换算使用ord()/chr()class Solution { /** * param String[][] $board * return NULL */ function solveSudoku($board) { $row array_fill(0, 9, array_fill(0, 9, false)); $col array_fill(0, 9, array_fill(0, 9, false)); $block array_fill(0, 3, array_fill(0, 3, array_fill(0, 9, false))); $ok false; $t []; for ($i 0; $i 9; $i) { for ($j 0; $j 9; $j) { if ($board[$i][$j] .) { $t[] [$i, $j]; } else { $v ord($board[$i][$j]) - ord(1); $row[$i][$v] true; $col[$j][$v] true; $block[intval($i / 3)][intval($j / 3)][$v] true; } } } $dfs function ($k) use ($dfs, $board, $row, $col, $block, $ok, $t) { if ($k count($t)) { $ok true; return; } [$i, $j] $t[$k]; for ($v 0; $v 9; $v) { if (!$row[$i][$v] !$col[$j][$v] !$block[intval($i / 3)][intval($j / 3)][$v]) { $row[$i][$v] $col[$j][$v] $block[intval($i / 3)][intval($j / 3)][$v] true; $board[$i][$j] chr($v ord(1)); $dfs($k 1); if ($ok) { return; } $row[$i][$v] $col[$j][$v] $block[intval($i / 3)][intval($j / 3)][ $v ] false; } } }; $dfs(0); } }可以看出六种实现共享同一个算法骨架初始化三张占用表 → 收集空格列表 → 按k索引递归填数 → 命中即截断、未中即回溯。语言差异只体现在坐标编码方式元组 / 整数编码 /pair和字符与索引的换算ord/chr、char强转、byte强转上。复杂度分析从代码结构可以推断本算法的时间与空间特征空间复杂度占用表row、col各 81 个布尔位block81 个布尔位加上空格列表与递归栈均与盘面规模线性相关可视为 $O(81)$ 的常量级辅助空间不把输出棋盘计入。时间复杂度最坏情况下每个空格要枚举 9 个候选数字递归深度等于空格数 $m$上界约为 $O(9^m)$但由于行、列、宫的占用检查把大量分支在极浅层就剪掉实际求解速度远优于暴力枚举。这也是文档强调必须在违反约束时立即停止的原因所在。与「有效的数独」的关系一脉相承的占用表本解的构思与仓库中 0036. Valid Sudoku 高度同源。36 题用三张布尔表在一次遍历中判断冲突row[i][num]、col[j][num]、sub[k][num]其中宫号k i / 3 * 3 j / 3见该题 Solution.java。37 题把同样的占用表从判重升级为搜索剪枝维度36 有效数独37 解数独目标判断已有数字是否冲突求出完整解并原地写回占用表row、col、sub9x9row、col9x9block3x3x9搜索无空格列表tdfs(k)ok截断宫索引i / 3 * 3 j / 3i / 3、j / 3直接做三维下标可以说掌握了 36 题的占用表思路再叠加空格列表 回溯 截断三层机制就是完整的 37 题解法。进阶方向从回溯到 Algorithm X / Dancing Links值得说明的是本题的 tags 中除了数组、哈希表、回溯、矩阵之外还标注了Algorithm XX 算法与Dancing Links舞蹈链见文档 Front Matter 的 tags 字段英文版为 Algorithm X、Dancing Links中文版为 X 算法。这意味着数独在精确覆盖Exact Cover模型下还有更高级的解法把每个位置-数字候选映射为列约束行列宫 324 列用舞蹈链的删除/恢复操作高效搜索。仓库当前给出的官方题解是回溯法对于想深入掌握精确覆盖建模与双向链表删恢复机制的读者可以沿着该标签方向继续研究但本文所展示的回溯方案已经是竞赛与面试中最通用、最易实现的版本。仓库内的参考文件题目与解法全量文档中文solution/0000-0099/0037.Sudoku Solver/README.md题目与解法全量文档英文solution/0000-0099/0037.Sudoku Solver/README_EN.md各语言独立源码Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.cs、Solution.php均位于 solution/0000-0099/0037.Sudoku Solver/ 目录下姊妹题「有效的数独」solution/0000-0099/0036.Valid Sudoku/README.md题目示例图片images/ 目录下的题目图与解图把本文的dfs(k)模板套用到其他语言、加上候选数最少优先等启发式优化如先填候选数最少的空格即可在竞赛环境下进一步提速而理解ok截断与回溯恢复的配合则是所有求一个可行解类回溯问题八皇后、N 皇后、数独、排列组合的通用心法。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 37. 解数独doocs/leetcode 仓库中的回溯算法多语言实现详解LeetCode 37. 解数独doocs/leetcode 仓库中的回溯算法多语言实现详解 导读 本文以 doocs/leetcode 开源仓库中 Leet示例工程LeetCode数独求解回溯算法剪枝优化终极指南LeetCode数独求解回溯算法剪枝优化终极指南 数独作为经典的逻辑推理游戏其求解算法一直是LeetCode热门面试题。本文将深入探讨回溯法在数独求解中的应示例工程LeetCode 37. Sudoku Solver 题解用 Go 实现 DFS 回溯求解数独LeetCode 37. Sudoku Solver 题解用 Go 实现 DFS 回溯求解数独 本篇以 leetcode/0037.Sudoku Solver示例工程上一篇BabelDOC 中间层翻译器ILTranslator深度解析占位符驱动的 PDF 版式保持翻译架构下一篇WTF-Solidity 教程精讲ERC4626 代币化金库标准——从标准接口到金库合约实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考