“世界最难数独”解题探索—手工运用深度搜索和回溯算法解题实例

世 界最 难 数 独 解 法 探 讨

这就是被称为世界最难数独”。它是芬兰数学家因卡拉，花费三个月的时间设计出来的。据说也是世界迄今难度最大的数独游戏，难度系数为10.7（目前最难数独的系数是10），并且只有一个唯一答案。

有报道说：扬州市的一位69岁老汉花三天时间破解了此题，但是，他将第四行的5改成了8。在今天来看，这就是个笑话。因为有人用计算机软件破解了此题，并证明确实是只有唯一答案。

这道数独题让国内数独玩家大伤脑筋，至今未见报道有人用手工解出此题，即使是第一步的破题之法也未见报道。

数独的出题之法就是挖坑法，在54亿多的组合中选一个，然后挖掉一些数字，当然挖数也很有技巧。超难数独的出题人或许只知道答案，并不知道所有解题过程和步骤。据说最难的地方要求解题者能提前想到10个数字的填写才能破解。

这道题是来源于英国《每日邮报》2012年6月30日的一篇报道。他面世9年多来，未见有人披露过解题思路，就连破题第一招也没人透露过。或许，真正的数学家们是不屑于数独游戏的。

数独是一种益智游戏，他的益处是能锻炼和高逻辑思维能力和专注力。对于培养儿童的自律、提高专注力和形成逻辑思维习惯大有益处；成年人闲暇之余活动活动大脑也大有裨益；再者就是老年人用来防止老年痴呆症。

在电脑软件工程师开发出数独计算软件能瞬间得到结果后，使得人们对数独游戏的兴趣大大降低。数独游戏软件的出世，人们随时都可在手机上玩数独消遣时光。但是靠自己动手一步一步推导，享受推理过程的成就感还是让许多数独爱好者乐此不疲。所以还是有许多培训机构和数独大咖们在孜孜不倦的培训和研究数独的“高级技巧”。

我们不能过度痴迷数独“高级技巧”，执着的花费大量时间研究一数、一链、一模板（以及无穷尽变形）的推理，因为它们大都是孤立的研究某个数的推理过程，最后得出一个是与否的结论，无益于高难度数独的解题，反而会把自己陷入苦恼、愁眉不展，甚至丧失自信造成心理障碍。

数独的每一个数都是和其他的数有关联的，牵一发而动全身。孤立的用一个数去推理，什么：强-弱-强、弱-强-弱.......是能得到一个准确的是与否，可是在实战中，大多数情况下推不出一个确定的结果，忙了半天无果而终。

数独的推演应当要用系统思考的方法，而不是依靠孤立的推导一个数字的是与否真与假。

数独是有规律的数字游戏，规律有基本规律和特殊规律。

基本规律适用于每一道数独题的每个步骤，限于一数、一宫、一行、一列和一链的推演，非此即彼，非真及假。国外数独爱好者在解题过程中发现了一些规律，然后再一步一步的推导求证，然后就成为了现在的“高级技巧”。但是，这些高级技巧有很大的局限性，就是它的数字结构和排列都要要符合模板（高级技巧）的条件，否则，英雄无用武之地。而且，这些“高级技巧”所推演的数字和步骤有限。随着数独爱好者孜孜不倦的追求，发现规律越来越多，“高级技巧”扩展和变形将会越来越多。因为9宫数独约有6.67×10的21次方种组合，就是剔除重复（如数字交换、对称等）后，也有54亿多种。

我们应该从另一个角度来寻求破解数独的方法，能够使解题化繁为简，直击目标。

从集合论的角度来看，数独就是一个集合，虽有81个单元格，但只有九个元素（123456789）。他的子集分别是：行、列和小九宫，每个子集的元素也是9个（123456789），只是它们排列与组合有所不同。每个单元格只包含一个元素，这个元素在所处的行、列和宫都不重复。

数独题待填格的候选数也是一个集合，这个集合的元素≤9个。但是，候选数的个数却远远大于集合的元素，这是因为每个待填单元格的候选数总是≥2。如果我们把每个单元格的候选数作为一个子集的话，这个子集中只有一个元素是符合数独规则的元素，这也是数独题探求的结果。

既然我们把集合作为数独题的表现形式，那么，我们就要寻找到一个适合的算法来求出答案。

我们知道，很多问题在无法根据某种确定的计算法则，同时也不能找出适用的数学模型来求解时，可以用搜索与回溯的技术求解。那么，深度搜索（DFS）和回溯算法为我们提供了一个可用的工具。但是，这两种算法是计算机解题中常用的算法。专业的表述就是：搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。

人脑和手工能否运用深度搜索（DFS）和回溯算法破解数独呢？

标准的9宫数独约有54亿多种组合，据说最难的地方要求解题者能提前想到10个数字，也就是使用搜索与回溯的算法要搜索到第十层才可能找到一个（单元格）的答案。如果要穷举遍历，人脑和手工在短时间内很难完成。

