|
|
700万小时搞定最小数独问题
sqybi 发表于 2012-01-14 18:42
刚刚迈入 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
一个经典的数独。图像来源：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 个数为初始数字的数独有唯一解。
如果检查所有的可能情况，对于每一个等价类，我们要检查的次数就是：
/gkimage/ld/cs/bh/ldcsbh.png
这显然很不幸：好不容易通过排除等价变换的方法把计算量减下去，怎么能在这里再加回来呢！所以这又需要数学家再做一些工作，把 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 越来越难越来越精彩了。你做过的最难的数独是什么？在这里抛一块砖：
/gkimage/3m/zl/eu/3mzleu.png
参考资料： There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem
http://www.guokr.com/article/89169/ |
|
楼主: newkid
IP卡
狗仔卡
发表于 2016-9-30 22:19
显身卡
