700万小时搞定最小数独问题 | 科学人 | 果壳网 科技有意思
700万小时搞定最小数独问题
本文作者:sqybi
刚刚迈入 2012 年，数学界就有一个不大不小的收获。三位爱尔兰数学家发表了一篇论文，证明了数独至少需要 17 个初始数字才有唯一解。这个问题很难吗？其实一点也不，计算机才花了 700 万小时的 CPU 时间（CPU时间指CPU上执行指定代码的时钟周期数乘以每个时钟周期的时间长度）就搞定了这道数独题。这 700 万个小时它了做了什么？是三位数学家的方法很笨才导致算了这么久吗？实际上，这个时间已经不算长了。看看死理性派的详细介绍你就知道了。
数独游戏和长久以来的世界难题
18 世纪末，瑞士数学家欧拉发明了一种叫做“拉丁方阵（Latin Square）”的游戏。虽然最初这个游戏并没有风靡起来，但随着时间的推移，在 20 世纪 70 年代的美国，这个游戏以“数字拼图（Number Place）”的名字迅速流行起来，之后逐渐流传到日本、英国，到现在已经成为了红遍全球的智力游戏。
数独游戏基本规则是这样的：在一个九宫格中给出一些初始数字。玩家需要在九宫格内填入缺失的数字（1 - 9），保证：
每一行的 9 个数字各不相同
每一列的 9 个数字各不相同
每一个用粗线标识出的 3 × 3 的小正方形内 9 个数字也各不相同
虽然规则非常简单，但其中包含的信息却毫不简单。数学家 Bertram Felgenhauer 在 2005 年证明，数独的解共有 9! × 722 × 27 × 27,704,267,971 种不同的可能组合，上面这个乘式的最后一个数还是一个质数。
一个经典的数独。图像来源：wikipedia
而如此多变的变化，无疑也给数学家们出了不少难题。其中一个被讨论了很久的问题是， 至少给定多少个初始数字，数独才会有唯一解？ 此前已经有人给出了一些包含 17 个初始数字的数独，并利用计算机证明了其解是唯一的（对于某个给定了 17 个初始数字的数独，计算机枚举了所有可能的排列情况，只找到一个解），从而证明了 17 个初始数字的数独是可以存在唯一解的。但是长久以来都没有人知道， 16 个初始数字的数独是否存在唯一解。终于，在 2012 的元旦，都柏林大学（University College Dublin）的数学家们给出了 答案：16 个初始数字的数独不存在唯一解。
有没有解试出来
消息一出，媒体争相报道，报道中不乏复杂的算法、超级计算机等“虽然不知道在说什么，但看起来很厉害”的词汇。事实上，研究人员用来证明这个问题的方法用一个字就可以总结，那就是——试。
解决这个问题几位数学家最初的想法非常可爱： 只要把每一种有 16 个初始数字的数独都尝试着填一遍，自然就知道答案了。
但很可惜，因为数独的组合实在是太多了，所以即使是现在最快的计算机，也不可能在我们的有生之年穷尽所有的组合。因此，必须用一些数学的方法来减少尝试的次数，这个想法才能够实现。
他们发现，数独虽然有很多种可能的组合，但是其中一些其实是等价的。如下图，可以看到交换第一列和第二列对整个数独并没有影响。实际上任意一个合法数独的解交换两列后，都可以构成一个新的合法数独，而这个新数独和原数独就可以看做是等价的。
两种等价的数独组合
三位数学家总结了数独的 4 种等价变换：
⒈ 列与列的重新排列（例如上图）
⒉ 行与行的重新排列
⒊ 数字 1 到 9 的重新排列。如把原先是 1 的位置都填上 2，然后把原先是 2 的位置都填上……直到把原先是 9 的位置都填上 1 等
⒋ 网格的变换。如整个数独顺时针旋转90度，整个数独做镜像对称等
在 2006 年已经有数学家证明，排除以上几种重复后，数独总共有 5,475,730,538 个等价类。因为每个等价类里的任意一种情况都可以通过这个等价类中的其它情况经由以上 4 种变换得到，所以对每个等价类来说，我们只要考虑一种情况即可。如此一来，有非常多的组合都被我们直接排除了，计算量大大减小。
让枚举量少一点，再少一点
虽然等价类的数量已经降低到了可以接受的范围，但问题还远没有结束。因为在选择了某个等价类中的一种情形之后，我们还需要验证这个情形的 81 个数字中是否可以选出 16 个，使得以这 16 个数为初始数字的数独有唯一解。
如果检查所有的可能情况，对于每一个等价类，我们要检查的次数就是：
这显然很不幸：好不容易通过排除等价变换的方法把计算量减下去，怎么能在这里再加回来呢！所以这又需要数学家再做一些工作，把 3.4 × 10 16 这个数减小，让枚举量少一点，再少一点。
因此，几位数学家利用了 “不可避免集”的概念：如下图所示，如果表示颜色的 4 个数字中任何一个都没有在初始数字中给出，那么这个数独一定没有唯一解——因为在没有给出的情况下这 4 个数字都是由玩家填进去的，玩家既可以以左图的方式填入这 4 个数字，也可以以右图的方式填入，而得到的两个解都是合法的。具有这种属性的数个方格就叫做不可避免集，一旦出现了不可避免集，我们就必须要在其中至少选出一个格子用来填写初始数字。
不可避免集
不可避免集大大化简计算量
在论文中，数学家们采用了 Ed Russell 总结的一套不可避免集的模板，总共记录了 525 种不同的不可避免集。因为一开始所说的 4 种等价变换对不可避免集也适用，所以他们对不可避免集进行了一些标准化的处理，以保证这 525 种不可避免集互相之间不能通过 4 种等价变换得到。
此时，枚举算法就被改造成这样：数学家给所有的不可避免集都设定一个状态，分为“被击中”或“未被击中”两种。初始时九宫格 81 个方格内都没有填入数字，所有不可避免集的初始状态均为“未被击中”。之后开始每次选择一个最小的未被击中的不可避免集，枚举其中的每个格子。即每次选择不可避免集中的一个格子填充初始数字，直至试完不可避免集中的所有空格。同时将这个不可避免集标记为“被击中”状态，每次枚举都有 4 种可能。
● 如果这个格子也出现在了其它不可避免集中，那么将这些被涉及到的不可避免集也标记为“被击中”状态；
● 如果枚举了 16 个格子后还有不可避免集未被击中，说明以这 16 个格子为初始状态的数独一定没有唯一解；
● 恰好枚举了 16 个格子后所有的不可避免集全部被击中；
● 如果枚举了不到 16 个格子后所有不可避免集已经全部被击中，则从剩下的所有格子中再枚举几个格子使初始填充了数字的格子达到 16 个。
完成上面这个工作后，就要用解数独的程序来验证所有枚举的情况是否有唯一解。为了进一步加快枚举速度，数学家们还加入了一些可行性剪枝和最优化剪枝，如提前判断“当前情况下已经不可能击中所有不可避免集”并终止枚举等。
在这一系列优化之后，算法的复杂度终于降低到了可以接受的范围内。但即使这样，整个计算过程还是耗费了 700 万小时的 CPU 时间。幸而这个算法最终给出了一个确定的结果：所有仅包含 16 个初始数字的数独，都不存在唯一解！
暴力与美学的结合
当然，上述结果的正确性还有待其他科学家进一步验证，因为算法耗时极高，所以验证过程也需要花费比较长的时间。但无论这次 3 位数学家给出的结论正确与否，随着验算结果的公布，这个问题终将得到一个解答。
粗略看来，这个算法的实现是非常暴力和机械化的：尝试每一种可能的情况。但是在实现的过程中，数学家们又在借助于数学的力量，不断地试图减少枚举的数量，最终将不可能的事情化为了现实。怪不得西澳大利亚大学的数学家 Gordon Royle 这样评价道：“这个挑战性的问题让人们把计算的能力和数学的技巧发挥到了极限，这就像是在攀登最高耸的山峰。”
现在关于数独的 puzzle 越来越难越来越精彩了。你做过的最难的数独是什么？在这里抛一块砖：
参考资料： There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem
你可能感兴趣
看不懂。？
这个答案给我。
你们这些人类都在用计算机做神马啊！
求17个数字的数独。。
700万小时我还是利用这个时间去冬眠吧
经济学爱好者
为什么最后一题只有16个数？
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：为什么最后一题只有16个数？因为有附加条件。。。
求非穷举证明的方法~
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：求非穷举证明的方法~如果有的话就不用这么累了！
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：700万小时我还是利用这个时间去冬眠吧700万小时是CPU时间。。。有好多好多的CPU们一起努力工作呢☆
什么叫“700 万小时的 CPU 时间”700万小时是29.17万天是0.08万年是800年啊
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：什么叫“700 万小时的 CPU 时间”700万小时是29.17万天是0.08万年是800年啊CPU时间指CPU上执行指定代码的时钟周期数乘以每个时钟周期的时间长度。。。如果有10000个CPU同时运行代码，那么700万小时的CPU时间只要一个月就可以跑完了。
的回应：这个答案给我。
的回应：求17个数字的数独。。你去找
的回应：为什么最后一题只有16个数？你来都来了，就不能推荐一下么……
声明不是我解出来的
经济学爱好者
的回应：因为有附加条件。。。也就是说，看起来是限制条件，其实反而提供了额外信息，降低了复杂度。
“让枚举量少一点，再少一点”里的图中右边那货也是合法的？
的回应：声明不是我解出来的用PS稍微写好看一点……慢了五分钟解出来啊
的回应：“让枚举量少一点，再少一点”里的图中右边那货也是合法的？THX 哎呀 谢谢谢谢 马上来改
楼主最后一题
的回应：声明不是我解出来的原来我慢了好多啊引用
的回应：用PS稍微写好看一点……慢了五分钟解出来啊
理论物理学硕士在读，维基百科小组管理员
LZ可以参考一下信息学奥赛里的相关资料，这里积累了很多关于数独的问题
的回应：LZ可以参考一下信息学奥赛里的相关资料，这里积累了很多关于数独的问题DLX =v=
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：DLX =v=引用
的回应：LZ可以参考一下信息学奥赛里的相关资料，这里积累了很多关于数独的问题想当初那篇论文还是我翻译的。。。哈哈哈口胡了，其实是吴豪同学完成了最主要的工作，我只是帮忙翻译一小部分然后校对一下啥的。。。顺便@ 下楼上的童鞋
如果有兴趣的话可以看一下这篇Knuth的论文 这个算法用在解数独上效果还是不错的
的回应：想当初那篇论文还是我翻译的。。。哈哈哈口胡了，其实是吴豪同学完成了最主要的工作，我只是帮忙翻译一小部分然后校对一下啥的。。。顺便@ 下楼上的童鞋
如果有兴趣的话可以看一下这篇Knuth的论文 这个算法用在解数独上效果还是不错的 ForbiddenYou don't have permission to access /works/dlxcn/ on this server.Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.
配图让数独控伤不起啊，有木有....
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：ForbiddenYou don't have permission to access /works/dlxcn/ on this server.Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.Ctrl+F5刷新下呢。。。我貌似设置了不能外链。。。囧
理论物理学硕士在读，维基百科小组管理员
的回应：想当初那篇论文还是我翻译的。。。哈哈哈口胡了，其实是吴豪同学完成了最主要的工作，我只是帮忙翻译一小部分然后校对一下啥的。。。顺便@ 下楼上的童鞋
如果有兴趣的话可以看一下这篇Knuth的论文 这个算法用在解数独上效果还是不错的 2个月前刚刚参加完信息学竞赛，现在已经淡出了……顺便看到一眼……想起来了，等将来有机会我会看的，嗯
的回应：你们这些人类都在用计算机做神马啊！难道你不是人类吗？
显示所有评论
(C)2016果壳网&&&&京ICP证100430号&&&&京网文[-239号&&&&新出发京零字东150005号Javascript 检测已停用
您目前已停用JavaScript。几个功能可能无法运作。请重新启用JavaScript来访问完整的功能。
标准数独技巧导读帖
主题发表者
这个主题已锁定
这个主题有19篇回复
以下列出本版已有涉及的解题技巧，会根据本版讨论情况及时更新，方便大家查询。请点击相关技巧名进入相应帖子。本帖为导读帖，以下所给连接帖只是提到了此结构，要更进一步了解此技巧请联系前后文及其他相关主题或帖文阅读。入门技巧：进阶技巧：高级技巧：____________________________________________________________________________________________________________________________________________________________________________________________________________________________________每个技巧介绍的帖子中或多或少会有些例题，形如每一行都是一道题目的81字串，把这个字串复制到黑白界面彩色界面（若上面两个链接你会看到格子偏移，请用最新版本黑白界面）即可在线游戏。
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
唯一数 Last Value适用情况：当某行、某列或某宫中已经出现八个不同数字时，最后一格即剩下还未出现过的第九个数。
图中这一行已经出现数字1、2、3、4、5、6、7、8，所以余下的星号格为9。实际应用：
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
宫摒除 Hidden Single in Box适用情况：观察某一个数字A，根据数独规则，在同行、列、宫内无重复数字，若一格是A，则其所在行、列、宫都不会再有A，若以此得出某一宫内数字A仅剩一个可能位置，则可以判断这格就是A。
图中对于第一宫，由于四个A的影响，第一宫只有一个地方可能填A，即星号处。实际应用：
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
行列摒除 Hidden Single in Row/Column适用情况：观察某一个数字A，根据数独规则，在同行、列、宫内无重复数字，若一格是A，则其所在行、列、宫都不会再有A，若以此得出某一行或列内数字A仅剩一个可能位置，则可以判断这格就是A。
图中对于第一行，由于四格受A的影响，第一行只有一个地方可能填A，即星号处。实际应用：
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
唯一余数 Naked Single适用情况：观察某一格，根据数独规则，一格与其所在的行列宫没有重复数字，点算这格所在行列宫已经出现过的数字，若已经出现8个不同的数字，则这格就是第9个没有出现过的数。
对于星号格，其所在行（第一行）已经出现2346，所在列（第五列）已经出现15，所在宫（第二宫）已经出现2678，即均出现了，故星号格为9。实际应用：
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
宫摒除区块 Pointing适用情况：在进行时，发现某数在某宫可能位置不止一个，但是可能位置处在同行或同列，则可以排除相应行或列中除他们外其他格的该数。
数字5对第二宫摒除发现第二宫5的可能位置是2个星号格，虽然目前不能确定是哪一格，但可以确定的是第三行除了星号格外其他格（用短横线标示）一定不是5。如下图所示：
实际应用：
观察数字6，对第七宫进行摒除，得到第七宫的6在星号两格（同在第七行），故第七行除星号格外不能再有6。
继而可以得到第八宫的6只能在r8c6。
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
行列摒除区块 Claiming适用情况：在进行时，发现某数在某行或某列可能位置不止一个，但是可能位置处在同宫，则可以排除相应宫中除他们外其他格的该数。
A对第一行摒除发现第一行A的可能位置是2个星号格，虽然目前不能确定是哪一格，但可以确定的是第二宫除了星号格外其他格（用短横线标示）一定不是A。如下图所示：
实际应用：
观察数字4，对第四行进行摒除，得到第四行的4在星号两格（同在第六宫），故第六宫除星号格外不能再有4。如下图所示：
数字4对第九列摒除，第九列的4只能在r4c9。
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
摒除数对 Hidden Pair适用情况：与、相同，只是同时观察2个数，且这两个数恰好被锁定在一行、一列、一宫的两个相同位置。
图中无论是字母A还是字母B在第一宫可能的位置都是星号格，故这两格不能再有除A、B外的其他数字。实际应用：为了阐述摒除数对，下面这个例子同时涉及到宫摒除数对（第一步）和行列摒除数对（第二步），如果希望找更直接的例子可以看[]。
数字2和3同时对第六宫摒除，得到第六宫的2和3只能在星号处。故星号两格除了2和3不再有其他可能的数。
数字1和4同时对第五行摒除，其中r5c7，我们之前已经得到它可能的候选数只有2或3，自然不能有1和4，第五行的1和4只能在星号处。故星号两格除了1和4不能会再有其他可能数字。
此时数字7对第五行摒除，第五行的7只能在星号处。
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
唯余数对 Naked Pair适用情况：与观察方法相同，只是同时观察两格，且这两格所剩可能填写的数字均为2个且组合相同。
图中星号所示两格可能的数字均只剩下8和9，由于他们同在第一宫，称其为89数对，继而可以删除它们同在的第一宫内其他格的候选数8和9。实际应用：为了阐述唯余数对，下面这个例子用到了3次唯余数对和1次摒除数对，方便大家对两者进行对比。
分别来看黑色星号的两格和白色星号的两格，通过点算他们所在行列宫已经出现过的数字，可以发现黑色星号两格剩余可能数字均为59，计为59数对；白色星号两格剩余可能数字均为57，计为57数对。
点算黑色星号可能的数字，我们发现在其行列宫已经出现过2,3,4,6,7，而第一步得到的59数对（蓝色所示）因为同在第三行，故第三行其他格不能再有5或9，黑色星号格可能数字只剩下1和8；同样的，看白色星号，其所在行列宫已经出现过的数字有2,3,4,5,6,9，第一步得到的57数对（紫色所示）同在第七行，故第七行的其他格内不能再有5或7，白色星号格可能数字只剩1和8。由于黑色和白色星号格同在第六列，且可能候选均为1和8，则称其为18数对，第六列除他们俩外其他格都不能是1或8。
数字1和3对第五行摒除，得到第五行的1和3只能在星号两格（摒除数对）。
数字4对第五行摒除，得到r5c8=4。
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
三链数 Triplet适用情况：与和观察方法相同，只是拓展到3个数或3格。这三格需属于同行或同列或同宫。实际应用：下面这个例子同时用到了摒除三链数(Hidden Triplet)和唯余三链数(Naked Triplet)，并会把前面的区块和唯余复习一下。
点算星号3格，自左往右，可能的数字依次为249,249,29，且它们同时处于第五行，则第五行的其他格不能再有2、5、9。
数字2,7,8对第四宫摒除，得到第四宫的2,7,8只能在星号3格。
数字4对第四宫摒除，得到第四宫的4只能在星号格。
r2c1唯余解9。
独数之道QQ群：欢迎订阅本站RSS以及各个你喜欢的主题！
0 位会员, 0 位访客, 0 位匿名会员
回复引用的文章&&&&& &&&
不建议在共用电脑上启用此选项。
不要将我加入到在线用户列表数独技巧论文1200字_百度知道数独解题方法大全
作者：扬子活力论坛 泥瓦匠      整理：隱讀書生
数独这个数字解谜游戏，完全不必要用到算术！会用到的只是推理与逻辑。解题方法分两大类：直观法和候选数法。
 直观法就是不需要任何辅助工具，从接到数独谜题的那一刻起就可以立即开始解题。绝不猜测。数独直观法解题技巧主要有：唯一解法、基础摒除法、区块摒除法、唯余解法、矩形摒除法、单元摒除法,余数测试法。
候选数法就是解数独题目需先建立候选数列表，根据各种条件，逐步安全的清除每个宫格候选数的不可能取值的候选数，从而达到解题的目的。
使用候选数法一般能解比较复杂的数独题目，但是候选数法的使用没用直观法那么直接，需要先建立一个候选数列表的准备过程。所以实际使用时可以先利用直观法进行解题，到无法用直观法解题时再使用候选数方法解题。
候选数法解题的过程就是逐渐排除不合适的候选数的过程，所以在进行候选数删除的时候一定要小心，确定安全的删除不合适的候选数，否则，很多时候只有重新做题了。有了计算机软件的帮助，使得候选数表的维护变得轻松起来。
数独候选数法解题技巧主要有：唯一候选数法、隐性唯一候选数法、区块删减法、数对删减法、隐性数对删减法、三链数删减法、隐性三链数删减法、矩形顶点删减法、三链列删减法、关键数删减法、关连数删减法。
一、直观法：
1、唯一解法：
        当某行已填数字的宫格达到8个，那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为行唯一解。
        当某列已填数字的宫格达到8个，那么该列剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为列唯一解。
        当某九宫格已填数字的宫格达到8个，那么该九宫格剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为九宫格唯一解。
  下面是例题：
A行已经添入8个数字，A行只有数字3没有出现过，所以A9=3，这是行唯一解。
第1列已经添入8个数字，第1列只有数字5没有出现过，所以E1=5，这是列唯一解。
在A8所在九宫格区域已经添入8个数字，只有数字9没有出现过，所以A8=9，这是九宫格唯一解。
2、基础摒除法
     基础摒除法就是利用1 ～ 9 的数字在每一行、每一列、每一个九宫格都只能出现一次的规则进行解题的方法。基础摒除法可以分为行摒除、列摒除、九宫格摒除。
实际寻找解的过程为：
寻找九宫格摒除解：找到了某数在某一个九宫格可填入的位置只余一个的情形；意即找到了 该数在该九宫格中的填入位置。
寻找列摒除解：找到了某数在某列可填入的位置只余一个的情形；意即找到了该数在该列中的填入位置。
寻找行摒除解：找到了某数在某行可填入的位置只余一个的情形；意即找到了该数在该行中的填入位置。
    利用基础摒除法解题的过程就是依次从数字1 ～ 9 在行、列、九宫格寻找能放入该数唯一的一个位置。需要综合用到行摒除、列摒除、九宫格摒除的方法。
    看能用基础摒除法确定Ｂ２、Ｃ８、Ｅ７、Ｆ６、Ｉ５的数字吗？
题目如下：
A4=9，则Ａ行其它格排除９；G1=9，第1列排除数字９；D3=9，第3列排除数字９。
由基础摒除法，第A1所在的九宫格内９只有一个唯一的位置，即确定B2=9。
A4=9，则4列其它格排除９；G1=9，第G行排除数字９；H9=9，第H行排除数字９。
由基础摒除法，第G4所在的九宫格内９只有一个唯一的位置，即确定I5=9。
A4=9，则4列其它格排除９；D3=9，第D行排除数字９；I5=9，第5列排除数字９。
由基础摒除法，第D4所在的九宫格内９只有一个唯一的位置，即确定F6=9。
A4=9，则A行其它格排除９；B2=9，第B行排除数字９；H9=9，第9列排除数字９。
由基础摒除法，第A7所在的九宫格内９只有一个唯一的位置，即确定C8=9。
C8=9，则8列其它格排除９；D3=9，第D行排除数字９；F6=9，第F行排除数字９；H9=9，第9列排除数字９。
由基础摒除法，第D7所在的九宫格内９只有一个唯一的位置，即确定E7=9。
3、区块摒除法
    区块摒除法是基础摒除法的提升方法，是直观法中使用频率最高的方法之一。
        所谓区块，就是将行分成3个三个相连的小方块构成，列也是分成3个三个相连的小方块构成。九宫格同样被看成由3个三个相连的小方块构成，如下面示意图： 
          
区块摒除法的核心思想如下面解释(以行为例)，对于在列也是相同的道理
假如(G1~G3)黄色区域区块其中之一是数字9。
则，(H4~H6)蓝色区域可能含有数字9。
否则(I4~I6)绿色区域含有数字9。
假定我们已确定(G1~G3)黄色区域区块其中之一是数字9。
(H4~H6)蓝色区域含有数字9。
则：在(I7~I9)绿色区域一定含有数字9。如果再通过其它方法确定(I7~I9)绿色区域中某两个宫格不能为数字9，则就能确定数字9在(I7~I9)区块的具体位置。
下面举一些例子
能使用区块摒除法确定F6的数字吗? 
D2=2，则E1~E3蓝色区块，或F1~F2绿色区块必包含数字2。
又有B1=2，利用列摒除法，E1、F1不能为数字1，有F2，F3已填有数字，所以，E2~E3蓝色区块必有数字2
由上面得出黄色区块,蓝色区块包含数字2,这是典型的区块摒除法,得到绿色区块必包含数字2
又G4=2,F5已添入数字,所以F6=2
4、唯余解法
    唯余解法就是某宫格可以添入的数已经排除了8个，那么这个宫格的数字就只能添入那个没有出现的数字。
唯余解法道理非常简单，但在实际使用是比较困难，要注意识别。A5=?
其实这就是唯余解法的原理，很简单吧。但是实际使用时就不会容易发现了。
能使用唯余解法确定B7的值吗?
呵呵，等于8。
能确定E9、A9、B9、C9的值吗?
由区块摒除法可以得出E9=9。在区块摒除法没有举这个例子，这里补充。
由唯余解法，C9=2。
同样，可得出B9=4，A9=8。
5、矩形摒除法
 矩形摒除法是比较高级的排除方法，虽然矩形摒除法的原理非常简单，在实际使用时比较难于观察出来。
矩形摒除法的原理如下：
如上图，如果在第3列，我们确定数字9只能在B3或H3出现。在第7列，数字9只能在B7或H7出现。则B3，H3，B7，H7构成矩形，符合矩形摒除法的条件。
由上，可以得出数字&9&仅可能出现在 (B3，H7)上，或者出现在 (B7，H3)上
无论出现上面的那一种情况，我们都可以推断出B行，H行的红色区域都不能再为数字 9了。
下面举一个使用矩形摒除法的例子
       
由C7=3，我们可以判断在第3列，数字3只能出现在A3和H3。
又第6列，数字3只能出现在A6和H6
由A3，H3，A6，H6形成矩形符合矩形摒除法的条件
由矩形摒除法得到H8不可能是3，又根据C7=3，所以G9=3
6、单元摒除法
单元摒除法是比较基本的排除方法,下面举例解释
能确定A8的数字吗?
由D5=7，得出D8不等于7
H9=7，得出G8、H8、I8均不等于7
7、余数测试法
所谓余数测试法就是在某行或列，九宫格所填数字比较多，剩余2个或3个时，在剩余宫格添入值进行测试的解题方法。
我们看B行，B3可能添入的数为5或者6，我们从5开始测试。
我们在B3添入5进行测试，得到左图，没有得出出错的推断，所以B3=5可能是正确的判断，如果能判断出B3&&6，则才能肯定B3=5。
所以下面我们还需要用B3=6进行测试
在B3添入6，推出B8=5。
观察C行，C7，C8，C9必含有数字5。
证明B3=6是错误的。从而得出B3=5
二、候选数法：
1、唯一候选数法
候选数法解题的过程就是逐渐排除不合适的候选数的过程，当某个宫格的候选数排除到只有一个数的时候，那么这个数就是该宫格的唯一的一个候选数，这个候选数就是解了。
我们可以排除D3为的可能，经过候选数的安全删除后，D3的候选数变为&4&这个唯一候选数了。
2、隐性唯一候选数法
当某个数字在某一列各宫格的候选数中只出现一次时，那么这个数字就是这一列的唯一候选数了。这个宫格的值就可以确定为该数字。
这时因为，按照数独游戏的规则要求每一列都应该包含数字1～9，而其它宫格的候选数都不含有该数，则该数不可能出现在其它的宫格，那么就只能出现在这个宫格了。
对于唯一候选数出现行，九宫格的情况，处理方法完全相同
这是制作好的一张候选数表，注意观察B5，B9，D1
可以看出在第1列，数字9只在D1出现。
在第5列，数字3只在B2出现。
在B9所处的九宫格里，数字9只有在B9出现。
所以“9”是第1列的隐形唯一候选数。
“3”是第5列的隐形唯一候选数。
“9”是A7九宫格的隐形唯一候选数。
所以确定D1＝3，B5＝3，B9＝9
3、三链数删减法
找出某一列、某一行或某一个九宫格中的某三个宫格候选数中，相异的数字不超过3个的情形，进而将这3个数字自其它宫格的候选数中删减掉的方法就叫做三链数删减法。
三链数删减法的原理如下面图示
在H行，H2，H5，H7的候选数（12），(23)，(13)，构成三链数，那么123这三个数在H行将只能出现在H2，H5，H7，那么本行其它宫格就可以删除这3个候选数了。这是三链数发生在行的情况。
在G7所在九宫格，G7，H8，I9的候选数（12），(23)，(13)，构成三链数，那么123这三个数在这个九宫格将只能出现在G7，H8，I9，那么本九宫格其它宫格就可以删除这3个候选数了。这是三链数发生在九宫格的情况。
三链数是数对的扩展，我们在对上面的三链数进行扩展，得到右边的特殊的三链数，只要保证在3个宫格内，其包含的候选数也为3个，就都符合我们的要求，比如(123，123，123)，(12，12，123)都符合要求。
我们进一步再扩充，发现只要在N个宫格内，其包含的候选数也恰为N个，那么处理和三链数是相同的道理，这样就形成了四链数，比如(12，23，34，14)，(123，123，14，1234)等。
甚至可以扩充到五链数，七链数（虽然在实际解题中作用不大了）。
平时我们用到最多的就是三链数，四链数了。
在A4所在九宫格，我们看到B4~B6，形成三链数，则本九宫格其它宫格就可以去除候选数&2&，&7&，&9&，这样就得到C6=4。
同上面完全相同的一副图，在A行，A7~A9形成由179构成的三链数，排除本行其它宫格的候选数179后得到A3=3。
4、隐性三链数删减法
隐性三链数是从隐性数对发展而来的。
在某行，存在三个数字出现在相同的宫格内，在本行的其它宫格均不包含这三个数字，我们称这个数对是隐形三链数。那么这三个宫格的候选数中的其它数字都可以排除。
当隐形三链数出现在列，九宫格，处理方法是完全相同的。
我们进一步扩充，在某行（列，九宫格），存在N个数字出现在相同的宫格内，在本行的其它宫格均不包含这N个数字，我们称这个数对是隐形N链数。那么这N个宫格的候选数中的其它数字都可以排除
在中间九宫格，候选数“2”，“5”，“9”仅出现在E4，E6，F4，形成隐形三链数，所以在E4，E6，F4，可以排除其它候选数，得到F4=9。
5、矩形顶点删减法
矩形顶点删减法和直观法讲到的矩形摒除法分析方法是一样的。矩形顶点删减法在识别时比较不容易找到，所以最好先使用其它的方法。
如上图，如果在第3列，候选数“9”只能在B3或H3出现。在第7列，候选数“9”只能在B7或H7出现。
则B3，H3，B7，H7构成矩形，符合矩形顶点删减法的条件。
由上，可以得出数字“9”仅可能出现在(B3，H7)上，或者出现在(B7，H3)上
无论出现上面的那一种情况，我们都可以推断出B行，H行的红色区域都不能再为数字9了。可以将红色的宫格的候选数中去除数字“9”。
举例说明如下：
在第3列，数字“3”仅在A3、H3出现和第6列，数字“3”仅在A6、H6出现，A3、H3，A6、H6构成矩形，符合矩形顶点删减法要求，
则红色宫格应排除候选数“3”
6、三链列删减法
三链列删减法是矩形顶点删减法的扩展，如果不清除矩形顶点删减法，可以参考矩形顶点删减法，以便于更容易理解本节内容。
利用“找出某个数字在某三列仅出现在相同三行的情形，进而将该数字自这三行其他宫格候选数中删减掉”；或“找出某个数字在某三行仅出现在相同三列的情形，进而将该数字自这三列其他宫格候选数中删减掉”的方法 就叫做三链列删减法。
如果数字“1”可能出现在B行、E行、G行的黄色宫格，则符合“某个数字在某三列仅出现在相同三行的情形”，符合三链列删减法的要求。
则红色宫格均不包含候选数“1”。
这是前图的一个变形。其中一行的“1”只能放在这一行的两个位置。 处理和上图一样，红色宫格均可以排除候选数“1”。
举例说明：
数字&6&在第2列，第6列，第8列。均出现在A，B,I行。其中在第6列仅出现B,I行，仍然符合三链列删减法的要求。
则红色宫格均可以排除候选数&6&
7、关键数删减法
在进入到解题后期，利用前面讲到的唯一候选数法、隐性唯一候选数法、 区块删减法、数对删减法、隐性数对删减法、 三链数删减法、隐性三链数删减法、矩形顶点删减法、三链列删减法都无法有进展的时候，可以考虑使用关键数删减法。关键数删减法就是在后期找到一个数，这个数在行（或列，九宫格）仅出现两次的数字。我们假定这个数在其中一个宫格类，继续求解，如果发生错误，则确定我们的假设错误。如果继续求解仍然出现困难，不妨假设这个数在另外一个宫格，看能不能得到错误。这就是关键数删减法。
关键数删减法的本质是让我们一个个去测试，逐渐排除不可能的候选数，从而求解的过程。
这种解法就暂时不举例子了
阅读(...) 评论()}