愛爾蘭數學家利用一套極為複雜的運算法則以及數百萬小時的“超級計算”，解決了數獨運算中的一個重要的開放問題。數獨是在日本乃至全球非常流行的一種遊戲，玩法是按照一定規則在一個9×9的方格內填寫數字1到9。
都柏林大學學院的Gary McGuire於1月1日在互聯網上貼出了自己的證明——完成一次數獨所需的最小提示數（或起始數）是17；而16個或更少的線索則無法得到唯一解。大多數報紙上的數獨都有25個線索，而隨著提示的減少，遊戲的難度也不斷增加。
在1月7日於美國波士頓市召開的一次會議上，數學家們就此達成了共識，McGuire的證明很可能是有效的，並且是發展中的數獨領域的一項重要進展。
弗吉尼亞州哈里森堡詹姆斯•麥迪森大學的數學家Jason Rosenhouse是一本即將出版的數獨演算法書籍《嚴肅看待數獨：全球最流行的鉛筆遊戲背後的數學》(Taking Sudoku Seriously: The Math Behind the World’s Most Popular Pencil Puzzle)的作者之一，他認為：“這一方法是合理的，並且似乎是可靠的。對此我持謹慎樂觀的態度。”
數獨的規則要求遊戲者用1到9填滿9×9的方格，同時每個數位在同一行、列以及3×3的小方格中不能重複，而所謂的線索或提示則是事先填充在其中的數字。數獨愛好者經過長期的觀察發現，儘管會有17個提示的數獨出現，但沒有人能夠提出一個僅有 16個提示的有效數獨。這導致了一種推測，即具有16個提示且有唯一解的數獨根本不存在。要想證明這一點的一個潛在方法便是核對所有可能的16個線索的數獨，但這需要太多的運算時間。因此McGuire通過設計一個“打集合演算法”簡化了這一問題。
McGuire和他的研究小組花了兩年時間來測試這一演算法——他們在都柏林的愛爾蘭高端計算中心耗費了約7百萬個CPU小時，利用“打集合演算法” (hitting set enumeration algorithm)來尋找可能的方格。同樣利用不同演算法證明17個線索的數獨的佩斯市西澳大利亞大學的數學家 Gordon Royle表示：“做到這一點的唯一現實辦法就是這種強力的方法……這是一個極具挑戰性的問題，它可以激發人們將計算與數學方法推向極限，就像在攀登最高的山峰。”
與Rosenhouse合作著書的詹姆斯•麥迪森大學的數學家Laura Taalman表示，這一方法的結論需要一段時間以便讓其他人進行足夠的計算加以證明。而Taalman強調，他們的新書還未出版（將於下周出版）便已過時——書中認為這一問題還將長期存在，而解決它的人將成為“搖滾巨星”。
McGuire表示，他的方法還可能在其他領域產生作用。這種“打集合演算法”已經被用於基因測序分析和蜂窩網路的論文中，McGuire期待它能夠被更多的研究人員所利用。他說：“希望這種演算法能夠激發更多的興趣。”
但具有諷刺意味的是，McGuire花了太多時間證明數獨難題，但卻沒空享受這種遊戲。“我現在依然覺得這是一種很好的放鬆方式，但說實話，我更喜歡縱橫字謎。”
中國科學報 2012/01/09
相關連結
- Mathematician claims breakthrough in Sudoku puzzle: Puzzles must have at least 17 clues to have a valid solution. (Nature News)
- Taking Sudoku Seriously: The Math Behind the World’s Most Popular Pencil Puzzle, ISBN: 978-0199756568 (Amazon)
- There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem (arXiv.org)
沒有留言:
張貼留言