← StudyX Devlog

数独的答案盘面一共有多少种

Hiroki ObaraHiroki Obara · DeveloperSudoku365使用指南
数独的答案盘面一共有多少种

上一篇 数独的答案只有一个 介绍了2012年证明提示数最少要17个的研究。文中顺带提到了两个数:完整盘面一共约有 6.67×10²¹ 种,本质上不同的约有54.7亿种。

这篇文章把这两个数再仔细看一看:它们是怎么数出来的,「本质上不同」又是什么意思。

数的是「答案盘面」

这里数的不是题目,而是所有格子都填满的答案盘面。问题是:每一行、每一列、每一个3×3的宫里,1到9都正好出现一次的盘面,一共有多少种。

题目的数量比答案盘面多得多。因为同一个答案盘面,换一种留提示数的方式,就能做出很多道有唯一解的题。题目的数量很难数,这里不讨论。

先看小一号的数独

一上来就想9×9会让人无从下手,所以先看4×4的数独:用1到4,每一行、每一列、每一个2×2的宫里都不能有重复的数字。

4×4的完整盘面只有288种。整数数列百科 OEIS 的 A107739 里收录了这个数。288种的话,只要有耐心,用纸和笔也能全部写出来。

9×9约有6.67×10²¹种

到了9×9,情况完全不同。完整盘面的数量是

6,670,903,752,021,072,936,960 种

用中文的单位说,大约是66.7万亿亿种。这个数是2005年由贝特拉姆·费尔根豪尔(Bertram Felgenhauer)和英国谢菲尔德大学的弗雷泽·贾维斯(Frazer Jarvis)计算并发表的。英文维基百科的 Mathematics of Sudoku 条目里也有这个数。

他们并不是把每个盘面都做出来一个一个地数。思路的骨架是这样的。

首先,左上角的宫里9个数字的排列方式有 9×8×7×…×1 = 362,880 种。但不管是哪一种排列,后面的填法数量都一样。因为只要给数字换个名字,任何排列都能变成「1 2 3 / 4 5 6 / 7 8 9」。所以,只要把左上角固定成「1 2 3 / 4 5 6 / 7 8 9」,数出剩下的填法,最后乘以362,880就行了。

左上角固定时,填法有 18,383,222,420,692,992 种。两人把最上面三行(包含左上角宫的横向一带)的各种填法,按照剩余填法数量相同的归为一类,减少到44类,再用计算机数出每一类剩余的填法。这不是能用手检验的方法,但它是一套仔细搭建的分类计算,保证不漏数也不重复数。

这个数有多大

6.67×10²¹ 大到让人没有感觉。

假设每秒看一个完整盘面,不睡觉一直看下去,看完全部大约要211万亿年。宇宙的年龄据说约为138亿年,这相当于它的约1万5千倍。

什么是「本质上不同」的盘面

不过,这么多的盘面里,很多彼此都很相似。对一个完整盘面做下面这些操作,规则依然成立。

  • 给数字换名字。比如把盘面上所有的1改成5,所有的5改成1。9个数字的换名方式有362,880种。
  • 在同一带内交换行。把最上面三行的顺序调换,每个宫里的内容不变,规则不会被破坏。
  • 整带交换。把最上面三行这一整块和最下面三行这一整块对调。
  • 列也一样,可以在同一竖带内交换列,也可以整条竖带对调。
  • 沿对角线翻转。以左上到右下的对角线为轴,把行和列互换。

旋转和镜像都可以由这些操作组合出来。比如旋转90度,就是先沿对角线翻转,再把列的顺序倒过来。

把行列的交换和翻转组合起来,一个盘面最多能变出3,359,232个盘面。再加上数字换名,一共约有1万2190亿种操作。

把通过这些操作能互相变换的盘面看作「同一个」来数,得到的就是本质上不同的盘面数。看起来不一样,但只是换了数字的名字、调换了几行的盘面,作为谜题的骨架是相同的。

本质上不同的盘面约有55亿种

本质上不同的盘面数是

5,472,730,538 种

这是埃德·拉塞尔(Ed Russell)和弗雷泽·贾维斯在2005年到2006年间计算出来的。

简单地想,用 6.67×10²¹ 除以约1万2190亿,似乎就能得到答案。真的去除,会得到约54亿7245万,比正确的值略小。之所以有差别,是因为有少数盘面具有对称性:做了某种操作之后,会变回完全相同的盘面,所以它们不会扩展成1万2190亿个不同的盘面。拉塞尔和贾维斯用一个叫做伯恩赛德引理的数学定理修正了这一点,得出了准确的数。

约55亿种的话,每秒看一个,大约173年就能看完。和宇宙年龄的1万5千倍相比,已经接近人能够得着的范围了。上一篇介绍的「不存在16个提示数的数独」的证明,就是把这约55亿个盘面逐一检查完成的。如果还是 6.67×10²¹ 种,恐怕连计算机也查不完。

和拉丁方阵的区别

数独和“ナンプレ”有什么不同 里写过,填好的数独盘面是拉丁方阵的一种。拉丁方阵只要求行和列里没有重复的数字。数独再加上3×3宫的条件,等于是从拉丁方阵里挑出还满足这个条件的那些。即便如此,仍然剩下6.67×10²¹种。

1200道题和6.67×10²¹种盘面

Sudoku365 有四个难度,每个难度300题,共1200题。每天解一道,全部解完大约要3年零3个月。

可是和答案盘面的数量相比,1200小到无法比较。数独的题目会不会用完,暂时完全不必担心。

应用里还有全世界共用的每日一题“每日挑战”。想先学解题技巧的话,可以看 初学者最先要学的基本技巧;想知道难度差在哪里的话,可以看 数独的难度由什么决定。

应用免费,带广告,可以一次性购买“移除广告”来关闭广告。第一道题怎么开始,写在 Sudoku365 入门里。

在 App Store 下载 在 Google Play 下载

Sudoku365每日数独,也能两个人玩