數獨 (Su DoKu) 的程式解

據說，靈長類的動物，都喜歡玩遊戲。

或許是出於天性，自己一直對於益智遊戲頗感興趣。而設計程式，不也是為了解決某個問題嗎？因此，從某種角度觀看，也可以將「不算複雜的程式設計」，當作一種益智遊戲。如此一來，程式設計與實作，就相當於發展出「如何找出遊戲答案」的方法了。

或許是由於媒體的炒作與推波助瀾，數獨 (Su DoKu) 在這幾個月裡，似乎吸引了不少閒暇排遣的大眾目光。上網路書店博客來查了一下，光是書名包含「數獨」的資料，就有 45 筆呢。

數獨的遊戲規則很簡單，就是在一個 9x9 的方陣中，給定一些 1~9 的數字；然後遊戲玩家必須在其他的空格裡填入 1~9 的數字，讓方陣的每一行、每一列、以及（將方陣切分為 9 個） 3x3 的小方陣裡，都不重覆地出現 1 到 9 的數字。

例如，下圖左方就是一個數獨問題的盤面，而右方則是這個問題的（唯一）解答。


解解數獨，就像是以往令人懷念的填字遊戲，可以在閒暇時鍛鍊自己的腦力。不過，對關心程式設計的人來說，怎樣寫出一個「能夠自動解數獨」的程式，或許才是有趣點。

這個問題並不難，網路上也已經有豐富的相關資源。用 Google 搜尋 Su Doku，很快就可以找到許多數獨相關的網站，有的提供線上遊戲，有的則連程式的原始碼都附上了。

但說實在地，在看過答案（程式原始碼）之前，自己思考、設計與實作這樣的程式，還是有趣得多（雖然，花時間做這樣的思考與實作，沒能得到什麼實質上的回饋）。而我不是也想整理些有趣的小程式嗎？數獨或許是一個不錯的主題吧。

因此，花了些時間，自己用 PHP 開發了一份解數獨的程式。貫穿程式的演算法，是 number-of-choices（可能的選擇數目；或者說是可能性）的想法，以及 backtracking（回溯）的機制。 Number-of-choices 的意思，是找出每個空格裡，有多少種可能的數字；而 backtracking 則是當程式發覺某條路走不下去時，回溯到先前的狀態，換另外一條路走。

對於上圖左方的問題，每個空格「可能出現的數字」總數（可能性），就如右圖紅色字體所示。例如，從左邊數來第三格、上邊數來第三格，原本可以填 1~9 的任意數字；但因為同一列 (row)已經出現數字 1, 2, 3, 7, 8，同一行 (column) 已經有數字 2, 3, 4, 5, 6，且同一個 3x3 子方陣已經填有 2, 3, 5, 7，因此這個格子裡，不可能填 1~8 的數字，它的可能性（用紅色數字表示）只剩下 1。

可能性為 1 的方格，表示已經可以決定這個方格內的數字。因此程式可以將這個數字找出來，填寫進去，然後產生一份新的盤面。接下來，重覆運用可能性的觀念，計算這個新盤面裡每個空格的可能性，可以算出更多可能性為 1 的方格數字；如此反覆計算，最後就可以得到解答。

困難些的數獨問題，會讓盤面裡的每個空格，可能性都超過 1。例如，下圖左方的盤面，每個空格的可能填寫的的數字總數，就都大於 1（用紅色字體標示於下圖右方）：


遇到這樣的盤面，我的程式會尋找目前具有最小可能性的方格（如果有數個方格有相同的最小可能性，就選擇「填入數字後，能夠降低最多其他方格可能性」的空格來填），猜測一個可能的數字，然後看看填入這個數字後，是不是能夠找到解答。如果最後失敗了（有某個空格可能性小於或等於零，意味著找不到解答），就表示這個數字猜錯了；這時程式會退回猜測前的狀態，重新選一個數字，然後繼續找尋問題的答案。

有時，一個數獨盤面也可能得出多種解答。至於上圖那個「比較困難」的數獨問題，很容易用程式算出唯一解：


雖然想要藉由這類的益智問題，來介紹、討論程式設計的一些相關課題，但還是懷疑自己是否有足夠的能力、毅力、與恆心來完成。既然對自己這麼沒有把握，那麼先利用 Blog 記錄一些目前的想法與結果，或許也是個不錯的作法吧。

後記：原先我把 number-of-choices 寫成 degree-of-freedom（自由度）。雖然「有多少種可能出現的選擇」(number-of-choices) 多少也代表「可自由變化的程度」，但 degree of freedom 是一個廣被接受的 well-defined term，還是不要錯用、亂用比較好。