2005-11-19

Sudoku (數獨.數讀.數毒?)

最近,我同事每朝拿一份《頭條日報》 回公司,而內頁有一個數字遊戲叫 Sudoku。我看了看,輕描淡寫地認為是個很簡單題目,隨便寫個程式便可以解決,亦不相信有很多人真的會玩。於是,無聊的我便在週末閒著的時候,寫了個很簡單的 Excel VBA,幻想從此可以靠贏取《頭條日報》的「年廿八碌柚葉沐浴露」來沖涼。

寫那程式倒是容易,花了六、七小時便寫好。然而執行的時候卻發現有些情況還是要人腦作決定,不能完全自動。那意味著這不是一個簡單的問題。於是我便上網搜集多些題目來測試我的程式。誰料一查之下,才發覺這遊戲已揭起一個全球的熱潮!而讓這有二百年歷史的遊戲重生的,竟是一個前香港高等法院的法官高樂德 (Gould, 2005 ; see also Wikipedia, 2005b, 2005c)!

經過一輪研究,我發現原來這個問題是一個 NP-Complete 的問題。NPNon-Deterministic Polynomial 的意思 (Wikipedia, 2005a)。這要和我大學時學的人工智能 (AI) 有關。當我們嘗試用電腦去解決一個問題的時候,我們要知道這問題是不是只要假以時日就「必定」可以解決?其次是有沒有更快、用更少記憶體的方法?前者的那個「必定」便是 Deterministic 的意思。而後者所謂的快慢,是由所需的時間與問題大小的關係來決定。譬如說,要知一個數是不是另一個數的因數,只需要除一除;有一個數除一次,有十個數除十次,那便是簡單的成正比,或曰 O(n),讀成「Big O of n」。也有問題是幾何級數的,好像以前學的,幫一副紙牌排序,是 O(n^2),優化後成 O(n ln n)。這便是 Polynomial 的意思。至於好像捉棋,有點需要嘗試與運氣的,行錯了又要回手再想的,便是所謂 NP-Complete 的問題,一般電腦只能算出之後五、六步的所有可能性,卻不能算出所有棋局。好了,說來這麼久,我只是想說 Sudoku 是一個 NP-Complete 的問題,並非表面那麼簡單。完成的 Sudoku 叫 Latin Square,而對稱的 Latin Square 總共有 5,472,730,538 個 (Sudoku Today, 2005)!那就是所謂的 Problem Space 或 Solution Space。運算所有組合的程式,是大 O 的三次方,即是 O(n^3) (Taylor, 2005)。似乎只用 Excel VBA 是「殺牛用雞刀」了!

其實,已經有人比我早一步用 VBA 寫了個程式 (Ireland, 2004);我更無意中發現了有人用三句 Perl 便寫了個能解決簡單 Sudoku 的程式 (von der Burg, 2005; 但由於 Sudoku 是 NP-Complete,沒有程式「必定」能解決所有的 Sudoku)。這令我想起在大學修讀電腦的時光。我們的學系叫「計算機科學系」,所以在我都曾經是一個「計算機科學家」!那時候同學都以用最少的程序去解決問題為榮,出來工作後,才發現讓別人一看便能理解的程式才叫好。說起來,我是從來沒有正式讀過 AI 那一科。我當時想選讀 AI 和商業法 (Business Law),但它們卻有時間上的衝突。最後我決定在開學前的暑假把兩本書都買來先看看。那本 AI 的書 (Russell & Norvig, 1995) 叫我愛不釋手,不消一個多月便看完了。還記得那時我在醫管局做暑假工,每天一早便做完我的工作,然後便埋首自學 AI 。至於那本商業法,我看了兩頁便知道,如果沒有人用功課和考試迫我,我是永遠都不會看完的了。所以我最後便選讀了商業法。至於 AI,我也便權充自己讀過了。後來畢業後的那個暑假,我還做了一個月的研究助理,幫我的教授用 Prolog 和 Tcl/Tk 去將一個有關 AI 與電力分配的論文變成程式模型;由於時間緊迫,我還誠邀白頼仁兄拔刀相助,才能如期完成。那次也是我第一次在實驗室的長硬桌上睡覺呢。不久之後,那論文提倡的電力自由市場,卻竟導致加洲大停電,那是後話了。

