数独的数量

数独

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline & 3 & & & & & & &\\ \hdashline & & 6 & & 1 & & 2 & &\\ \hdashline 7 & & 8 & 5 & 9 & 4 & & & 3\\ \hline & & & & & & & & 6\\ \hdashline 8 & & 2 & 3 & 6 & & & &\\ \hdashline & & & & 7 & 5 & & &\\ \hline & 6 & & 4 & & & 3 & 7 &\\ \hdashline 5 & & & 7 & 3 & & 4 & &\\ \hdashline & & 3 & 9 & 8 & 2 & & & 1\\ \hline \end{array}\]

我是喜欢玩数独游戏的人，最开始接触数独应该是小时候，不过那个时候还不太懂得规则，后来工作之后偶然在闲暇时候玩起来数独，就疯狂的爱上了这种纯粹做逻辑推导得出结论的小游戏。玩了这么多年，期间也思考过能否写一个程序来解出数独，仔细思考后发现并没有什么比较优秀的算法，在网上也能看到各路大神写的解数独程序，不过大致也是暴力回溯加剪枝的做法。于是就不了了之了。想了解的朋友可以直接看 wiki Sudoku_solving_algorithms

最近我又开始玩数独，突然开始思考起玩了那么久的数独，是否会有一天把所有的数独都玩过一遍呢？于是数独到底有多少种？这样一个问题出现在脑袋里。

拉丁方

要求解这个问题，首先得分析数独的特征。回忆组合数学的内容，可以很容易的理解数独一定是 9 阶拉丁方的一个子集。如果有不清楚的朋友，一句话就能理解，拉丁方就是一种 $n * n$ 的方阵，恰好每一种元素在同一行同一列里只出现一次。为什么说数独是 9 阶拉丁方的子集呢？因为数独还要求在每一个 3 阶方阵里 0 - 9 也只出现一次，比如下面是一个合法的 9 阶拉丁方，但这不是一个合法的数独：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2\\ \hdashline 2 & 1 & 9 & 8 & 7 & 6 & 5 & 4 & 3\\ \hdashline 3 & 2 & 1 & 9 & 8 & 7 & 6 & 5 & 4\\ \hline 4 & 3 & 2 & 1 & 9 & 8 & 7 & 6 & 5\\ \hdashline 5 & 4 & 3 & 2 & 1 & 9 & 8 & 7 & 6\\ \hdashline 6 & 5 & 4 & 3 & 2 & 1 & 9 & 8 & 7\\ \hline 7 & 6 & 5 & 4 & 3 & 2 & 1 & 9 & 8\\ \hdashline 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 9\\ \hdashline 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\ \hline \end{array}\]

对于拉丁方，已经有非常明确的公式给出其精确值了，详情可以参见 wiki Latin_square¹

\[{\displaystyle L_{n}=n!\sum _{A\in B_{n}}^{}(-1)^{\sigma _{0}(A)}{\binom {\operatorname {per} A}{n}},}\]

想要了解上述公式是如何推导出的，可以参看《A Course in Combinatorics》 的第 17 章节 Latin squares²

对于拉丁方的数量，随着阶数的提升，其数量膨胀的非常快，超过 11 阶的拉丁方数量已经无法计算出精确值了，详情可见下表：

size	all Latin squares of size n
1	1
2	2
3	12
4	576
5	161280
6	812851200
7	61479419904,000
8	108776032459082956800
9	5524751496156892842531225600
10	9982437658213039871725064756920320000
11	776966836171770144107444346734230682311065600000

不过 9 阶拉丁方的数量是明确的，也就意味着我们想要知道的数独数量应该比这个值要小：

\[5524751496156892842531225600\]

如何求数独的数量

在这个网站³上给出了数独的精确数量，并且给出了证明的过程跟代码，对代码感兴趣的朋友可以仔细阅读一下。

简单来说就是分析出数独的类型，然后用程序对每一种情况进行验证，当然由于 9 阶拉丁方的总数量是如此的大，所以我们需要想出一个分类办法来减少我们需要验证的数量，这样才能让写出的验证程序有可行性。

这里我简单翻译下 Bertram Felgenhauer 跟 Frazer Jarvis 的论文 Enumerating possible Sudoku grids⁴，描述了他们是如何对数独进行分类来减少验证过程的，这个比较有意思。详情可以参看这篇论文 。

简化计算

一、置换数字

首先我们根据拉丁方的性质可以知道，对一个数独采用数字置换的方式并不改变数独本身的性质，如果对这条感到疑惑可以自己操作一下，或者参见上面的 wiki¹。

