爱尔兰数学家破解数独之谜（至少17个提示才能玩）

qianping

爱尔兰数学家破解数独之谜

至少17个提示才能玩，相关算法可用于诸多领域

图片来源：Gary McGuire

来自科学网
你玩过数独（Sudoku，又称九宫格游戏）吗？

如今，一位爱尔兰数学家利用一套极为复杂的运算法则以及数亿小时的“超级计算”，解决了数独运算中的一个重要的开放问题。数独是在日本乃至全球非常流行的一种游戏，玩法是按照一定规则在一个9×9的方格内填写数字1到9。

都柏林大学学院的Gary McGuire于1月1日在互联网上贴出了自己的证明——完成一次数独所需的最小提示数（或起始数）是17；而16个或更少的线索则无法得到唯一解。大多数报纸上的数独都有25个线索，而随着提示的减少，游戏的难度也不断增加。

在1月7日于美国波士顿市召开的一次会议上，数学家们就此达成了共识，McGuire的证明很可能是有效的，并且是发展中的数独领域的一项重要进展。

弗吉尼亚州哈里森堡詹姆斯·麦迪逊大学的数学家Jason Rosenhouse是一本即将出版的数独算法书籍《严肃看待数独：全球最流行的铅笔游戏背后的数学》的作者之一，他认为：“这一方法是合理的，并且似乎是可靠的。对此我持谨慎乐观的态度。”

数独的规则要求游戏者用1到9填满9×9的方格，同时每个数字在同一行、列以及3×3的小方格中不能重复，而所谓的线索或提示则是事先填充在其中的数字。数独爱好者经过长期的观察发现，尽管会有17个提示的数独出现，但没有人能够提出一个仅有16个提示的有效数独。这导致了一种推测，即具有16个提示且有唯一解的数独根本不存在。要想证明这一点的一个潜在方法便是核对所有可能的16个线索的数独，但这需要太多的运算时间。因此McGuire通过设计一个“打集合算法”简化了这一问题。

McGuire和他的研究小组花了两年时间来测试这一算法——他们在都柏林的爱尔兰高端计算中心耗费了约7亿个CPU小时，利用“打集合算法”来寻找可能的方格。同样利用不同算法证明17个线索的数独的佩斯市西澳大利亚大学的数学家Gordon Royle表示：“做到这一点的唯一现实办法就是这种强力的方法……这是一个极具挑战性的问题，它可以激发人们将计算与数学方法推向极限，就像在攀登最高的山峰。”

与Rosenhouse合作著书的詹姆斯·麦迪逊大学的数学家Laura Taalman表示，这一方法的结论需要一段时间以便让其他人进行足够的计算加以证明。而Taalman强调，他们的新书还未出版（将于下周出版）便已过时——书中认为这一问题还将长期存在，而解决它的人将成为“摇滚巨星”。

McGuire表示，他的方法还可能在其他领域产生作用。这种“打集合算法”已经被用于基因测序分析和蜂窝网络的论文中，McGuire期待它能够被更多的研究人员所利用。他说：“希望这种算法能够激发更多的兴趣。”

但具有讽刺意味的是，McGuire花了太多时间证明数独难题，但却没空享受这种游戏。“我现在依然觉得这是一种很好的放松方式，但说实话，我更喜欢纵横字谜。”

数独至少需要17个提示来解决。


《中国科学报》 (2012-01-09 A2 国际)

qianping

顶贴，看来对这个感兴趣的人不多啊

hawking2006

玩过，没有想过。看来随便一个什么东西深入研究水都深得很。

ctoby1

能提供一个打集合算法的例子么