回溯法求解数独：LeetCode 37 解数独的三重占用标记剪枝与多语言实现解析

• 示例工程

数独求解是回溯（Backtracking）算法最经典的应用场景之一。本文以 doocs/leetcode 开源仓库中 0037.Sudoku Solver 的题解为骨架，完整讲解"行、列、3x3 宫三重占用标记 + 空格列表驱动 DFS"的解数独方案，并逐语言拆解仓库内 Python、Java、C++、Go、C#、PHP 六套实现，让你掌握一套可复用的数独求解模板，也能顺带理解「有效数独」判断与「求解数独」在数据结构上的承袭关系。读完本文，你既能把算法讲清楚，也能照着仓库代码写出任意语言的求解实现。



题目背景与规则

LeetCode 37「解数独」（Sudoku Solver）要求编写一个程序，通过填充空格来解决一个9 x 9的数独问题。空白的格子用字符'.'表示，填充后的数独必须同时满足以下三条规则：

1. 数字1-9在每一行只能出现一次；
2. 数字1-9在每一列只能出现一次；
3. 数字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 == 9
• board[i].length == 9
• board[i][j]是一位数字1-9或'.'
• 题目数据保证输入数独仅有一个解

"仅有一个解"这一保证非常关键：它意味着搜索过程中一旦找到一个可行解就可以立即终止，而不用继续枚举其他可能的填法。

为什么必须用回溯而不是暴力枚举

数独盘面最多有 81 个格子，极端情况下空格数量可达八十余个，每个空格有 9 种填法。如果直接枚举全部填法，搜索空间的上界是 $9^{81}$ 量级，完全不可行。因此搜索策略必须做到两点：

1. 尽早剪枝：一旦某个数字的填入违反了行、列、宫的约束，立即放弃该分支，不再向下探索；
2. 按约束查找：与其每填一个数字就重新扫描整张棋盘来检查冲突，不如预先用布尔标记把"哪些数字已经占用"记录下来，填数时 O(1) 判断。

仓库文档的思考过程（Thinking）明确点出了这个思路：与「有效的数独」相同，反复扫描棋盘以检查某数字是否已用的代价较高，所以先把已填数字记入row、col、block三张占用表，再只对空格列表t做搜索。

核心算法：三重占用标记 + 空格列表驱动的 DFS

整个算法可以拆成三个部分：数据结构定义、棋盘初始化扫描、递归回溯搜索。以下分析均对应仓库中的实际实现（如 Solution.py、Solution.java、Solution.cpp 等）。

1. 数据结构定义

用三个布尔数组分别记录占用情况：

• row[9][9]：row[i][v] == true表示数字v（0 基索引，对应字符'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个空格，递归逻辑如下：

1. 终止条件：若k == len(t)，说明所有空格都已填完，置ok = True并返回；
2. 取出当前空格坐标(i, j) = t[k]；
3. 枚举候选数字v（0..8，对应'1'..'9'）：仅当row[i][v]、col[j][v]、block[i//3][j//3][v]三个位置都未被占用时才尝试填入；
4. 写入并递归：占用三处标记、把board[i][j]写成str(v + 1)，然后dfs(k + 1)；
5. 回溯恢复：无论递归结果如何，撤销三处占用标记（把三处布尔值恢复为False）；
6. 截断：递归返回后若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存进List<Integer>，递归时用/ 9、% 9还原，字符与数字的换算用board[i][j] - '1'得到 0 基索引、用(char)(v + '1')写回：

class Solution { private boolean ok; private char[][] board; private List<Integer> 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]与vector<pair<int, int>> t，递归用支持自引用的泛型 lambda 表达：

class Solution { public: void solveSudoku(vector<vector<char>>& board) { bool row[9][9] = {false}; bool col[9][9] = {false}; bool block[3][3][9] = {false}; bool ok = false; vector<pair<int, 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 题解法。

进阶方向：从回溯到 Algorithm X / Dancing Links

值得说明的是，本题的 tags 中除了数组、哈希表、回溯、矩阵之外，还标注了Algorithm X（X 算法）与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 皇后、数独、排列组合）的通用心法。

• 示例工程