Sudoku is fun!

最近為了不讓自己的腦子退化太多，於是也常常有事沒事上網玩一個美國人很流行的遊戲－數獨。其實整個數獨遊戲就只是一個排列組合的遊戲，但是卻讓人有永遠解不完的題目，和難易不同的階段。我自己的解法都是很直觀的，就是去觀察各個大小九宮格的數字相關性，然後填入數字。聽說有一些奇怪的速解法，不過我還沒去研究過。感覺美國人已經把數獨當成一種全民運動，不管大人小孩都迷上這個玩意；在美國人的小超級市場或是大賣場、加油站的商店、機場的書店等等，都會擺上大大小小幾本的數獨題目本；報紙上也會每天刊登一題。飛機椅背上的雜誌，數獨題目被旅客畫的亂七八糟；公車上也常常看到有下班的人在專心解題。


之前有位著名的網友(似乎有在建中當過教官)發表過一篇數獨的數學研究觀點，滿有趣的所以轉錄如下：

數獨 (Sudoku) 這玩意兒到底怎麼紅起來的, 看在猜謎成性如我的眼中, 簡直莫名其妙.泰晤士報在英國炒作, 日本林立的網站也居功厥偉, 而台灣是由中國時報跟著泰晤士報炒起來的. 現在每個報紙每天都會有一兩個數獨.

我知道這個遊戲至少是十年前的事了. 多年來英文報紙上猜謎的主流是縱橫字謎(crossword), 數獨是偶爾眾多調劑身心換換口味的遊戲中的一種, 名稱也不叫數獨. 我是非常迷縱橫字謎的. 然而縱橫字謎需要太多的智力和字彙, 不是人人都能享受, 而且語言文化的隔閡無法消弭.數獨這個完全沒有文化差異, 容易上手, 又非常花腦筋的推理數學智力遊戲就這樣短短幾年間火紅起來. 現在在 Google 上打 Sudoku, 會出來59,800,000 個網頁, 第一屆的國際數獨電視公開賽去年開始, 有數獨協會, 市面上一堆數獨書, 嘿, 我也買了一本數獨日曆, 每天可以撕一張來動動腦, 很有趣的.

教官要說的是數獨背後的數學... 喔, 這數學可是大有來頭. (我真的要找一年來開通識課 "數學與人生" , 我覺得身邊處處都是數學, 材料根本講不完)

如果你有解過數獨, 難的數獨是真的很不容易解. 有多不容易? 當然, 9*9 的數獨暴力電腦總是可以解決的. 更大一點的數獨呢? 比如說 n^2 by n^2 的數獨有多不容易解? 一個非常讚的答案: NP-complete. 這是幾年前才被證出來的. 可參考
http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf

(Toma按：原連結已失效，可以用下面這個連結看到論文
http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf)

暴力可以解決, 那就寫個程式吧. 網路上好多可以下載. 比如才華洋溢的組合學家Zeilberger, 就寫了一個在 Maple 上跑的程式可以解數獨.
http://www.math.rutgers.edu/~zeilberg/tokhniot/SuDoku

這麼多的報紙和網站, 每天都有不同的謎題, 那不是很快就用光了嗎? 喔, 不會的.

數獨是 9*9 的方格, 首先每排每列都要是1,2,3,4,5,6,7,8,9. 這個叫拉丁方陣. 有多少9*9 的拉丁方陣? 確定 n*n 的拉丁方陣個數是組合數學上的大難題. 9*9 的拉丁方陣一共有 5,524,751,496,156,892,842,531,225,600 個.

可是數獨不只每排每列都要是1,2,3,4,5,6,7,8,9, 數獨的九個 3*3 的小方塊也要有1,2,3,4,5,6,7,8,9 啊, 所以應該少很多. 對. 但是還剩下很多. 去年底數學家才算出來, 一共有 6,670,903,752,021,072,936,960 個可能的數獨謎題. 這兩個數學家寫了一個網頁 http://www.afjarvis.staff.shef.ac.uk/sudoku/ 慶祝這個結果.

可是這麼多個數獨謎題中有些根本是等價的. 比如說, 兩個看來不同的只要把 1 和 2 全部對換就一樣了. 或是說, 轉90 度或翻面等等會變成一樣. 所以應該少掉更多. 對對對, 但是還是很多. 數學家也算出來了. 這計算, 當然用到群論. 本質上不同的數獨謎題一共有 5,472,730,538 個. 結果可參考
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html .
五十億個本質上不同的數獨謎題, 假設每天全球媒體網頁刊登 10000 個本質上不同的數獨, 也要花一萬多年才能全部列完一次啊.

前些日子我去基隆演講, 有個學生在研究怎麼產生數獨謎題. 這是困難的問題. 好的數獨謎題要求提示(已知的數字)是點對稱的, 而且謎題要有唯一解. 當然, 已知的數字愈少愈好. 一個明顯的問題是, 一個唯一解的數獨謎題, 提示的數字可以少到什麼程度? 這是數學上的未解問題! 目前最好的紀錄是 18, 就是說給定 18 個數字就可以唯一解出數獨.如果放寬到不需要點對稱, 最好的紀錄是 17. 在
http://www.csse.uwa.edu.au/~gordon/sudokumin.php 有不少 17 的例子.

如果有人可以證明出 17 是最佳下界, 或是找到 16, 我會非常興奮.

2006, 森棚教官.