数独算法 - 求解器的原理与编程实现

最简单的数独求解器可以用回溯法（深度优先搜索）实现。找到空格，依次尝试 1-9 的数字，如果不违反约束就前进到下一个空格。违反时回退到上一个格子（回溯），尝试其他数字。这个算法一定能找到解，但最坏情况下需要尝试所有组合，效率很低。即使是 Easy 级别的谜题也可能需要数千次尝试。

大幅提升回溯效率的是约束传播（Constraint Propagation）。每次放置数字后，立即更新受影响的行、列、宫格的候选数。如果某格候选数变为 0，立即回溯（提前剪枝）。如果某格候选数变为 1，自动确定（自动应用显性单数）。通过约束传播，搜索空间被大幅缩减，大多数谜题无需回溯即可求解。

搜索顺序的优化也很重要。MRV（Minimum Remaining Values）启发式是优先搜索候选数最少的格子的策略。候选数为 2 的格子最多尝试 2 次就能确定，而候选数为 8 的格子最多需要 8 次。MRV 使搜索树的分支最小化，大幅减少回溯的发生频率。约束传播与 MRV 的组合可以在 1 毫秒内解出世界最难的谜题。

计算机求解器与人类解法有本质区别。计算机能精确管理所有候选数并快速回溯，因此「猜测后尝试」的方法很有效。而人类倾向于避免猜测，只用逻辑确定的步骤来解题。这是由人类工作记忆的限制决定的。回溯需要记住多个状态，对人类来说很困难。数独的难度设计正是以人类能否不猜测就解出为标准的。

数独求解器能瞬间解出，靠的是与人类无法相比的试错速度，与省去无用功的巧思相结合。仅凭朴素的回溯，对 9×9 这一固定规模也已足够快，因为计算机每秒可尝试数百万次数字摆放。而加入约束传播与搜索顺序优化后，试错次数本身骤减，连最难的题目也能瞬间了结。关键在于：速度的本质不仅在于处理之快，更在于如何聪明地缩小搜索范围。与其盲目地全部尝试，不如尽早砍掉显然无用的分支，这样的设计决定了效率。

在数学上，数独可表述为一种精确覆盖问题 (Exact Cover)。把在各格填入数字这一行为，表述为对应满足的约束集合恰好各覆盖一次的选择。以此视角，唐纳德·克努斯提出的称为 Dancing Links (DLX) 的算法便能极其高效地应用。DLX 是一种通过临时移除与还原链表元素来加速回溯的技法，不仅用于数独，也用于谜题快速求解之普遍场合。对同一问题换个视角，便能看见另一种强大解法——这正是计算机科学的乐趣之一。

数独求解器并非只为给出答案。在实用上更重要的，其实是谜题生成中对唯一解的验证，以及难度的估计。生成器用求解器来确认所造的题目是否真的只有一个解，并借助模拟人类解法的求解器判定需要哪些技巧。另一方面，用求解器来显示答案，可能是一种夺走解题乐趣、本末倒置的用法。求解器终究是幕后的工具，其真正价值，恰恰在于为给游玩者送上优质题目而进行的验证与分析。

试着自己写一个数独求解器，是极好的编程练习。因为回溯、递归、约束传播、搜索优化等计算机科学的基础概念，都浓缩在这一道谜题之中。先用朴素的穷举让它跑起来，再加入约束传播使其加速，进而在搜索顺序上下功夫。在这一逐步改良的过程中，你能亲身体会算法效率如何变化。既熟悉又易于核对答案的数独，是理想的学习题材，它教给你有别于解题之乐的、创造之乐。