回覆列表
  • 1 # lanfengz1

    目前(截止2011年)發現的最少提示數9×9標準獨數為17個提示,截止2011年11月24日16:14,共發現了非等價17提示數謎題49151題,此數量仍在緩慢上升中,如果你先發現了17提示數的題目,可以上傳至“17格數獨驗證”網站,當然你也可以在這裡下載這49151題。

    關於是否有16提示數的合格題目,網路上也爭論很久,有發現16提示數雙解的,但是仍未發現唯一解。國外有網友給出了關於為什麼至少需要17提示的證明,受到了大家的質疑,比如9×9對角線獨數(在標準數獨規則基礎上,兩條大對角線的數字不重複)的最小提示數為12,按照他的理論則需要更多的提示數。

    另外在2006年Gary McGuire撰寫了程式,試圖透過暴力法來證明16提示數的數獨是否存在,方法很簡單,既然Bertram Felgenhauer和Frazer Jarvis已經計算出不等價的終盤總數為5,472,730,538個,那麼將每個終盤是16提示的情況都跑一遍,如果沒有找到16提示的數獨,那麼就可以證明最少提示數為17個。但因為是暴力方法,對於一臺單核的電腦來說需要跑30萬年才能跑出結果。臺灣的吳毅成教授和他的團隊將Gary McGuire的程式加以改進,使得效率大幅提升,大約2417年即可完成演算。並放在伯克利開放式網路計算平臺上讓世界加入BOINC的電腦一同演算,令人欣喜的是,截至編輯2012年4月18日已經完成了51.73%。

    Gary McGuire的團隊在2009年設計了新的演算法,利用致命結構的思路,花費710萬小時CPU時間後,於2012年1月1日提出了9×9標準數獨不存在16提示唯一解的證明,繼而說明最少需要17個提示數。並將他們的論文以及原始碼更新在2009年的頁面上。

  • 中秋節和大豐收的關聯?
  • 請問人像攝影師遇到瓶頸如何突破?