作者：尤金妮·塞缪尔·雷克，来自《自然》杂志
一位爱尔兰数学家使用了一种复杂的算法和数百万小时的超级计算时间来解决数独数学中的一个重要的未解决问题，数独是在日本普及的游戏，它涉及根据某些规则在 9x9 的方格中填入数字 1-9。
都柏林大学学院的加里·麦奎尔在 1 月 1 日在线发布的一份证明中表明，完成一个谜题所需的最小线索数——或起始数字——是 17 个；线索少于或等于 16 个的谜题没有唯一的解。大多数报纸上的谜题大约有 25 个线索，随着线索的增多，谜题的难度会降低。
关于支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。通过购买订阅，您正在帮助确保未来能够继续讲述关于塑造我们当今世界的发现和想法的有影响力的故事。
1 月 7 日在马萨诸塞州波士顿举行的一次会议上，数学家们逐渐达成共识，认为麦奎尔的证明可能是有效的，并且是不断发展的数独数学领域中的一项重要进展。
“这种方法是合理的，并且是可信的。我认为现在的态度是谨慎乐观，”弗吉尼亚州哈里森堡詹姆斯·麦迪逊大学的数学家杰森·罗森豪斯说，他是一本新出版的关于数独数学的书的合著者。
数独的规则要求解谜者在一个 9x9 的方格中填入数字 1-9，使得同一列、行或 3x3 子方格中没有数字重复。线索是最初填入的数字，爱好者们长期以来观察到，虽然有一些谜题有 17 个线索，但没有人能够提出有效的 16 个线索的谜题。这导致了一个猜想，即具有唯一解的 16 个线索的谜题根本不存在。证明这一点的潜在方法可能是检查每个 16 个线索的谜题的所有可能的完整网格，但这将花费太多的计算时间。因此，麦奎尔通过设计一种“命中集算法”简化了问题。这背后的想法是搜索他称之为不可避免的集合，或完整谜题中数字的排列，这些排列是可以互换的，因此可能导致多个解。为了防止不可避免的集合导致多个解，线索必须重叠，或“命中”不可避免的集合。一旦找到不可避免的集合，证明没有 16 个线索的谜题可以命中所有这些集合就变成了一项小得多的——尽管仍然不简单的——计算任务。
在花费两年时间测试该算法后，麦奎尔和他的团队在都柏林爱尔兰高端计算中心使用了大约 7 亿 CPU 小时，使用命中集算法搜索可能的网格。“唯一现实的方法是暴力破解方法，”西澳大利亚大学珀斯分校的数学家戈登·罗伊尔说，他一直在使用不同的算法研究计算 17 个线索谜题的问题。“这是一个具有挑战性的问题，它激励人们将计算和数学技术推向极限。这就像攀登最高的山峰。”
詹姆斯·麦迪逊大学的另一位数学家劳拉·塔尔曼说，所采取方法的一个结果是，其他人需要一些时间才能获得足够的计算时间来检查这个证明，她也是《认真对待数独：世界上最流行的铅笔谜题背后的数学原理》一书的合著者，罗森豪斯也是该书的合著者。塔尔曼指出，上周出版的这本书已经过时了：它说这个问题仍然悬而未决，谁解决这个问题将成为“摇滚明星”。
麦奎尔说，他的方法可能会在其他方面有所回报。他为证明开发的命中集思想已被用于基因测序分析和细胞网络方面的论文中，他期待着看看他的算法是否可以被其他研究人员有效地改编。“希望这将激发更多兴趣，”他说。
但他表示，具有讽刺意味的是，随着他将更多时间投入到这个难题的数学研究中，他花在享受谜题上的时间却变少了。“我现在仍然觉得这是一种不错的放松方式，但老实说，我更喜欢玩纵横填字游戏，”他说。
这篇文章经《自然》杂志许可转载。 该文章于 2012 年 1 月 6 日首次发表。