現在回想起來,當年學的「計算機科學」,與今天資訊科技 (IT) 這行業的工作,其實並沒有太大的關係。這些理論與學問,就如中學時學的數理化一樣,只是用來鍛鍊我們的思考力與記憶力。後來自己再讀工商管理 (MBA),學的也不是怎樣去平每一本帳目,而是去學一個正確的概念 (Mindset),好像如果公司需要資金,向銀行借貸會比上市集資便宜很多;至於便宜多少,自然有電腦系統或專業人員去估算。IT 也是一樣。IT 行裏有軟硬件銷售、項目管理、軟件工程、網路管理、電訊設備、資訊保安等等,五花八門,又怎可能每樣都懂。朋友曾說,門鎖壞了、燈泡燒了、廁所塞了,都是 IT!親戚朋友便常問,咦,你「做電腦」的,可否看看我家的電腦為什麼跑不動了?老實說,我可以做的只是去好言安慰你的電腦,希望它回心轉意而已。

雖然如此,閒來寫寫程式,動動腦筋,總能延遲老人痴呆罷?

Reference:
Gould, W. (2005). Sudoku: One of the puzzles by Pappocom. Retrieved from http://www.sudoku.com

Ireland, D. (2004). Su doku solver. Retrieved from http://www.di-mgt.com.au/sudoku.html

Russell, S. J., & Norvig, P. (1995). Artificial intelligence: A modern approach (1st Ed.). Prentice Hall. Retrieved from http://www.amazon.com/gp/product/0131038052

Sudoku Today. (2005). Sudoku Algorithm. Retrieved from http://www.sudokutoday.com/sudoku-algorithm.html

Taylor, P. (2005). Sudoku algorithm for available numbers. Retrieved from http://forum.java.sun.com/thread.jspa?threadID=666311&messageID=3928804

von der Burg, E. (2005). Blogs. Retrieved from http://www.ecclestoad.co.uk/blog

Wikipedia. (2005a). Complexity classes P and NP. Retrieved from http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP

Wikipedia. (2005b). 數獨. Retrieved from http://zh.wikipedia.org/w/index.php?title=%E6%95%B8%E7%8D%A8&variant=zh-tw

Wikipedia. (2005c). Sudoku. Retrieved from http://en.wikipedia.org/wiki/Sudoku

Bibliography:
Eppstein, D. (n.d.). Computational complexity of games and puzzles. Retrieved from http://www.ics.uci.edu/~eppstein/cgt/hard.html

Gwerdy Software. (2005). SuDoku Solver algorithm explained. Retrieved from http://www.gwerdy.com/products/sudoku_solver/index.php

4 則留言:

stuartbabble 說...

hi,
great post. How long have you been blogging? I really love this blog and have added it to my favourites. I have just set up a website all about book digit easy puzzle sudoku, perhaps you could take a look and let me know what you think.

狂人.Paul Sin 說...

Hi Stuart,

Thanks for your posting. Your site has great wealth of information, don't think I can find the link back to my site :D Plus your audience probably don't understand Chinese. I've been only blogging for two months. Couldn't find your email or blog, hence post my reply here. Thanks for visiting.

Best Regards,
Paul Sin.

匿名 說...

寫得很棒!有喚起我對computer science的感覺了,收集資料很認真,謝謝你的介紹。

yllan 說...

: 但由於 Sudoku 是 NP-Complete,沒有程式「必定」能解決所有的 Sudoku

這句話有問題。所有的 NP-Complete 問題都可以在 EXP 內被解決,只是時間的多寡