小伙伴们大家好，今天吴佳乐讲的文章是数独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），那么在另外一个单元个也应有一个一样的数组，不然一个单元格无法安放两个元素。
做出以上定义和限制的目的，是为了减少搜索层级，尽快找出答案。避免频繁回溯，节约时间。
对于高难度数独，直接用排除法和余数法是无法解题的，通常就要通过候
选数来解决。候选数：就是在待填空格中将所有可填的候选数填上，然后再删减候选数，精简题面。
我们来看这道号称世界上最难数独题怎样破解吧。先将候选数填好，再来审视题面。
我们精通很多高级技巧，按部就班的来擦亮眼睛，寻找高级技巧所说的题面，然后再推敲删减。见下图：
纵观题面，我们先将在行、列或宫只出现两次的数标出，并没有发现可以直接可以使用高级技巧来删减的候选数或直接确定的可填数字。可见，高难度数独并没有给我们一个直接使用所谓的高级技巧的机会。没想到刚入题就陷入了困境，百思不得其解。
我们把九宫的待填数视作集合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，而且它们的元素完全一样。
按规则进行整理后的题面见图2：
作为一个集合是行不通的。进行整理后见下图：
格E3，AUB所在单元格A3。见示意图：
现在来研究第五宫。五宫也是有5个待填数。集合S{2、3、6、8、9}。
单元格D5（2、3、6、8）、F5（2、6、8）、F6（2、6、8、9）都有数组268，那么268就是子集C{2、6、8}的元素用橘色标注。还是来看用示意图：
在这种情况下如何取数，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：
集合理论破解度也不是万能的，如果遇到两个待填数出现”AB:AB”组合，三个待填数出现”AB：BC：AC、ABC:ABC:ABC“等的组合，四个待填数出现”AB:AC:AD:DB”等的组合，每个子集都只出现≤n(元素个数)次的组合时，只得进行回溯，回到原点从另一条路线继续搜索。不过，从实际解题来看，当我们得到一定数量的解时，这个数独便成了基础题，用排除法和余数法就能顺利解题，这也是手工解题的优势吧。
今天这篇文章就写到这里了，希望能帮到大家，看完了数独10级难度题「必看：世界第一难题解法探讨」，收获很多，欢迎帮忙分享一下。我在这边先谢谢各位了哈！
本文发布者：万事通，不代表寂寞网立场，转载请注明出处：https://www.jimowang.com/p/6984.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 jimowangmail@126.com 举报，一经查实，本站将立刻删除。
