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

luyuanhong

爱尔兰数学家破解数独之谜
作者：赵路
来源：中国科学报
你玩过数独（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个提示来解决。

cx654321

坚定的信心是不可少的

cx654321

不能想象数学家的大脑到底是个什么样的逻辑思维!

王小峰

如果证明没有问题，这个结论是很有意义的。17这个数字蛮有诱惑力。