我们把数独分成 9 个小方阵如下标记：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline & & & & & & & &\\ \hdashline & B1 & & & B2 & & & B3 &\\ \hdashline & & & & & & & &\\ \hline & & & & & & & &\\ \hdashline & B4 & & & B5 & & & B6 &\\ \hdashline & & & & & & & &\\ \hline & & & & & & & &\\ \hdashline & B7 & & & B8 & & & B9 &\\ \hdashline & & & & & & & &\\ \hline \end{array}\]

我们通过数字置换，也就是把数独中任意两个数字调换位置的方式来使得左上角的 B1 变成一个标准型的 3 阶拉丁方：

\[\begin{array}{|c:c:c|} \hline 1 & 2 & 3\\ \hdashline 4 & 5 & 6\\ \hdashline 7 & 8 & 9\\ \hline \end{array}\]

这意味着我们只需要验证这种标准型的情况，就能够得到所有的情况，因为其他情况可以通过置换数字获得，这一下子就使得我们需要验证的情况缩减了 $9! = 362880$ 倍。

我们的思路是针对标准型的 B1 块，我们计算出有多少种 B2 跟 B3 的情况存在，然后推广到整个数独。

二、计算 B2 和 B3

首先我们考虑 B2、B3 的第一行，只可能是以下 20 种情况之一：

\[\begin{array}{c|ccc|c} \{4,5,6\} & \{7,8,9\} & & \{7,8,9\} & \{4,5,6\}\\ \{4,5,7\} & \{6,8,9\} & & \{6,8,9\} & \{4,5,7\}\\ \{4,5,8\} & \{6,7,9\} & & \{6,7,9\} & \{4,5,8\}\\ \{4,5,9\} & \{6,7,8\} & & \{6,7,8\} & \{4,5,9\}\\ \{4,6,7\} & \{5,8,9\} & & \{5,8,9\} & \{4,6,7\}\\ \{4,6,8\} & \{5,7,9\} & & \{5,7,9\} & \{4,6,8\}\\ \{4,6,9\} & \{5,7,8\} & & \{5,7,8\} & \{4,6,9\}\\ \{5,6,7\} & \{4,8,9\} & & \{4,8,9\} & \{5,6,7\}\\ \{5,6,8\} & \{4,7,9\} & & \{4,7,9\} & \{5,6,8\}\\ \{5,6,9\} & \{4,7,8\} & & \{4,7,8\} & \{5,6,9\} \end{array}\]

其中每种情况下，例如首行是 ${4,5,6},{7,8,9}$ 时，B1 - B3 的填充情况可能如下：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 2 & 3 & \{4 & 5 & 6\} & \{7 & 8 & 9\}\\ \hdashline 4 & 5 & 6 & \{7 & 8 & 9\} & \{1 & 2 & 3\}\\ \hdashline 7 & 8 & 9 & \{1 & 2 & 3\} & \{4 & 5 & 6\}\\ \hline \end{array}\]

而不难发现，B2、B3 的每一行中的 3 个数字任意调换顺序都是可行的，同时有 6 行需要填充，所以这里其实有 $(3!)^6$ 种不同情况。上述 20 种情况每一种都有这么多相同的全排列变换。

再仔细分析我们可以这么分类，我们发现 B2 的第一行要么是跟 B1 的第二行或者第三行完全相同（这里有 2 种情况 ${4,5,6}$ 和 ${7,8,9}$），要么是由 B1 的第二行和第三行里的数字交错形成的（这里就有剩余的 18 种情况）。

当 B2 的第一行是由 B1 的第二行和第三行里的数字交错形成的情况下。我们发现其中一定可以按照如下的规则替换。例如当第一行是 ${4,5,7},{6,8,9}$ 时，${4,5,7}$ 就是混合了 B1 的第二行的 4,5 和 第三行的 7，其中 a，b，c 代表剩余的数字 1,2,3，他们相互之间可以有 3 种替换情况。

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 2 & 3 & \{4 & 5 & 7\} & \{6 & 8 & 9\}\\ \hdashline 4 & 5 & 6 & \{8 & 9 & a\} & \{7 & b & c\}\\ \hdashline 7 & 8 & 9 & \{6 & b & c\} & \{4 & 5 & a\}\\ \hline \end{array}\]

所以在这种情况下还需要再乘以 3。

所以对于 B2、B3 我们得出一共的情况是：

\[2 × (3!)^6 + 18 × 3 × (3!)^6 = 56 × (3!)^6 = 2612736\]

这样对于 B1、B2、B3 来说，B1 里的所有数字可以做一次全排列，所以数独的前三行的所有情况是：

\[9! × 2612736 = 948109639680\]

三、继续分类降低暴力搜索规模

