發表文章

目前顯示的是 1月, 2013的文章

HTML5 Kill Sudoku

圖片
花了二晚將前次發表的 KillSudoku 移植成Web版,這次利用HTML5的繪圖功能取代掉原來簡單的文字模式顯示,改良成更好的圖形顯示。 這個版本實作了簡單的編輯功能,可以很容易的輸入或創造謎題(滑鼠左鍵輸入再點一下取消輸入)。不過目前還沒有實作檢查輸入的題目是否有唯一解,所以如果嘗試去解沒有唯一解的題目時可能有會不可預期的結果。 這次增加了一個新的Pattern:XYZ Wings,不過現在懶的介紹了~ 目前只在Chrome及Safari上試過。 ( 試試看 )

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個數字,由左至右,由上而下,一列一列的由上往下輸入。每一個數字範