[日記]數獨消去猜測法
開新視窗連結 以JavaScript撰寫，用消去法與猜測法搭配回溯法進行運算數獨解答計算程式，是以前用n-Queen演算法的程式進階版本。
請幫忙找找可以考倒他的題目吧，SUDOKU 數獨 Online 這個網站的hard++可是非常的難喔！
虛擬碼：
- 初始化：
- 畫好表格，從[0][0]到[8][8]，第一維為x軸，第二維為y軸，每格都有已檢查標籤，預設值為false
- 宣告紀錄堆疊
- 填好題目
- 將空格的值填入123456789
- 如果全部都是空格，表示沒有題目，把[0][0]設為1表示題目
- 消去法：
找到可能數字最少的一格，而且不能為9個全滿- 如果有，設該格可能數字數量為n
- 檢查同x軸、同y軸、同九宮格的數值當中，是否有n個與該格的值同樣的格子(已確定數字)
- 如果有，那其他格就刪去那些值
- 如果被刪去值的格子可能數字的數量有受到影響，則取消已檢查標籤
- 在進行刪去動作中，如果有格子被刪掉沒有可能數字了，則進行回溯法(4)
- 該格設定已檢查標籤
- 進行消去法(2)
- 檢查同x軸、同y軸、同九宮格的數值當中，是否有n個與該格的值同樣的格子(已確定數字)
- 如果沒有
- 進行猜測法(3)
- 如果有，設該格可能數字數量為n
- 猜測法：
- 找到
- 沒有已檢查標籤，且可能數字數量為1的一格
- 可能數字最少且大於2的一格
- 將目前的陣列儲存進記錄堆疊中，也記錄找到的那格的座標
- 猜這格的第一個數字為該格的答案
- 取消該格的已檢查標籤
- 進行消去法(2)
- 找到
- 回溯法：
- 用紀錄堆疊將陣列恢復到上一個儲存時的狀況
- 將當時儲存時的該格的第一個數字刪去
- 如果刪完還有可能數字
- 取消該格的已檢查標籤
- 進行消去法(2)
- 如果刪完沒有可能數字了
- 進行回溯法(4)，再回溯到前一個陣列的狀況
- 如果刪完還有可能數字
講完了，這並不是很標準的虛擬碼，只是概要說明而已。
就如你所看到的，基本的作法就是用已確定的數字把其他可能數字刪掉。如果已經沒有已確定數字了，再來猜測。如果猜錯了，那就回溯，就這麼單純。
這個程式我加了很多額外花俏的東西，包括你在網頁上看到的所有視覺效果。雖然可以直接從網頁上看到JavaScript的原始碼，不過應該會被這些花俏的功能弄很混亂。
接下來說說心得吧...
今天花了一整天的時間寫這個程式，很難得地寫到想吐。JavaScript在程式語言裡面算是結構很鬆散、非常自由的一種，所以只要一把程式寫大，就會有很多問題發生。今天最常遇到的是：
- 陣列前面不可以用變數宣告 var
- 要使用陣列前，必須要先new Array
- 函式裡面的變數要加var，以免變成全域變數影響其他函式進行
- split()切割時，會保留原本的切割字元
光是這些問題，要一一設檢查點alert()來檢查，就做到想吐。不過最後還是給我做出來了，JavaScript的程式能力又升了一級。
這個程式會隨著計算時間增加，程式給電腦的負擔也會越來越重，看你電腦等級到什麼程度。那個時間設定擺著很心酸，因為這程式額外的動作很多，所以很難10毫秒就可以計算一次。我的筆電算到500次計算以上，速度就會降到1秒計算一次，算到1000次以上更是讓人看了想睡覺，連打字都很吃力。不過還好，可以把停止執行打勾，電腦就會恢復正常。
這個程式目前解過最高的計算次數為1349次，題目為SUDOKU 數獨Online的#5264。雖然會為程式連這麼難的計算都算得出來而感到開心，可是就如朋友所說的，一個數獨要猜就不好玩了，這種要猜超過50次才猜得到正解的數獨根本就是給電腦算的，真不有趣，看來這是題目設計上的問題啦。老實說，我用手算過的數獨才只有三題，這是典型的遇到問題就用電腦解決的逃避行為啊。
這個解答演算法的猜測法還有待改進，可以先從影響其他格可能數字最多的那格開始猜起，不過這個計算不像人可以用眼睛看的那樣輕鬆，尤其是在JavaScript這個低效率程式上更是如此。如果能搭配資料庫強大的運算能力，那麼實作上就比較有可能了。
完成了這個程式，不過其實並沒有什麼成就感，大概是因為debug的挫折太讓人吐血了，所以一點也開心不起來。另外一個晚上都看著那個數字一直跑，越看越頭昏，使用的時候請小心啊。
對了，有人可能會問我說，為什麼要寫這個程式？其實這個演算法是很早以前就想好的，只是一直沒有時間實作。趁今天空檔，趕快把腦海中的想法寫出來。既不是作業，也不是賺錢的CASE，也沒有要幫誰作，只是單純地想寫出來。後來才想到既然我要推甄的話，那麼這個作品應該也可以幫點忙吧。
今天是寫數獨的解答程式，改天來等數獨題目看多了之後，抓到出題的訣竅之後，我也來做做看數獨的出題程式好了。
