數獨的程式設計法

以下摘自 阿丁之窟 網站內 數獨窟 (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

『腦殘搶救班』 襲捲而來!! 喜悅的享樂~~

很高興筆者前一篇【新一代閱讀享樂 繪動本悄悄問市】中所介紹的『奇豆線上書房』(http://www.kiddobook.com/) 入圍了2008年數位金鼎獎的「最佳電子書」獎項，雖然最後沒有得獎；但是，入圍即是一種肯定！所以還是恭喜『奇豆線上書房』。當然，這也正是筆者眼光的執著--不是好東西就絕對不會推薦，所以能在這裡上檯面的，絕屬佳品！

不過，筆者文章的標題喜歡下的與眾不同，誠如之前的『繪動本』一樣，感覺『奇豆線上書房』似乎打死也不願意使用。而更別說今天要介紹這個網站 http://homepage.seed.net.tw/web/ading/ ，我想站長更是打死也不願用『腦殘搶救班』來命名，搞不好還想打死我也說不一定。或許向來不會有人自認腦殘而需要自我搶救或被搶救，所以若取這個名稱會阻礙「正常人」進到這個網站，但是我有不同的見解--或許站長同我都叫『阿丁』，自然而然就會想到『丁丁』--傳說中的人才！腦殘中的代表！腦殘絕非壞事，腦殘意味著...呃，將會有更多的成長空間！！

這讓我想到一件事--無關的事，補習界的『台大搶救班』跟『台大保證班』，似乎意味著同一件事--讓補習的學生能進台大為目標，無論是真的考進台大或是得重症進台大，起碼『搶救』跟『保證』似乎是相當的。好了，那將『腦殘搶救班』改成『腦殘保證班』來試試看吧？哈～ 那換成較低俗(低齡又通俗)的說詞--『益智』，這樣可以接受了吧？自從【數獨】遊戲的盛行，社會上興起了一股益智風(對了，今天這個網站也有【數獨】喔！)，為的是啥？

你知道人的大腦使用率有多少嗎？據研究一般人是連10%都不到，也就是說有90%以上的腦是殘餘的，你的大腦又殘餘了多少？如何好好的能運用到那些未被使用到的腦細胞？如何讓自己更能開竅？請加入『腦殘搶救班』或『腦殘運用保證班』，將使你的人生更豐富更精彩！！所以，腦殘絕非壞事，體認腦殘、運用腦殘，這才是王道(不敢正視自己腦殘的，才是可憐蟲)。或許，有朝一日站長會感謝我幫他想出這個名稱(『腦殘搶救班』)的。

好了，介紹一下這個我稱之為『腦殘搶救班』的網站 (http://homepage.seed.net.tw/web/ading/ )，它裡面還在陸陸續續的添增一些免費的線上遊戲，截至今日目前為止有四個遊戲，都可以搶救腦殘！！但是要注意的是--這網站是使用Microsoft最新的Silverlight 2的技術，所以你的瀏覽器要加掛Silverlight 2，這有點像加掛Flash player一樣，反正遲早都要安裝的，若還沒安裝過Silverlight 2的，就趁現在就裝一裝吧!! 早裝早享樂~~

(1) 球球連連消

搶救腦殘-- 靈活度

這幾乎和以前流行的Color Linez一樣，只要有五顆相同顏色的球連成一直線(橫直斜皆可)就會將球消失得分。
不過，這遊戲多了半透明的彩色球(姑且稱為魔力球)，這魔力球可以取代所有顏色的球喔，魔力球取得的方式是透過求救(有三次球舊的機會)還有當分數累積到某些程度就會自動出現。有魔力球後讓遊戲更加有趣好玩。

(2) 色彩對對碰

搶救腦殘-- 敏銳度

這也跟以前流行的遊戲相似，不過這個似乎較難，因為它考驗著視覺的敏銳度。剛開始玩總覺得有些顏色都差不多，很難分辨；可是玩久了就會發覺自己眼睛能辨識的色階居然提升了，我原本以為我家浴室是貼白色磁磚，後來發現是有帶粉紅細紋的粉白色磁磚，感覺這世界多添了許多的色彩喔。蠻奇特的感受！

(3) 數區(Shikaku)

搶救腦殘-- 空間感

沒想到這遊戲從6x5到40x34的大小都有，可隨高興玩不同盤面大小的。這遊戲是找出盤面上數字所代表的矩形，直接用滑鼠去框起來即可，每個盤面都只有唯一的解答；所以這也是考驗推理能力。
相當不確的遊戲喔，可以讓小朋友從簡單的盤面開始，潛移默化的學加法與乘法喔。

(4) 數獨窟(Sudoku)

搶救腦殘-- 邏輯力

這是我所見過最棒的線上版數獨了！不是蓋的，操作容易--直接點數字即可，甚至還能用滑鼠右鍵來註記(方便推理)。而且有6x6、8x8、9x9和12x12四種大小，也各都包含有標準數獨(Sudoku)、X數獨(X-Sudoku) 與 外加底色數獨(More Sudoku) 還有 拼圖數獨(Jigsaw Sudoku) 四種遊戲型態，所以可以玩的花樣很多。
可自訂想玩的難易程度，題題都不相同，也都僅有唯一的解答喔。

詳細的遊戲說明在網站上都有，或者也可以在遊戲中將滑鼠移到左上角遊戲名稱的位置，也會出現遊戲說明喔。
好了, 要搶救腦殘, 就從現在開始吧!!! http://homepage.seed.net.tw/web/ading/