16-數獨沒有唯一解 - 數獨

先祝帕索版版友新春大吉，謎題道道攏解開

跨了兩個年，大家有沒有忙到沒空關心雜七雜八的消息呢，聽說有人已經把
最小數獨問題解決了唷！

結論是： 所有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-數獨都沒有!

<< 太精采了! >>




--