數獨的程式設計法

以下摘自 阿丁之窟 網站內 數獨窟 (http://homepage19.seed.net.tw/web@5/ading/sudoku.html)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
◎數獨的程式設計

目前在網路上能看到的數獨遊戲，大致上可區分為四種程式設計方法，介紹如下：

第一種、亂來法
這是利用已經完整的一些數獨盤面(或稱數獨陣列)，以隨機的方式挑選出一個盤面，並利用數獨的特性加以隨機鏡射(左右、上下、對角或不鏡射)、旋轉(90、180、270度或不旋轉)、行與行對調(不破壞九宮關係的情況下)、列與列對調(不破壞九宮關係的情況下)，接著再以亂數產生的數字對應表(數字一對一)的方式替換盤面中的數字(如1變2、2變5、3變9、4變7、5變1、6變3、7變8、8變4、9變6 ) 等等；透過前列各種可能採用的方式來產生新的數獨盤面。

接著以很不負責的方式隨機拿掉盤面上的部分數字，然後以號稱是數獨題目的方式出現。而事實上大多是多解的數獨題目(喔，是不該稱為數獨題目)，所以這種程式方式簡直是來亂的；讓有心想體驗數獨的初學者遇到這種數獨程式，會信心大失而無法對數獨產生興趣。偏偏網路上這種 亂來法程式屢見不鮮....

第二種、題庫法
這是利用已經建好的大量數獨題目，以隨機的方式挑選出一個題目，並利用數獨的特性加以隨機鏡射(左右、上下、對角或不鏡射)、旋轉(90、180、270度或不旋轉)、行與行對調(不破壞九宮關係的情況下)、列與列對調(不破壞九宮關係的情況下)，接著再以亂數產生的數字對應表(數字一對一)的方式替換題目中的數字(如1變2、2變5、3變9、4變7、5變1、6變3、7變8、8變4、9變6 ) 等等；透過前列各種可能採用的方式來產生新的數獨題目。

這種數獨題目是以既成的數獨題目演化而來，所以若當初是唯一解，那所得題目也將是唯一解。這種方式的特點是出題速度快，缺點是要蒐集大量的數獨題目來建立題庫來豐富數獨題目的變化性。而這種題庫法也是市面上的數獨機所慣用的方法。

第三種、挖洞法
這是利用已經完整的一些數獨盤面(或稱數獨陣列)，以隨機的方式挑選出一個盤面，並利用數獨的特性加以隨機鏡射(左右、上下、對角或不鏡射)、旋轉(90、180、270度或不旋轉)、行與行對調(不破壞九宮關係的情況下)、列與列對調(不破壞九宮關係的情況下)，接著再以亂數產生的數字對應表(數字一對一)的方式替換盤面中的數字(如1變2、2變5、3變9、4變7、5變1、6變3、7變8、8變4、9變6 ) 等等；透過前列各種可能採用的方式來產生新的數獨盤面。

接著先準備好一個解數獨的程式，該程式需可以驗證所得的解是否為唯一。然後透過挖洞程式從先前產生的數獨盤面隨機或特定移除(挖掉)某些位置(為了對應性)上的數字，之後再以解數獨程式去驗證是否為唯一解，若『是』的話則繼續挖並反覆驗證唯一解，若為『否』的話則將挖除的數字填回後改挖其他的地方。當沒地方可挖或不想挖時，無論如何起碼目前所呈現的都是經過驗證後有唯一解的數獨題目了。

以上就要看解數獨程式的功力了，解的快出題也就快，解的好也能分析解題過程中用了哪些解題技巧(什麼xx刪減法、xx摒除法的，算了~我沒認真去記過那些，只想玩數獨而已又何必記些有的沒的名詞；但不可諱言的有那些名詞的出現倒是能增進數獨的交流與相關討論。)，而以不同的解題技巧使用數量去評分來評斷這數獨題目的難易度。

目前在網路上看到的唯一解數獨大多是使用挖洞法，因為出題方式簡單，只差在解數獨程式的功力。而在台灣最富盛名的則是尤怪大師的『數獨樂園』網站與『數獨大師』軟體，即是使用挖洞法來產生題目的。而現在挖洞法還演化出『題型法』的方式，就是以某些固定挖洞的題型來確保能將任何數獨盤面都能挖出成唯一解的數獨題目；所以『題型法』只是挖洞法的演化，特點是出題最為迅速。

第四種、填入法
填入法與前面三種方法截然不同，是種「無中生有」的功夫。較像手工數獨出題般，只是改由程式去完成出題的任務。整個理念也很簡單，就是程式在隨機的位置(或加上相對應的位置)去填入可以填的數字(由『候選字』中隨機或特定選出，以9x9的數獨而言剛開始每個位置上的候選字都是1~9)，而相對的同行、同列與同宮的候選字中則剔除該數字，若候選字數量只剩唯一則表示為該位置的唯一解。但若候選字的數量為0，則表示出題任務失敗，看是要退回之前的動作或重新來過。幸好累的是電腦程式而不是人，所以感覺上出題的速度就會慢很多。

不過，也有解決出題慢的方法就是在程式中增加刪除部分候選字的智慧，也就是能推測出候選字中哪些是多餘的就先予以剔除掉，這樣能避免出題時的錯誤使用，並能降低出題時的失敗率。所以當賦予程式的智慧最高時失敗的機率則將為0%，同樣出題的速度也就相當迅速了。當然，這種方式所得到的數獨題目也將是唯一解。

或許是較少人想挑戰這種智慧型的出題程式設計，或許也有人寫了但因為程式智慧不足而出題速度慢的可以，最後放棄這種方式而改用簡單的挖洞法。所以這種『填入法』的數獨題目在網路上較為罕見，能見到算是運氣不錯(就像看到幸運草一般)，也就像發現這個『數獨窟』一樣，這個數獨窟(Sudoku)即是以『填入法』來產生數獨題目的喔。事實上你也可以自己試試看『填入法』的出題樂趣，我以9x9的標準數獨出題方式來說明一下：可在數獨窟的程式中選取 9x9 的陣列大小，並選取『標準』後按下【設計與解題】的按鈕，接著就可以選取某位置上的候選字來觀察其它位置候選字的變化情形，然後繼續出題最後就能出完一題唯一解的數獨題目囉。


(end)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
阿丁之窟 網址 : http://homepage.seed.net.tw/web/ading