目前我们得到了前三行的所有情况的数量，但是要遍历 B2、B3 的 $2612736$ 种情况依然是非常耗时的，所以我们需要继续降低搜索规模。前面我们提到过一种置换数字的方式不会改变数独的性质。这里我们考虑另外一种操作，比如我们交换整个 B2、B3 这两个方阵，这样我们发现之前所有完成 B2-B3 的填充情况，也可以通过交换 B5、B6 和交换 B8、B9 来同样满足数独要求。所以其实我们可以全排列 B1、B2、B3 来降低搜索规模。虽然这样会破坏 B1 是标准型这个最开始的要求，但是我们依然可以通过前面提到的数字置换的方式来让 B1 再次恢复标准型。

更进一步，我们可以交换 B1、B2、B3 的任意两行或者任意两列，然后通过数字置换的方式让 B1 恢复标准型，而不改变数独的性质。

所以针对 B2、B3 的 $2612736$ 种情况，我们按照如下方式进行分类：

1. 交换 B2、B3 各自方阵中的任意列来使得他们各自的第一排的数字处于升序状态；
2. 交换 B2、B3 整个方阵来使得 B2 的左上角数字比 B3 的左上角数字小；

第一个步骤，B2、B3 的列有 6 种情况，所以一共有 $6^2=36$ 种，第二个步骤把 $36 * 2$ 了，所以这样一来，我们可以把需要遍历的数据减少 $72$ 倍，也就是 $2612736 / 72 = 36288$ 种情况了。

然后对于每种情况，其实 B1-B2-B3 是可以全排列不改变性质的，同时对于每一个方阵，里面的 3 列也是可以全排列不改变性质的，所以我们还可以把需要遍历的总数减少 $6^4=1296$ 倍。当然，这样处理之后依然需要用数字置换的方式让 B1 恢复标准型，然后再用上面的两步来处理 B2-B3。

这 $1296$ 种情况，每种情况都有一对新的 B2-B3 出现，也就有相同的完成整个数独的填充数量。通过计算，我们发现这样一来，我们只需要检查 $2051$ 种可能的 B2-B3 的情况，而且这些情况中绝大部分都来自只来自于 $36288$ 中的 $18$（$18=6^4/72$） 种，虽然依然有少部分来自剩余的情况，所以还是得存储 $36288$ 种不同情况的给定块。

同样的，我们可以对前面的 3 行采取同样的全排列手段，然后数字置换让 B1 恢复标准型，通过上面两步来让 B2、B3 满足我们的分类要求。这样会继续减少我们的搜索情况到只有 416。

举个操作的例子来说明一下，假设前三行如下：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 2 & 3 & 4 & 5 & 8 & 6 & 7 & 9\\ \hdashline 4 & 5 & 6 & 1 & 7 & 9 & 2 & 3 & 8\\ \hdashline 7 & 8 & 9 & 2 & 3 & 6 & 1 & 4 & 5\\ \hline \end{array}\]

然后我们交换 B1 的第一列和第二列得到如下（交换行的情况也是类似）：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 2 & 1 & 3 & 4 & 5 & 8 & 6 & 7 & 9\\ \hdashline 5 & 4 & 6 & 1 & 7 & 9 & 2 & 3 & 8\\ \hdashline 8 & 7 & 9 & 2 & 3 & 6 & 1 & 4 & 5\\ \hline \end{array}\]

B1 此时不再是我们要求的标准型了，所以我们通过置换数字 1-2、4-5、7-8 来恢复 B1 为标准型：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 2 & 3 & 5 & 4 & 7 & 6 & 8 & 9\\ \hdashline 4 & 5 & 6 & 2 & 8 & 9 & 1 & 3 & 7\\ \hdashline 7 & 8 & 9 & 1 & 3 & 6 & 2 & 5 & 4\\ \hline \end{array}\]

现在 B1 是标准型了，但是 B2-B3 不满足我们的顺序要求了，然后我们执行之前的两步，来使 B2-B3 恢复我们的分类要求：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8 & 9\\ \hdashline 4 & 5 & 6 & 8 & 2 & 9 & 1 & 3 & 7\\ \hdashline 7 & 8 & 9 & 3 & 1 & 6 & 2 & 5 & 4\\ \hline \end{array}\]

这样的前三行跟我们最开始假设的那个前三列是拥有相同的数独填充数量的，因为我们所有的变化都保持了数独性质的不变性。所以我们可以认为这两种前三行的情况是相同的。这样就说明了我们上面减少规模的操作是正确的。

还有其他方式可以减少搜索规模吗？让我们假设一下前三行如下：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 2 & 3 & 4 & 5 & 8 & 6 & 7 & 9\\ \hdashline 4 & 5 & 6 & 1 & 7 & 9 & 2 & 3 & 8\\ \hdashline 7 & 8 & 9 & 2 & 3 & 6 & 1 & 4 & 5\\ \hline \end{array}\]

