[情報] 16-數獨沒有唯一解

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者jurian0101 (Hysterisis)時間14年前 (2012/01/26 00:55)推噓6(6推 0噓 6→)

留言12則, 7人參與討論串1/1

先祝帕索版版友新春大吉，謎題道道攏解開跨了兩個年，大家有沒有忙到沒空關心雜七雜八的消息呢，聽說有人已經把最小數獨問題解決了唷！結論是：所有16-數獨都不存在唯一解答。漿醬~ 最早是從果殼網看到的報導 http://www.guokr.com/article/89169/ 然後去arXive找原本論文 http://arxiv.org/pdf/1201.0749v1.pdf (Gary McGuire et al.) 非常有趣，寫的讓即使對技術細節不全瞭也可以懂他們是怎麼改進算法，讓問題縮小到可執行的程度。內文有幾個點我提一下 - - - - Frazer Jarvis 和 Ed Russell 在2006 證明了數獨獨特的解答盤面共有5,472,730,538 種。此結果已獲得多次驗證無誤，並且已有人以程式枚舉(Enumerate)出所有盤面! (論文節4.3) - - - - 論文第七頁提及: 台灣交大的吳毅成教授團隊－－大大殘念了 http://www.pac.nctu.edu.tw/News/news_more.php?id=381 在2010年吳教授改進了上面作者Gary McGuire 在2006年提出的演算法(提升129倍效率)，然後直接就號召各界網友鄉民，欲用平行演算的方式跟難題硬幹... 結果在2011年年初，這project算到一半就當機了XXD http://sudoku.nctu.edu.tw/joomla/ 據該網頁，他們現在的進度只有1/3不到，應該相當扼腕吧。 Gary McGuire教授果然比較兇猛，對算法的改進更牛人一截 = = - - - - 另外就是要怎麼只用三言兩語說服人唯一解16-數獨答案是極度相當非常無敵可能不存在~~的呢 (如果你像我一樣口拙，有點難解釋論文一般的詳細過程；或是你的解釋對象是四色問題紙筆解基本教義份子，不相信任何電腦跑出來的結果XD) 文中有提到(@第八頁) : 現在已知的唯一解17-數獨有約50,000個 (等價則視同一個) 收集這些解的網站可以參考 #1EDExtM_ (puzzle) 推文中 LPH666 和utomaya大提供的網址這些17-數獨當中，彼此最終會得到「相同的最終結果(completion)」的最高紀錄是29個。 6 3 9 2 4 1 7 8 5 也就是左邊這個最終解答。以窮舉法可以從中得到 2 8 4 7 6 5 1 9 3 5 1 7 9 8 3 6 2 4 不多不少29個唯一解的17-數獨 1 2 3 8 5 7 9 4 6 7 9 6 4 3 2 8 5 1 4 5 8 6 1 9 2 3 7 3 4 2 1 7 8 5 6 9 8 6 1 5 9 4 3 7 2 9 7 5 3 2 6 4 1 8 (@論文第25頁提到對這個結果確認) 重點來了，假設今天我們有一個唯一解 16-數獨，借由再添一個數字上去，我們洽可以得到 81-16 = 65個唯一解 17-數獨彼此有共同的解答。如果觀察已知17-數獨的「解答重數」，最大值是29，其餘形成某個統計分布，借由統計方法可以估計「新找到一整群有共同的唯一解的17-數獨，其成員數至少是65」的機率。而無論如何這機率都該是微乎其微。理論完了~ 上面所說是先預設前述50,000個解答是由全世界許多人無共識而且隨機開始，再用程式輔助找尋。所以即使整個數獨的「解答空間」很大大大大的n次方，但他們的搜尋可相當於在裡面隨機取樣~~~ 當然以上理論無法完全排除哪天突然找到以上所述的一大群17-數獨，其中蘊含一個唯一解16-數獨直到本文作者硬是將所有數獨窮舉，證明普天之下竟真的連一個16-數獨都沒有! << 太精采了! >> -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.164.4.251 ※ 編輯: jurian0101 來自: 218.164.4.251 (01/26 01:33)