【结论先行】深度解析数独(Sudoku)背后的组合数学与计算机算法:①Felgenhauer & Jarvis 证明 9×9 数独共有 6,670,903,752,021,072,936,960(约667万兆)种有效终盘;②Gary McGuire 团队耗费 700 万 CPU 小时证明唯一解最少需要 17 个。
在很长一段时间里,数学界与数独爱好者都在寻找一个问题(俗称 Minimum Sudoku Problem)的答案:「最少只需要给出多少个提示数字,就能唯一确定整个 81 格数独?」人们找到了超过 49,000 道拥有唯一解的 17 提示数(17-Clue)数独,却始终找不到哪怕一道具有唯一解的 16 提示数数独。
2012年1月,爱尔兰都柏林大学(UCD)的数学家 Gary McGuire、Bastian Tugemann 与 Gilles Civario 发表了里程碑式的证明:他们并非盲目检查某一个终盘的所有 $\binom{81}{16} \approx 3.4 \times 10^{16}$ 种挖洞方式,而是利用了「不可避免集(Unavoidable Sets / 致命模式 Deadly Patterns)」的图论性质。
所谓「不可避免集」,是指终盘中的一组格子,如果这组格子里没有任何一格被设为初始提示数,那么只需把这组格子里的数字相互对调,就能在不违反任何行列宫规则的前提下得到第二个合法终盘(最典型的例子就是两行两列构成的 4 格可交换数对 $[a,b]$)。因此,任何具有唯一解的数独题目,其初始提示数集合 $C$ 必须是该终盘所有不可避免集的一个「命中集(Hitting Set)」——即每一个不可避免集中至少要有 1 个格子被给定为提示数。McGuire 团队编写了高效的命中集枚举算法,耗费约 700 万 CPU 小时穷举了全部 5,472,730,538 个非同构终盘,最终在数学上严格证明:没有任何一个 9×9 数独终盘存在大小为 16 的命中集!
在计算机科学中,求解或验证一道 9×9 数独是否具有唯一解,最经典的数学建模是将其转化为「精确覆盖问题(Exact Cover Problem)」,并使用图灵奖得主高德纳(Donald Knuth)提出的 Algorithm X 与舞蹈链(Dancing Links, DLX)双向十字链表结构。
| 精确覆盖矩阵维度 | 数量计算 | 数学含义 |
|---|---|---|
| 矩阵总行数 (Rows) | $9 \times 9 \times 9 = 729$ 行 | 代表「在第 $r$ 行、第 $c$ 列填入数字 $v$」的每一种可能决策。 |
| 单元格约束 (Cell Constraints) | 81 列 | 81 个格子中,每个格子必须且只能填入 1 个数字。 |
| 横行约束 (Row Constraints) | $9 \times 9 = 81$ 列 | 第 1〜9 横行中,数字 1〜9 必须各出现恰好 1 次。 |
| 竖列约束 (Column Constraints) | $9 \times 9 = 81$ 列 | 第 1〜9 竖列中,数字 1〜9 必须各出现恰好 1 次。 |
| 九宫格约束 (Box Constraints) | $9 \times 9 = 81$ 列 | 第 1〜9 个 3×3 宫中,数字 1〜9 必须各出现恰好 1 次(总计 $81 \times 4 = 324$ 列约束)。 |