:::

[日記]數獨消去猜測法

11月 23, 2006 0 Comments Edit Copy Download

開新視窗連結 以JavaScript撰寫,用消去法與猜測法搭配回溯法進行運算數獨解答計算程式,是以前用n-Queen演算法的程式進階版本。

請幫忙找找可以考倒他的題目吧,SUDOKU 數獨 Online 這個網站的hard++可是非常的難喔!

虛擬碼:

  1. 初始化:
    1. 畫好表格,從[0][0]到[8][8],第一維為x軸,第二維為y軸,每格都有已檢查標籤,預設值為false
    2. 宣告紀錄堆疊
    3. 填好題目
    4. 將空格的值填入123456789
    5. 如果全部都是空格,表示沒有題目,把[0][0]設為1表示題目
  2. 消去法:
    找到可能數字最少的一格,而且不能為9個全滿
    1. 如果有,設該格可能數字數量為n
      1. 檢查同x軸、同y軸、同九宮格的數值當中,是否有n個與該格的值同樣的格子(已確定數字)
        1. 如果有,那其他格就刪去那些值
        2. 如果被刪去值的格子可能數字的數量有受到影響,則取消已檢查標籤
        3. 在進行刪去動作中,如果有格子被刪掉沒有可能數字了,則進行回溯法(4)
      2. 該格設定已檢查標籤
      3. 進行消去法(2)
    2. 如果沒有
      1. 進行猜測法(3)
  3. 猜測法:
    1. 找到
      1. 沒有已檢查標籤,且可能數字數量為1的一格
      2. 可能數字最少且大於2的一格
    2. 將目前的陣列儲存進記錄堆疊中,也記錄找到的那格的座標
    3. 猜這格的第一個數字為該格的答案
    4. 取消該格的已檢查標籤
    5. 進行消去法(2)
  4. 回溯法:
    1. 用紀錄堆疊將陣列恢復到上一個儲存時的狀況
    2. 將當時儲存時的該格的第一個數字刪去
      1. 如果刪完還有可能數字
        1. 取消該格的已檢查標籤
        2. 進行消去法(2)
      2. 如果刪完沒有可能數字了
        1. 進行回溯法(4),再回溯到前一個陣列的狀況

講完了,這並不是很標準的虛擬碼,只是概要說明而已。

就如你所看到的,基本的作法就是用已確定的數字把其他可能數字刪掉。如果已經沒有已確定數字了,再來猜測。如果猜錯了,那就回溯,就這麼單純。

這個程式我加了很多額外花俏的東西,包括你在網頁上看到的所有視覺效果。雖然可以直接從網頁上看到JavaScript的原始碼,不過應該會被這些花俏的功能弄很混亂。


接下來說說心得吧...

今天花了一整天的時間寫這個程式,很難得地寫到想吐。JavaScript在程式語言裡面算是結構很鬆散、非常自由的一種,所以只要一把程式寫大,就會有很多問題發生。今天最常遇到的是:

  1. 陣列前面不可以用變數宣告 var
  2. 要使用陣列前,必須要先new Array
  3. 函式裡面的變數要加var,以免變成全域變數影響其他函式進行
  4. split()切割時,會保留原本的切割字元

光是這些問題,要一一設檢查點alert()來檢查,就做到想吐。不過最後還是給我做出來了,JavaScript的程式能力又升了一級。

這個程式會隨著計算時間增加,程式給電腦的負擔也會越來越重,看你電腦等級到什麼程度。那個時間設定擺著很心酸,因為這程式額外的動作很多,所以很難10毫秒就可以計算一次。我的筆電算到500次計算以上,速度就會降到1秒計算一次,算到1000次以上更是讓人看了想睡覺,連打字都很吃力。不過還好,可以把停止執行打勾,電腦就會恢復正常。

這個程式目前解過最高的計算次數為1349次,題目為SUDOKU 數獨Online的#5264。雖然會為程式連這麼難的計算都算得出來而感到開心,可是就如朋友所說的,一個數獨要猜就不好玩了,這種要猜超過50次才猜得到正解的數獨根本就是給電腦算的,真不有趣,看來這是題目設計上的問題啦。老實說,我用手算過的數獨才只有三題,這是典型的遇到問題就用電腦解決的逃避行為啊。

這個解答演算法的猜測法還有待改進,可以先從影響其他格可能數字最多的那格開始猜起,不過這個計算不像人可以用眼睛看的那樣輕鬆,尤其是在JavaScript這個低效率程式上更是如此。如果能搭配資料庫強大的運算能力,那麼實作上就比較有可能了。

完成了這個程式,不過其實並沒有什麼成就感,大概是因為debug的挫折太讓人吐血了,所以一點也開心不起來。另外一個晚上都看著那個數字一直跑,越看越頭昏,使用的時候請小心啊。

對了,有人可能會問我說,為什麼要寫這個程式?其實這個演算法是很早以前就想好的,只是一直沒有時間實作。趁今天空檔,趕快把腦海中的想法寫出來。既不是作業,也不是賺錢的CASE,也沒有要幫誰作,只是單純地想寫出來。後來才想到既然我要推甄的話,那麼這個作品應該也可以幫點忙吧。

今天是寫數獨的解答程式,改天來等數獨題目看多了之後,抓到出題的訣竅之後,我也來做做看數獨的出題程式好了。