注意圈出来的数字 8 和 9

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 2 & 3 & 4 & 5 & ⑧ & 6 & 7 & ⑨\\ \hdashline 4 & 5 & 6 & 1 & 7 & ⑨ & 2 & 3 & ⑧\\ \hdashline 7 & 8 & 9 & 2 & 3 & 6 & 1 & 4 & 5\\ \hline \end{array}\]

我们置换 8 和 9，很容易发现数独的任何一种满足这三行的填充方法同样满足如下的前三行：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline 1 & 2 & 3 & 4 & 5 & ⑨ & 6 & 7 & ⑧\\ \hdashline 4 & 5 & 6 & 1 & 7 & ⑧ & 2 & 3 & ⑨\\ \hdashline 7 & 8 & 9 & 2 & 3 & 6 & 1 & 4 & 5\\ \hline \end{array}\]

所以这种情况我们应该只搜索其中一种就够了，那么还有多少类似的这种不变数字对呢？4、7 列的 (1,2)，1、4 列的 (1,4)，2、9 列的 (5,8)，3、6 列的 (6,9)（当然如果 B1 不再是标准型了依然需要通过数字置换成为标准型）。

进一步，我们会发现，其实只要任何在两行或者两列拥有相同数字的组合，都可以使用这种技巧来替换，比如：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline ① & ② & 3 & ④ & 6 & 7 & ⑤ & 8 & 9\\ \hdashline ④ & ⑤ & 6 & 8 & ① & 9 & 3 & ② & 7\\ \hdashline 7 & 8 & 9 & ② & ⑤ & 3 & ① & ④ & 6\\ \hline \end{array}\]

这三行跟下面三行获得的数独数量是完全一致的：

\[\begin{array}{|c:c:c|c:c:c|c:c:c|} \hline ④ & ⑤ & 3 & ② & 6 & 7 & ① & 8 & 9\\ \hdashline ① & ② & 6 & 8 & ⑤ & 9 & 3 & ④ & 7\\ \hdashline 7 & 8 & 9 & ④ & ① & 3 & ⑤ & ② & 6\\ \hline \end{array}\]

所以通过找 2 * 2、3 * 2、2 * 3、4 * 2 的形式可以把剩余的 416 种情况缩减到 71 种。实际通过计算，发现这 71 种中其实只有 44 种不同类型，不过 71 已经可以接受了，不必继续分类了。

总结

通过分类，我们可以看到最开始的任意 B1-B2-B3 的组合完全等价于最终的 44 种组合。我们只需要搜索这 44 种 B1-B2-B3 的组合的所有数独就可以得到数独的总数。

接下来只需要暴力搜索 44 种 B2-B3 的组合的情况下，如何填充满其他的格子。这里还有一些优化可以做，比如对于 B4、B7，我们也可以采用类似 B2、B3 的处理方式让其保持数字顺序，这样同样可以减少 72 种情况。当然， 上面我们用到的降低搜索规模的其他方式一样可以应用在 B4、B7上，但没有太大的实际意义了，在我们前面的努力下，基本上在普通电脑上，可以在几分钟内得出结果。

所以通过这番操作，程序计算出所有的数独数量是：

\[6670903752021072936960\]

后记

他们在一年后更新了他们的论文内容，其实主要是写的更加清晰了，可以查看这里⁵

后记二

同年，Ed Russell 跟 Frazer Jarvis 又继续分析了数独的情况，因为之前查找的数量是完全认为有一点不同就觉得是两个数独，比如通过数字置换或者旋转之类的操作能够完全一致的数独也被认为是两个完全不同的数独。但是这明显是不妥的，因为如果仅仅只是通过数字置换就能一样的数独，其实从各种意义上来说都应该看作两个相同的数独。因为如果你做一个数独游戏，你出这样变化可以一致的数独给人来玩，解法一定是一致或者类似的，从而并不好玩。

所以他们又设定了一些规则，如果通过这些规则变化能够一样的数独，被认为是相同的数独。这样就可以得到完全性质不一样的数独的数量。这篇论文在这里⁶。我就不作翻译了，感兴趣的朋友可以看看。

这些规则如下：

• 数字置换
• 镜像
• 旋转
• 重新排列所有块的 1-3，4-6，7-9 列
• 重新排列所有块的 1-3，4-6，7-9 行
• 重新排列 1-3 列
• 重新排列 1-3 行
• 重新排列 4-6 列
• 重新排列 4-6 行
• 重新排列 7-9 列
• 重新排列 7-9 行

通过这些限制，实际上完全不同的数独的数量是：

\[5472730538\]

54 亿多的数独，如果我每秒可以解开一个，需要 174 年 ：D

参考