数独的自动推理
By 苏剑林 | 2014-04-21 | 37308位读者 |写在前面:作为离散数学的实验作业,我选择了研究数独。经过测试发现,数独的自动推理还不算难,我把两种常规的推理思路转化为了计算机代码,并结合了随机性推导,得到了一个解题能力还不错的数独程序。事实上,本文的程序还可以进一步优化,以得到更高能力的数独程序(只需要整理一下代码,加上几个循环和判断即可),但是我实在太懒,没有动力继续弄下去了,就这样先和大家分享吧。最后,笔者认为本文的算法是更接近我们的思维的算法。
数独简介 #
历史
相传数独源起于拉丁方阵(Latin Square),1970年代在美国发展,改名为数字拼图(Number Place)、之后流传至日本并发扬光大,以数学智力游戏智力拼图游戏发表。在1984年一本游戏杂志《パズル通信ニコリ》正式把它命名为数独,意思是“在每一格只有一个数字”。后来一位前任香港高等法院的新西兰籍法官高乐德(Wayne Gould)在1997年3月到日本东京旅游时,无意中发现了。他首先在英国的《泰晤士报》上发表,不久其他报纸也发表,很快便风靡全英国,之后他用了6年时间编写了电脑程式,并将它放在网站上,使这个游戏很快在全世界流行。
台湾于2005年5月由“中国时报”首度引进, 且每日连载, 亦造成很大的回响。台湾数独发展协会(Taiwan Sudoku Association, 简称 TSA)亦为世界解谜联盟会员。香港是在2005年7月30日由AM730在创刊时引入数独。中国大陆是在2007年2月28日正式引入数独。北京晚报智力休闲数独俱乐部(数独联盟前身)在新闻大厦举行加入世界谜题联合会的颁证仪式,成为世界谜题联合会的39个成员之一。(引用自“中文维基百科”: http://zh.wikipedia.org/wiki/数独)
规则 #
如图1,通常的数独题目都会预先给出一些数字,留下一些空白让我们填满。要求是,每行、每列和每“3$\times$3方块”(图中用粗黑线划分)都必须出现1,2,3,4,5,6,7,8,9这九个阿拉伯数字,左图的答案如右图。
对于一道数独题目,预先给出的数字有多有少,数独难度也有高有低,而且,数独的难度和预先给出的数字数目没有必然联系,甚至对于一个给出的初始数独,正确的答案也可能不止一个。也许正是由于这种不确定性的魅力,才使得数独风靡全球。
推理思路 #
推理的方法无法就是两种,一种是根据前后左右已知的数字确定空白处的数字,实在无法进行确定性推理了,就使用“试探法”,即把一个空白可能的数字列出来,随机选择一个,然后继续进行确定性推理,看看会不会矛盾,如果导致矛盾,就换另外一个数字,重复上面程序。
确定性推导 #
确定性推导基于两种思路,其中第一步都是通过排除法,把所有空白处所有可能的数字列出来,然后分析这些数字列表。比较理想的情况是,某个空白处的可能数字只有一个,那么就相当于确定了这个数字了。比如某列只有2个空白,第一个空白可能的数字是2,9,第二个空白可能的数字是2,那么就确定了第二个空白的数字2。填写了数字2之后,重复这个程序,就确定了第一个空白。
另外一个情况是,每行、每列、每块的所有可能数字中,某个数字只出现了一次,那么就确定了那个数字。比如,某一行有四个空白,第一个空白可能的数字是1,2,第二个空白可能的数字是2,3,第三个空白可能的数字是1,3,4,第四个空白可能的数字是1,2,3,由于4只出现在第三个空白处,而它又必须出现,所以第三个空白处的数字就确定了是4。
随机性推导 #
随机性推导的思路就更加易懂了,在确定性推导实在无法推出更多数字的情况下,我们只能碰运气了。我们找那些只能两个数字可能的空白处,随机选一个填下去,同样来说,多了这个数字后,确定性推导就可以继续进行下去了,如果在进行的过程中发现矛盾,那么就排除这个数字,选择另外一个数字;如果没有矛盾,一般情况下都可以完成整个数独的推导。从某种意义上来说,这也是确定性的推导,只是由于其推导具有一定的随机性,因此冠以“随机性”以表区别。
经过测试,通过以上两个推理,可以完成大部分难度的数独的推算。某些难度比较高的,可以通过再重复上面的程序一次,以得到进一步的结果。(当然,单靠这两种思路,并不总是奏效的(参考下面的测试程序。),由于我们没有使用更进一步的推理或者深度更高的枚举,程序的能力确实不足以尽善尽美。)
计算机实现 #
编程思路 #
下面要做的工作就是把上面的思路翻译成程序代码,本文采用的代码是C++。
为了实现上述思路,我使用了一个9$\times$9的数组B(矩阵)储存已经完成推理的部分结果(用0表示未知的待推导数字),用9$\times$9$\times$9 的数组A (“立方阵”)储存“推理过程”,也就是每个空格可能的数字。A也可以看成每个元素是向量的矩阵,其每个元素的初始值为$(1,2,3,4,5,6,7,8,9)$,即对于任意$i,j$都有$A_{ijk}=k$。每确定一个数字$k$,把与之有关联的(对应的行、列、块)的$A_{ijk}$ 设为0。
程序由主程序和三个函数组成,三个函数分别是确定性推导程序、检测程序、随机性推导程序,分叙如下:
1.确定性推导程序 即把“确定性推导”的推理思路转化为计算机思路,主要用到嵌套循环和判断;
2.检测程序 这是为了配合随机性推导而写的,主要是检测每行、每列以及每块的已知数字中,是否存在重复的非0数字,这是数独正确的必要条件;
3.随机性推导程序 即把“随机性推导”的推理思路转化为计算机思路,主要用到嵌套循环和判断。
其中,代码和生成的程序放在本文件所在的目录的c++文件夹中(代码在Windows 8 + Visual Studio 2013下编译通过)。下面展示几个推导案例,数独由“数独博士”自动生成。
程序测试 #
入门级测试 #
笔者的程序的求解(入门级)
可见,入门级数独仅需确定性搜索就可以完成。这大概也是入门级的“入门”意义所在吧。
中级测试 #
以上是由数独博士生成的中级数独,但是很遗憾,本程序却解决不了这个数独,原因在于该数独初始数字太少,对于人工来说,可能是自由度较高显得比较简单,但是对于计算机推理来说,这种自由度往往造成了推理上的困难。当然,可以改进本文所用的判断解决这个数独(使用多重“确定+随机”搜索和判断),但是这将会导致程序代码长度激增,因此不再赘述。
高级测试 #
以上是由数独博士生成的高级数独,使用笔者的程序迭代三次就可以得出最终答案。要注意的是,由于迭代中并没有使用关联判断,因此换个例子就不一定迭代成功了。
骨灰级测试 #
“骨灰级”意味着“发烧”到了最高境界,意思是难度最高的数独级别。意外的是,测试一个由“数独博士”生成的骨灰级数独,却只需要一次确定性和随机性推导即可。由此可见,本文的算法推导思路跟数独博士的思路并不一致。个人认为本程序的算法更接近人工思维。
最后 #
源码和程序下载:数独推导_苏剑林.zip
转载到请包括本文地址:https://www.kexue.fm/archives/2527
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Apr. 21, 2014). 《数独的自动推理 》[Blog post]. Retrieved from https://www.kexue.fm/archives/2527
@online{kexuefm-2527,
title={数独的自动推理},
author={苏剑林},
year={2014},
month={Apr},
url={\url{https://www.kexue.fm/archives/2527}},
}
February 14th, 2019
With thanks! Loads of material.