如果我们能够利用化整为零的方法减少数据规模，根据数独的规则定义解题空间，在搜索过程中再利用剪枝函数避免无效搜索，那么，人脑和手工运用深度搜索和回溯算法破解数独还是有可能的。当然，深度优先搜索算法和回溯算法运用计算机软件来实现要方便得多。

第一、如果以九宫数独的小九宫、行和列作为研究对象，他们组合便只有

362，880种。再以小九宫、行和列的待填格作为研究对象的话，数据的规模将会更小。

第二、根据数独的规则，定义解题空间。每个单元格只有一个有效元素，且与所在的小九宫、行和列其它单元格的元素不重复这是数独的规则要。我们定义的有效解是：当一个单元格只有一个元素不包含在该单元格的所出现的子集中，那么，这个元素就是该单元格的解。

第三、利用剪枝函数避免无效搜索。如一个数组有两个元数（比如A、B），那么在另外一个单元格也应有一个一样的数组，不然一个单元格无法安放两个元素。我们在确定子集的数组时，要保证它与其它子集∪时，至少要有一组∪中不存在∩。确定子集元素时要保证子集中的元素在上一层集合中它们是连接最紧密（最多）的。

第四、确定集合研究的范围也很重要，它可以避免我们在解题过程陷入混乱和迷茫。数独不研究有0个元素的集合，因为数独的每个单元格必须且只有一个元素，不存在空单元格。也不研究只有一个元素的集合，因为一个单元格只有1个元素，他就是这个单元格的解，再去研究毫无意义。

当子集的元素是n(n≥2)个时，它应当同时在≥n个单元中出现。这是数独规则所要求的，如一个数组有两个元数（比如1、2），那么在另外一个单元个也应有一个一样的数组，不然一个单元格无法安放两个元素。

做出以上定义和限制的目的，是为了减少搜索层级，尽快找出答案。避免频繁回溯，节约时间。

对于高难度数独，直接用排除法和余数法是无法解题的，通常就要通过候

选数来解决。候选数：就是在待填空格中将所有可填的候选数填上，然后再删减候选数，精简题面。

我们来看这道号称世界上最难数独题怎样破解吧。先将候选数填好，再来审视题面。

我们精通很多高级技巧，按部就班的来擦亮眼睛，寻找高级技巧所说的题面，然后再推敲删减。见下图：

纵观题面，我们先将在行、列或宫只出现两次的数标出，并没有发现可以直接可以使用高级技巧来删减的候选数或直接确定的可填数字。可见，高难度数独并没有给我们一个直接使用所谓的高级技巧的机会。没想到刚入题就陷入了困境，百思不得其解。

用集合理论和深度搜索（DFS）和回溯算法破解这道号称“世界最难”的数独题呢？我们拭目以待！

先从提示最数多且看起来最简单的第九宫开始。九宫有5个待填空格，G7、H7、H9、I8和I9，待填数字是2、3、5、7、9。分别是：G7(359); H7(39)；H9(2379)；I8(257)；I9(2357)。见左图：

我们把九宫的待填数视作集合S{2、3、5、7、9}；它分别由子集A{2、7}用粉红色标注、子集B{3、5}用绿色标注、和子集C{3、9}用橘色标注。

我们所确定子集的数组时要保证它与其它子集∪时，至少要有一组∪中不存在∩。确定子集元素时要保证自己种的元素在这个大的集合中它们时连接最紧密（最多）的。

九宫有唯一双值格H7{3、9}，在G7(359)和H9(2379)也有39的集合，我们把39作为一个集合，另外，我们发现27是一个与生俱来的集合，他们只是同出现，且分别出现在H9(2379)、I8(257)、I9(2357)中。所有元素中还有5没有结伴，候选数中有3个5，显然它应该有一个集合，我们发现在I9(2357)中，有35的组合，是否还有其它单元格也有35的组合呢，在G7(359)也有35的组合，符合数独研究的集合范畴。

为什么不把5和2进行组合呢？我们看到25组合分别出现在I8(257)；I9(2357)，我们可以把257看作一个∪，当它们同时出现两次，且除此之外没有25独立的集合，其实它们应该是一个257的集合，不把它们看作一个三元素集合就会造成混乱，因为257可以说是27、25的∪，也可以说是57、25的∪。如果看作时257的集合，它不符合“当子集的元素是n(n≥2)个时，它应当同时在≥n个单元中出现“。可见它（257）的存在不合理。

为了便于直观的从集合的理论来研究，用示意图来说明集合，见下图：子集之间的关系：AUB{2、3、5、7},对应单元格I9。AUC{2、3、7、9}，对应单元格H9。BUC{3、5、9}，对应单元格G7，B∩C{3}。用小黑圈代表集合T{2、3、5、7、9}，可见S包含T，而且它们的元素完全一样。

数独的每一个单元格只能包含一个元素，且在行、列和宫中不能重复。一个子集包含两个元素，它们只能出现在两个单元格中，超过两个的都不合理，应当删除。在集合T中，子集A和B都已出现在三个单元格中（A：H9、I9，B：I9、G7）。超过两次的都是不合理的存在，需要删除。

