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

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

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

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

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