数独求解器

数独里的数字是标签，不参与算术。每个空格从 1..9 中排除同行、同列和同一个 3×3 宫里已有的数字。求解器填入一个候选数，递归求解；子问题无解，就把这次填写还原为 0。

撤销属于算法。候选集合来自当前棋盘，失败的数字若未清除，就会变成下一条分支里的假约束。

用 MRV 选择空格

选择第一个空格也能得到正确解。最少剩余值（MRV）会检查所有空格，选择候选数最少的那个。数量相同按行优先顺序选格，候选数字按升序尝试，因此两种策略的执行顺序都固定。

MRV 优先暴露矛盾：一个候选意味着被迫选择，零个候选意味着当前分支无解。两个候选比六个候选更容易在决策附近发现错误。默认棋盘只改变选格代码，结果如下：

第一个空格策略得到相同解，但多做了 53 次试填和 53 次撤销。这个输入上的搜索树大小给出了 MRV 的效果。

候选函数把行、列、宫中的非零数字合并为 used 集合，再从 1..9 排除它们。选格时棋盘显示每个空格的候选数，便于核对最小值。使用第一个空格策略时，也能看到被它跳过的更小候选集合。

一个已知数如何改变搜索

下面的预设固定使用 MRV，只改变一个已知数：

固定正确值 7 会消除 MRV 轨迹中唯一一个有两种选择的决策，余下每格都只剩一个候选。

固定 4 没有造成重复，因此它局部合法，却无法扩展成完整解。试填两次后，一个空格没有候选数。求解器撤销这两次填写，遇到不可修改的已知数后报告无解，并恢复输入棋盘。局部合法不代表可以完成。

棋盘小、约束检查便宜、只需一个解时，直接回溯适合这类问题。批量处理难题可以维护行、列、宫的位掩码，减少集合重建。约束更多或需要穷举时，可考虑精确覆盖、SAT 或约束编程。

数独回溯如何工作

选定 (row, col) 后：

1. 没有空格，返回 true。
2. 所选空格没有候选数，返回 false。
3. 填入一个候选数，递归处理当前棋盘。
4. 子调用成功，返回 true，保留完成的棋盘。
5. 子调用失败，把该格恢复为 0，尝试下一个候选。
6. 候选全部失败，返回 false。

循环不变量是：每次试填之前，棋盘都等于本次调用收到的状态。深层调用撤销自己的填写，当前调用再清除自己的填写，下一候选就不会继承失败子树的残留。

求解器找到第一个解就停止，不统计解的数量，也不验证唯一性。

数独求解逐步演示

默认棋盘有 38 个已知数、43 个空格。MRV 首先选择 (0, 4)，候选为 [4, 7]。

1. 在 (0, 4) 试填 4。
2. MRV 在 (2, 4) 被迫填 7，再在 (2, 3) 填 3。
3. (2, 8) 的行、列、宫合起来排除了全部九个数字，子调用返回 false。
4. 清除 (2, 3) 的 3。该层没有第二个候选，返回 false。
5. 清除 (2, 4) 的 7。该层也没有其他候选。
6. 根调用清除 (0, 4) 的 4。候选记录保留 4 x，旁边是尚未尝试的 7。
7. 根调用改填 7，后面的选择都只有一个候选，棋盘完成。

算法试填 46 次、撤销 3 次，最大深度 43。播放器展示 33 个节拍：失败分支和三次撤销逐个显示，其余 41 次单候选填写合并成七个带标签的快进检查点。快进属于讲解节奏，代码仍逐次递归；检查点的棋盘和计数取自逐操作轨迹。

最终棋盘：

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

随后三个验证节拍分别检查所有行、列、宫。每个节拍可暂停，验证图形变绿，数字保持原色，便于看清正在验证的约束。

时间与空间复杂度

设空格数为 B，每格最多九个候选，宽松最坏时间上界为 O(9^B)。数独约束与 MRV 能减少搜索量，默认示例从 99 次填写降到 46 次，但不改变最坏指数级上界。

实现每次递归都扫描空格并重算候选。在固定 9×9 棋盘上，每次行、列、宫检查有常数上限。递归栈和试填路径最多保存 B 个选择，除棋盘外辅助空间为 O(B)。

MRV 改变搜索顺序，不改变正确性。在相同候选规则下，第一个空格策略具有相同解集，只可能探索更多失败分支。

边界情况

• 输入已完整且合法，第一次调用就返回 true，不试填。
• 已填格都局部合法，也可能有空格候选数为零，构成矛盾。
• 多解棋盘只返回固定搜索顺序中的第一个解，不能据此证明唯一性。
• 已知数重复应在递归前拒绝，不属于搜索函数的输入契约。本课会先验证全部预设。
• 无解预设没有重复已知数，但无法完成。全部试填撤销后才返回 None 或 null。

常见错误

• 漏掉 board[row][col] = 0。 失败数字会挡住本应合法的候选。
• 把零候选当成完成。 零候选是矛盾，没有空格才是完成。
• 第一个数字失败就返回 false。 当前格可能还有候选，失败返回应放在循环之后。
• 只查行和列。 漏掉 3×3 宫约束，可能得到拉丁方而非数独解。
• 修改已知数。 只有输入中的空格可以参与试填和撤销。
• 把 MRV 当成正确性的前提。 第一个空格策略也正确，只是在默认棋盘上搜索更多。