数独到底有多少种

题目

标准 9×9 数独（每行、每列、每宫都含 1–9 各一次），总共有多少种不同的完整解？

答案与解析

经过大量计算（菲利格豪尔与贾尔拉希 2005 年），答案是：

$6\,670\,903\,752\,021\,072\,936\,960 \approx 6.67\times10^{21}$

这是个天文数字，但算起来极难：直接枚举 $9^{81}$ 不可能，必须利用约束传播与对称性剪枝（行列/数字重标、旋转翻转等价类），把搜索空间压到可计算范围。

注意这是“完整解”数。若问“不同的谜面（挖空后）”有多少、以及“最少给几个提示仍可唯一解”（已知最少 17 个提示），又是更深的难题。

背后的数学

数独计数是精确覆盖（exact cover）与组合枚举的范例，可用舞蹈链（Dancing Links, Knuth）高效求解。它和拉丁方（Latin squares）、组合设计理论同源。一个看似报纸小游戏，背后是计数组合学里最烧脑的精确算术之一。