Kill Sudoku

前陣子斷斷續續的玩了一陣子數獨(sudoku)，才終於把安裝在我的野火機裡的OpenSudoku的全部謎題解到只剩下一題VeryHard等級的謎題留作紀念。

在解這些題目的過程中一直有個想法，就是想要也自己寫個可以解數獨的小程式。數獨解答機在網路上很多，大多是使用回溯法為基礎的演算法製作的，也就是基於試誤法或窮舉法的方式，和我們一般在解題時使用的方法不同。我想要寫的是一個可以像人類一樣，使用各種技巧來解數獨謎題的程式，解題過程的每一個步驟都要清楚條列出來，這樣這個程式也可以用來作學習用途。

這個想法一直到最近才動手，目前還只是初步階段，寫了一支文字模式的小程式，可以從文字檔案裡讀出一個數獨謎題，將解題過程一個一個步驟都顯示出來，如下圖所示。將來可以寫成圖形化的APP或者是Web的型式，以更豐富的圖式方式來呈現。(HTML5 KillSudoku)

這個程式是基於使用候選數法來製作的，所以從上圖可以看到個一個還未解出答案的格子裡都會列出全部的可能的數字，這些數字就叫作候選數。

~~~

一道數獨謎題是由9(row)x9(column)=81個格子(cell)組成，每一個cell裡可以填入1~9中的一個數字。這9x9個格子裡面，又可以再分成較小的9(box)個3x3的格子。

如上的一個9x9宮格圖所示，左側數字1~9為每一列(row)的編號，上方小寫英文字母a~i為每一行(column)的編號，b1~b9為每一個小九宮(box)的編號。

以上定義了幾個基本名詞：cell, row, column, box，再加上前面所提到過的候選數(candidate)，就是我們全部需要知道的幾個定義。至於數獨的規則部份，這裡就不再複述。

~~~

這個程式的基本原理很單純，只是把我們平常在解數獨題時所用到的手法程式化而已。例如要找唯一數存不存在，就一行一行一列一列的去找看看某數是不是在這一行或這一列裡面是唯一的，如果是的話那就把這個數填入。目前版本的程式還很陽春，只實作了7種pattern，下面一一介紹。使用這7種找pattern的方法最多可以解出初級到中級左右的題目。

在開始找pattern前，需要把輸入資料作一些轉換成內部資料的處理。謎題的輸入是81個數字，由左至右，由上而下，一列一列的由上往下輸入。每一個數字範圍為0~9，0表示這個cell是空的，待填的，1~9則表示這個cell的確定數。

這81個數字讀入後，在程式裡面使用一個一維陣列儲存(int cell[])，同時再以另一個同樣維度的陣列，用來儲前面提到過的候選數(int candidate[]; // bitset)。如果cell[n] != 0，那candidate[n]就不看。如果cell[n] == 0，那就是說cell[n]是空的，那candidate[n]裡存的就是cell[n]的候選數，其中n = 0~80。

整支程式基本上作的事情就是根據程式定義的pattern，想辨法去消減候選數，當某個cell的候選數消減到只剩下一個的時候，那就可以將這個最後的數填入這個cell，變成確定數。程式執行時會不斷的重複找pattern的動作，直找無法再找到任何pattern為止。結果有二種，一種是全部解完，一種是卡關，需要加入更多pattern才能繼續。這是程式的基本運作概念。


Single

Single是唯一候選數的pattern，這個pattern有二種情況：

1. 顯式的(naked)：在這個情況下，這個候選數是這個cell裡唯一的一個候選數。
2. 隱式的(hidden)：這表示說，在這個cell裡面還有其它的候選數存在，但因為在這個cell所在的column或row或box裡面，這個候選數是唯一的，所以可以忽略其它候選數，填入這個唯一數。

如上圖，cell f2裡面只有一個候選數8，所以可以將8填入f2。

如上圖，在紅線框的這個box裡面，候選數5只存在cell c1裡面，所以可以將5填入c1。

Claiming

在一個row或column裡面，如果某一數的候選數都集中在同一個box裡面，則在這個box裡面在這個row或column以外的候選數都可以消除。

如上圖所示，候選數7在row9裡面都集中在box7裡，這表示說在box7裡面候選數7只可能出現在row9裡面，因此在box7裡面row9以外的候選數7都可以消除。

Pointing

這個技巧和Claiming類似，差別只在於Pointing是先由box的角度來看。如果在一個box裡面的某個候選數都集中在同一個row或column的話，則在這個row或column上的其它候選數都可以消除。

如上圖，在box7裡候選數3只存在row8裡面，也就是說在整個row8上面候選數3只可能出現在box7裡面，因此在row8上在box7以外的候選數3都可以被消除。

Set

Set(或Subset)是在找數字組合的pattern，Set的長度可以是2~4。長度為n的Set可以定義一組由這幾個數字構成的Subset，Subset的長度可以是2~n。

例：3及9二個數字構成的Set，長度為2，Subset只有一種39。

例：1，4及7三個數字構成的Set，長度為3，它的Subset可以是14、17、47及147。

Set可以是顯式及隱式二種。

對於顯式的Set，假如構成長度為n的Set的Subset只出現在n個不同的cell裡面的話，則其它cell裡面的Set候選數都可消除。如上圖所示為一個顯式的Set的例子。這是由5及7構成的Set，出現在box3裡的g2及i3 cell裡面。換句話說，5及7只可能出現在這二個cell裡面，因此其它的cell裡面的5或7都可以消除。

對於隱式的Set，假如構成長度為n的Set的Subset只出現在n個不同的cell裡面的話，則在這n個cell裡面的其它候選數都可以消除。如上圖是一個隱式Set的例子，在這個例子裡面2及8只出現在d4及f6二個cell裡面，因此構成了一個Set的pattern，所以除了2和8以外的數字都可以從d4及f6二個cell裡面消除，只留下2及8。

X Wings

若某個候選數同時出現在二個row和二個column上共4個cell裡面，並且這4個cell都處在不同的cell裡面。若其中二個row或二個column裡的這個候選數都是唯二的，那麼在對應的二個column或二個row裡面的這個候選數都可以被消除。

如上圖，在column e和column h都各有二個候選數5，並且這二對5也同時存在於row 2和row 5上，因此構成XWings pattern。

因為在column e上候選數5要嘛出現在e2要嘛出現在e5，在column h上候選數5要嘛出現在h2要嘛出現在h5。當5出現在e2時，h5必為5，e5及h2就不能為5(互斥)；當5出現在e5時，h2必為5，e2及h5就不能為5(互斥)。

無論5出現在那個地方，在row 2和row 5上其它地方也不可能出現5(也被排斥掉了)，所以column e和column h上以外的5都可以被消除。


Finned X Wings

這是XWings的變化型態，如下圖所示。

如果h3 != 4的話就構成上述的XWings pattern，那麼i2的4就可以被消除。如果在box3裡面h3=4的話，那麼i2就被排除不能為4。結合這二個pattern，不論那個情況發生，i2都不可能為4，所以可以把候選數4消除。


XY Wings

這是在找由XYZ三個數構成的XY / XZ / YZ的組合，分別存在三個不同的cell裡面，其中二個cell在同一row或同一column，並且其中二個cell必須在同一個box中。

如上圖所示，由245三個數構成的三個數對分別在e8 g9 h8三個cell裡，其中e8和h8在同一個row上，而g9和h8在同一個box裡面，所以構成XY Wings pattern。

現在來分析：如果h8=2的話，那麼g9=5；如果h8=4的話，那麼e8=5。無論那種情況發生，同時被這三個cell看到的5都會被排除。