现在,一位爱尔兰数学家使用一套极为重大的运算规则以及数亿小时的“超等盘算”,解决了数独运算中的一个主要的开放问题。数独是在日本以致全球很是盛行的一种游戏,玩法是凭证一定规则在一个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个提醒来解决。