数独与数学 - 谜题背后的组合学
数独是纯粹的逻辑谜题，但其背后蕴含着深刻的数学结构。完成盘面的总数、最小提示数的证明、通过对称群进行分类等，本文讲解数独的数学性质。
完成盘面的总数
9×9 数独的有效完成盘面约有 6.67×10^21 种。这个数字由 Bertram Felgenhauer 和 Frazer Jarvis 于 2005 年精确计算得出，为 6,670,903,752,021,072,936,960 种。然而考虑旋转、翻转、数字置换等对称性后，本质不同的盘面约为 54 亿种。「本质不同」的定义在数学上是严格的，被形式化为对称群下等价类的数量。
最小提示数的证明
数独谜题拥有唯一解所需的最小提示数为 17。这是 Gary McGuire 团队于 2012 年通过计算机穷举搜索证明的。结果表明 16 个及以下的提示数无法保证唯一解。但并非有 17 个提示数就一定有唯一解，根据分布模式可能存在多个解。已发现约 49,000 个拥有唯一解的 17 提示数谜题。
NP 完全性
推广的 n×n 数独（n^2×n^2 网格）的解的存在性判定已被证明是 NP 完全问题。这意味着随着谜题规模增大，找到解所需的计算时间可能呈指数增长。但标准的 9×9 数独是固定规模，实际上可以通过高效的回溯算法瞬间求解。NP 完全性是理论上的计算复杂度分类，限定在 9×9 时不构成实际问题。
数独与约束满足问题
对称性如何得出本质盘面数
完整盘面的总数与本质上不同的盘面数之间的差距，源于如何计算对称性。把盘面旋转 90 度、左右翻转，或交换数字的名称，只要逻辑结构相同，就可视为同一道题。把这些操作全部汇集起来，便构成一个对称群；以该群作用下能相互转化的盘面为同一族 (等价类) 重新计数，数字便压缩到约 54 亿。这里用到的计数定理称为伯恩赛德引理，它通过对每个对称操作下保持不变的盘面数求平均，来求出等价类的数目。仅仅引入对称这一视角，庞大的总数就被整理到差了若干数量级，这正表明数独并非单纯的游戏，而是拥有丰富组合结构的对象。
解的唯一性与数独的魅力
数独之所以有别于其他数字游戏，在于好题必有唯一解这一严格的约定。可能存在多解的题目会在中途逼迫你猜测，使你无法仅凭逻辑判定真伪。正因为唯一性得到保证，解题者才能怀着此处在逻辑上只能填这个数字的确信向前推进。这种唯一性在生成阶段由计数解的算法加以验证。用数学语言来说，唯一解是指约束满足问题的解空间收敛到唯一一点的状态，意味着提示的布局不多不少地指定了那一点。好题，正是用最少的线索把解空间锁定到一点的、精炼的信息设计之产物。
数独所联结的数学诸领域
数独乍看像是给孩子的数字游戏，但其背后交汇着组合论、图论、计算复杂性理论等多个现代数学领域。例如，把每个格子看作顶点，将同行、同列、同宫的格子以边相连，数独便可表述为图的着色问题，等价于用九种颜色着色、使相邻顶点不同色。此外，解的存在性判定在一般情形下属于 NP 完全，这表明数独与密码学、排程等现实难题共享同样的计算硬度。身边的一道谜题竟与理论计算机科学的重要问题一脉相连，正是研习数独的智识乐趣之一。