先祝帕索版版友新春大吉，谜题道道拢解开 跨了两个年，大家有没有忙到没空关心杂七杂八的消息呢，听说有人已经把 最小数独问题解决了唷！ 结论是： 所有16-数独都不存在唯一解答。 浆酱~ 最早是从果壳网看到的报导 http://www.guokr.com/article/89169/ 然後去arXive找原本论文 http://arxiv.org/pdf/1201.0749v1.pdf (Gary McGuire et al.) 非常有趣，写的让即使对技术细节不全了也可以懂他们是怎麽改进算法，让问题 缩小到可执行的程度。 内文有几个点我提一下 - - - - Frazer Jarvis 和 Ed Russell 在2006 证明了数独独特的解答盘面 共有5,472,730,538 种。 此结果已获得多次验证无误，并且已有人以程式枚举(Enumerate)出所有盘面! (论文节4.3) - - - - 论文第七页提及: 台湾交大的吴毅成教授团队－－大大残念了 http://www.pac.nctu.edu.tw/News/news_more.php?id=381 在2010年吴教授改进了上面作者Gary McGuire 在2006年提出的演算法(提升129倍效率)， 然後直接就号召各界网友乡民，欲用平行演算的方式跟难题硬干... 结果在2011年年初，这project算到一半就当机了XXD http://sudoku.nctu.edu.tw/joomla/ 据该网页，他们现在的进度只有1/3不到，应该相当扼腕吧。 Gary McGuire教授果然比较凶猛，对算法的改进更牛人一截 = = - - - - 另外就是要怎麽只用三言两语说服人 唯一解16-数独答案是 极度相当非常无敌可能不存在~~的呢 (如果你像我一样口拙，有点难解释论文一般的详细过程；或是你的解释对象是 四色问题纸笔解基本教义份子，不相信任何电脑跑出来的结果XD) 文中有提到(@第八页) : 现在已知的唯一解17-数独 有约50,000个 (等价则视同一个) 收集这些解的网站 可以参考 #1EDExtM_ (puzzle) 推文中 LPH666 和utomaya大提供的网址 这些17-数独当中，彼此最终会得到「相同的最终结果(completion)」的 最高纪录是29个。 6 3 9 2 4 1 7 8 5 也就是左边这个最终解答。以穷举法可以从中得到 2 8 4 7 6 5 1 9 3 5 1 7 9 8 3 6 2 4 不多不少29个唯一解的17-数独 1 2 3 8 5 7 9 4 6 7 9 6 4 3 2 8 5 1 4 5 8 6 1 9 2 3 7 3 4 2 1 7 8 5 6 9 8 6 1 5 9 4 3 7 2 9 7 5 3 2 6 4 1 8 (@论文第25页提到对这个结果确认) 重点来了， 假设今天我们有一个 唯一解 16-数独，借由再添一个数字上去，我们洽可以得到 81-16 = 65个 唯一解 17-数独 彼此有共同的解答。 如果观察已知17-数独的「解答重数」，最大值是29，其余形成某个统计分布，借由 统计方法可以估计「新找到一整群有共同的唯一解的17-数独，其成员数至少是65」 的机率。 而无论如何这机率都该是微乎其微。理论完了~ 上面所说是先预设前述50,000个解答是由全世界许多人 无共识而且随机开始，再用 程式辅助找寻。所以即使整个数独的「解答空间」很大大大大的n次方，但他们的搜 寻可相当於在里面随机取样~~~ 当然以上理论 无法完全排除哪天突然找到以上所述的一大群17-数独，其中蕴含一个 唯一解16-数独 直到本文作者硬是将所有数独穷举，证明普天之下竟真的连一个16-数独都没有! << 太精采了! >> --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.164.4.251 ※ 编辑: jurian0101 来自: 218.164.4.251 (01/26 01:33)