Sudoku（作者：狂人Paul Sin）

2008-03-29 14:08:51 来自: 倉海君

2005-11-19
Sudoku (數獨．數讀．數毒？)

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

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

經過一輪研究，我發現原來這個問題是一個 NP-Complete 的問題。NP 是 Non-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

2008-03-30 22:37:12 way (way)

受了同样爱好数独的朋友邀请来这组，对这组到底怎么回事还不是太明白，单这篇写数独的写得不错，就加入了。

为什么说写得不错，借用作者本人解释什么是好的程式（大陆这边叫方程式？）的话就是“让别人一看便能理解”，这篇其实就数独本身没有太多深入介绍，由数独引发的话说得清楚明白，让我这个没上过计算机科学系的人也看个八九不离十。

> 删除
2008-04-02 00:02:39 henrry

我要找人来看看了

> 删除
2008-04-03 19:52:42 养猫的宅男||||增肥 (早日早日有朝一日每朝一日)

都唔明嘎～～

> 删除
2008-04-03 20:06:28 Benjamin (Evenhile seated)

Sudoku很有意思的

> 删除
2008-04-09 15:48:53 WHY

哈哈,我挺喜欢玩SUDOKU的.

> 删除
2008-04-09 15:52:00 kay

大家都是数独爱好者啊

> 删除
2008-04-14 04:00:05 文泽尔 (潜心报告.暂别豆瓣)

9x9数独必能用穷举法列出所有解，或者判断无解，无需人工干预。
做数独有一些诀窍，掌握之后就变得程式化、机械，不再有趣。最小唯一解问题（唯一解数独最少需要给出多少个数字）才是值得研究的东东..^^

> 删除
2008-04-14 15:19:15 双人床Ω (我的爱？？我自己？？)

因为喜欢数独而+入这个小组。

十分同意LS，“一解数独最少需要给出多少个数字才是值得研究的东东..”

> 删除
2008-04-16 21:01:15 oohlala

掌握技巧后就好无聊的

研究最小唯一解对于我又过于高深

> 删除
2008-05-23 23:30:23 耶麦

这个有意思。。。。

> 删除
2008-06-27 15:29:34 顿宁

我經常列印出數獨題隨身帶嗰啵，無聊嘅時候玩玩

> 删除
2008-06-30 22:20:32 凝夕

我手机上就有，搞不定的时候就把所有可能都列出来。一个一个试

> 删除
2008-09-07 01:23:20 大P

手机里有，看不懂说明--

> 删除
2008-12-12 10:28:03 明月如霜

《頭條日報》的數獨太簡單lar
沒等回到公司就填完
後來自己上網列印d惡魔級隨身攜帶....

> 删除
2008-12-12 10:35:55 明月如霜

很有興趣想認識下這位
狂人Paul Sin 呢呵呵

> 删除
2008-12-12 13:05:08 Gwing

閒來寫寫程式，動動腦筋，總能延遲老人痴呆罷

我钟意这句

> 删除
2008-12-19 03:25:38 年少无知

高三玩过一段时间，打发时间的玩意

> 删除