那么存在于H7中B∩C{3}应当删除，I8中A{2、7}应删掉。从集合示意图也可以看出，S与T之间有两个独立的不属于任何一个子集的元素5和9，H7中的候选数9和I8中的候选数5数，它们就是H7和I8中唯一存在的元素。见上图1。

按规则进行整理后的题面见图2：

继续进行整理后见图3：

现在看第七宫：待填数集合S{2、3、4、6、7}。唯一双值格G2（2、4），H1和H2都有24数组的集合，把它作为子集A{2、4}，用橘色标注。再来看H2（2、3、4、6），除了有数组24，还有一对数组36，且数组36在H1I1都有出现，把它作为子集B{3、6}，用绿色标注。继续看，I1（2、3、6、7），除了数组36外还有数组27，数组27也同时出现在H1（2、3、4、6、7）和I3（2、6、7）,把它作为子集C{2、7}，用粉红色标注。见下图：

第七宫集合分布情况，G2：A{2、4}。H1:AUBUC{2、3、4、6、7}，A∩C{2}。H2：AUB{2、3、4、6}。I1：BUC{2、3、6、7}。I3：C{2、7}+6。还是用示意图表示直观，见下图：

在第七宫中，集合A、B、C都出现了三次。集合A: G2、H1、H2。集合B：H1、H2、I1。集合C：H1、I1、I3。有两个元素的集合同时出现在三个单元格中，其中一个必为假。哪个是可以删除呢，从图中可以看出，I3（C{2、7}+6）中C可以删除，I3取值6。见下图：

我们来分析一下是否可以将I3（267）作为一个集合。设集合N{2、6、7}，则H1、I1、I2都有2、6、7数组，符合我们的要求。接下来是选择{2、4}还是{3、4}的集合。选择24组合，元素3(待填数3)就没有被组合进去，显然不行。选择34组合，G2（2、4）和H2中候选数26就非常尴尬。可见，将H3（2、6、7）

作为一个集合是行不通的。进行整理后见下图：

这时，第三列一个典型的集合出现了，见下图。第三列有4个待填格，待填数为2、4、5、9。A3：（2、4、5、9）。C3：（4、5）。D3：（2、4、9）。E3：（2、9）。很容易看出集合S{2、4、5、9}：A{4、5}，B{2、

9}，他们的组合是：结合A所在单元格C3，集合B所在单元

格E3，AUB所在单元格A3。见示意图：

集合A分别出现在A3、C3,集合B分别出现在A3、E3，那么D3（B{2、9}+4）中的B{2、9}就要删去，D3取值4。

现在来研究第五宫。五宫也是有5个待填数。集合S{2、3、6、8、9}。

如何确定第五宫的子集？D4、E4都是由2389组成，作为四个元素的集合显然不行，因为它们只出现两次。所以只能作为两个子集的并集。怎样给这两个子集分配元素又是一个问题，我们发现数组28是与生俱来的集合，因为它们同时出现在第五宫所有待填格，所以有A{2、8}用绿色标注、B{3、9}用粉红色标注。这才解决了两个单元格，还有3个单元格呢？

单元格D5（2、3、6、8）、F5（2、6、8）、F6（2、6、8、9）都有数组268，那么268就是子集C{2、6、8}的元素用橘色标注。还是来看用示意图：

它们的组合是，单元格D4、E4：AUB{2、8、3、9}。单元格F5： C{2、6、8}。单元格D5：C{2、6、8}+3。单元格F6：C{2、6、8}+9。

在这种情况下如何取数，D5 和F6的C{2、6、8}是否可以删除呢？

如果我们不把2、6、8作为一个集合，而是看成一个U，是68和26或28和68的U，那么268就是AUC，三个AUC就可以删掉一个。问题又来了，D5和F6哪个是该买的呢？从理论上讲删除那个都没错，既然删除哪个都可以，一起删掉也应该不会出问题。那么就果断删除D5和F6的C{2、6、8}，D5取值3、F6取值9。见图4：

我们对第三列和第五宫已确认取数的单元格的相关行、列、宫进行整理，再用排除法和余数法就能顺利解题：

题完成见答案：

从以上实列来看，用集合的理论和人工运用深度搜索（DFS）和回溯算法破解数独时可行的。用集合的理论破解数独，是根据数独元素排列和组合的内在规律解题。它是一个系统的破解法，不是依据一数一格，用是与非、真与假，孤立的来推论单元格的元素。

集合理论破解度也不是万能的，如果遇到两个待填数出现”AB:AB”组合，三个待填数出现”AB：BC：AC、ABC:ABC:ABC“等的组合，四个待填数出现”AB:AC:AD:DB”等的组合，每个子集都只出现≤n(元素个数)次的组合时，只得进行回溯，回到原点从另一条路线继续搜索。不过，从实际解题来看，当我们得到一定数量的解时，这个数独便成了基础题，用排除法和余数法就能顺利解题，这也是手工解题的优势吧。