:::

[作品]數獨sudoku解答計算器

5月 13, 2006 44 Comments Edit Post

數獨sudoku,在每一個小九宮格中,分別填上1至9的數字,讓整個大九宮格每一列、每一行的數字都不重複。

這個程式的使用方法是:

  1. 先填入題目
  2. 按下「開始計算」
  3. 等待計算完畢,你可以看到計算的過程喔!
  4. 解答出來囉

不管怎麼說,來玩玩看吧!這邊也提供一個從報紙上抄下來的範例作為題目,按下「範例1」就會自動填入喔!

這個演算法是很基礎的N-QUEEN回溯法,計算方式如下

  1. 從第一格開始判斷,方向為前進
  2. 將該格數字+1並模數10,進行檢查是否符合規則
  3. 檢查通過,跳下一格,方向為前進
  4. 如果數字為0(即10 mod 10),則代表所有可能都計算過,這格沒有可能解,必須退回檢查上一格
  5. 如果該格為題目,則跳下一格(方向為前進)或上一格(方向為後退)

詳細演算法可以自行查詢本網頁的原始碼當中JavaScript的sudoku這個函式。

不過,這個演算法只能說是基礎,還有更好的作法:先列出每一格當中的可能數字,先從擁有最少可能的數字開始進行運算測試,再做下一個,這樣不斷地到所有格子都完成。這跟基礎演算法關鍵性的不同是:進階演算法是利用最可能取得答案的那格開始計算,基礎演算法只是很笨地從第一格開始計算而已。這個程式撰寫時,我也已經留好寫入進階演算法的空間,改天會把它完成吧。

接下來閒聊一下。

數獨sudoku(数獨‧看發音儼然是日文),這玩意兒不知為何在各個場所流行起來了。不僅班上同學特地買了書來玩,連各大報紙每天都有不同的數獨題目。在這個9*9的小空間裡面,數獨的變化可說是變化無窮。

我個人對這種東西就有點不行了,比起花時間向機器般地推敲這個遊戲,我可能比較喜歡玩東方永夜抄訓練手指(汗)。

話說回來,最近演算法上到回溯,可說是越聽越不懂啦。之前的演算法,大部分我都可以直接轉換成程式語言來實作。可是這個回溯的道理雖然簡單,但是要實作起來可就麻煩了。

昨晚吃晚餐的時候,隨意拿起了身邊的報紙來看,又是數獨。之前我就有想過要來寫個簡單的小程式來解數獨了,吃飯的時候跟隆基討論了一下演算法,然後就上機實作當作飯後消化吧。最後是花了三個多小時完成了,之間發生很多無所謂的Bug就不說了,總之完成的那種感覺很爽。

趁月圓的時候,買罐飲料向月亮舉杯,慶賀一下吧XD。


總共44 則留言, (我要發問)

  1. 問題發現:回溯到第一格的時候,會造成判斷錯誤。也就是如果第一格第一次判斷失誤的話,那就沒辦法判斷第二次了。

    回覆刪除
  2. 同样对数独比较感兴趣,在做一个数独的project,比较不同的数独推算法的解题能力,进而比较不同算法的优劣
    想引入的是:人解数独的时候有逻辑的推理,就想你说的第二种方法,不仅仅是简单的简化版,有很多推理的结果是建立在推理的基础上的,这是目前的程序做不到的,如何改进在进一步的逻辑推理呢?
    ps: 个人还在找最难和最简化的数独,目前已知的最少的数独是17个已知数字

    回覆刪除
  3. 不好!我尝试着算一个数独,算了93032次,最后告诉我无法计算!晕!

    回覆刪除
  4. 可以把題目寫給出來,讓我改良看看嗎?

    回覆刪除
  5. 我的题目算了101224次,也是无法计算,!

    回覆刪除
  6. 唉呀,畢竟只是隨手寫寫的程式,不可能盡善盡美啦
    可以把題目貼給我參考看看嗎?

    回覆刪除
  7. 可能题目本身就错误,我做过N个了,没出过问题,这个运算器还是比较好的,应该没有不能破的题,除非题就有错

    回覆刪除
  8. 喔喔,也許是這樣沒錯喔
    不過我還是想看看題目確認一下,如果可以的話請POST上來借我研究研究吧!

    回覆刪除
  9. 呵,我几乎每天都在做,我做了个超大型程式...哈哈这算算半天啊

    回覆刪除
  10. 16格的,有兴趣可以问我要了拿去做做看哦

    回覆刪除
  11. 哈哈,我发现了,有个程式这个计算器说不能算,哈哈...但我自己算倒算的出来
    -3-1-26--
    1----7389
    56--8----
    --3--6--8
    4-679---3
    -8-2---56
    3-18-5967
    --593---2
    -9-------

    回覆刪除
  12. 测试后才知道,可能因为第一排数字排列的运算几率可能性太小,且由高到低,运算时的排序方法编程需改进.

    回覆刪除
  13. ...我是上面那个匿名的...什么高手吖...

    回覆刪除
  14. -1---3--7
    -3--8--46
    --7---2--
    6--8-1---
    -8---3-5-
    ---4-7--9
    --6---5--
    57--2--9-
    ---1---7-


    好了..這題目也無法計算。

    回覆刪除
  15. -3-1-26--
    1----7389
    56--8----
    --3--6--8
    4-679---3
    -8-2---56
    3-18-5967
    --593---2
    -9-------
    有三个解:
    9 3 8 1 4 2 6 7 5
    1 2 4 5 6 7 3 8 9
    5 6 7 3 8 9 1 2 4
    2 1 3 4 5 6 7 9 8
    4 5 6 7 9 8 2 1 3
    7 8 9 2 1 3 4 5 6
    3 4 1 8 2 5 9 6 7
    6 7 5 9 3 1 8 4 2
    8 9 2 6 7 4 5 3 1

    9 3 8 1 4 2 6 7 5
    1 2 4 5 6 7 3 8 9
    5 6 7 3 8 9 2 1 4
    2 1 3 4 5 6 7 9 8
    4 5 6 7 9 8 1 2 3
    7 8 9 2 1 3 4 5 6
    3 4 1 8 2 5 9 6 7
    6 7 5 9 3 1 8 4 2
    8 9 2 6 7 4 5 3 1

    9 3 8 1 4 2 6 7 5
    1 2 4 5 6 7 3 8 9
    5 6 7 3 8 9 2 4 1
    2 1 3 4 5 6 7 9 8
    4 5 6 7 9 8 1 2 3
    7 8 9 2 1 3 4 5 6
    3 4 1 8 2 5 9 6 7
    6 7 5 9 3 4 8 1 2
    8 9 2 6 7 1 5 3 4


    -1---3--7
    -3--8--46
    --7---2--
    6--8-1---
    -8---3-5-
    ---4-7--9
    --6---5--
    57--2--9-
    ---1---7-
    题目错误,无解

    回覆刪除
  16. 我的題目也有算不出來的

    回覆刪除
  17. 有題目跟解答讓我方便偵錯嗎?

    回覆刪除
  18. 以我的經驗,台灣某一些出版社的數獨書是亂出題目騙錢的,題目根本不能解出答案,要不然就是一題多個解答,如果用這類題目測試解答計算器,當然是會失望的.我用一些正確題目測試的結果,解答計算器都能跑出唯一且正確的解答.

    回覆刪除
  19. 好,修正了之前一直就有的bug。

    匿名講到的題目,我把它做成範例2的按鈕,而現在也能夠正常地運算啦。
    它會算出匿名講到的三個解答中的第一個。

    雖然感謝Thomas Ti幫我護航,可是之前的確是有bug。
    現在修正了,歡迎大家再來挑戰。

    沒想到這個大學時在演算法課堂中無聊實作的一支小程式,到現在都還有人在使用
    真是讓人感到欣慰

    有問題歡迎提出喔!

    回覆刪除
  20. 4x4的數獨有人 會嗎?????
    (1~16)
    如有發現,請相告,急需~~~>_<

    謝謝!!!!!!!!!

    回覆刪除
  21. 這還真的是相當特別的要求呢。
    我並不會解4x4數獨,不過程式修改一下邏輯的話,應該就能夠做到。

    我比較好奇的是,為什麼會需要解4x4數獨呢?

    回覆刪除
  22. 因為我要考奧林匹亞

    回覆刪除
  23. 嗯……那你要的應該是解4x4數獨的方法,而不是程式或人?

    是說,不能用解3x3的方法去解4x4嗎?

    回覆刪除
  24. 验证次数:495276

    回覆刪除
  25. To 28樓的匿名:

    似乎是很難的題目呢,最後有解答出來嗎?

    回覆刪除
  26. ---8-9---
    5-----71-
    --2--3---
    -1--2----
    ------4--
    -3---85-9
    -54------
    --1---2--
    ---9-2---
    誰能給我正解

    回覆刪除
  27. To 30樓匿名:

    從http://www.shudu.net/jieti.php取得的解答:
    【答案】shudu.net
    7 4 3 8 1 9 6 2 5
    5 8 9 2 6 4 7 1 3
    1 6 2 5 7 3 8 9 4

    9 1 6 7 2 5 4 3 8
    8 2 7 3 4 1 5 6 9
    4 3 5 6 9 8 1 7 2

    2 5 4 1 3 6 9 8 7
    3 9 1 4 8 7 2 5 6
    6 7 8 9 5 2 3 4 1

    回覆刪除
  28. To 30樓匿名:

    至於這個網頁的算法算出來之後的答案是:

    1 4 3 8 7 9 6 5 2
    5 8 9 2 4 6 7 1 3
    6 7 2 1 5 3 8 9 4
    9 1 5 4 2 7 3 6 8
    8 2 6 3 9 5 4 7 1
    4 3 7 6 1 8 5 2 9
    2 5 4 7 8 1 9 3 6
    3 9 1 5 6 4 2 8 7
    7 6 8 9 3 2 1 4 5

    驗證次數:1304115
    計算時間大概花了一個多小時XDDD

    畢竟這只是基本的算法,「能算得出答案就好」的程度,只有這種效率也不讓人覺得意外。
    我是有改善演算法的方案,文中也有提到,只是一直沒有機會去完成它就是XDD

    有人會期待我做出改善後的演算法嗎?
    雖然現在已經有很多網站都有數獨解答器的功能了耶?

    回覆刪除
  29. 謝謝原作者。

    老二考完期末,從學校拿回來個課外作業就是個數獨。自己和老大搞了很久都搞不出來,最後用這個工具算出來了,7萬多次搞定。

    有興趣大家可以試試,原題為:
    --- 2-- -3-
    7-- -1- 5--
    -1- --4 2--

    --3 --5 -4-
    9-- -6- --1
    -6- 3-1 8--

    --9 7-- -1-
    --4 -3- --5
    -3- --2 ---

    由於1和3出現較多,可以推出,簡化後為:
    --- 2-- 13-
    7-- -13 5--
    31- --4 2--

    1-3 --5 -4-
    9-- -6- 3-1
    -6- 3-1 8--

    --9 7-- -13
    --4 13- --5
    -31 --2 ---

    這個算了7萬多次就搞定

    回覆刪除
  30. To 33樓匿名,

    感謝提供了一個相當有挑戰性的題目
    我只是有點意外到現在這個工具還如此受人歡迎XD

    回覆刪除
  31. http://blog.yam.com/ewestein/article/16409663

    回覆刪除
  32. To 38樓的匿名先生:

    我本來以為這是廣告連結,結果打開之後卻是另一個數獨解答器

    不過邏輯上似乎還有待加強,畢竟是物件導向的時代了,把包很多層的迴圈拆成多個方法,會讓人比較容易理解。

    然而這解答器跟我的作法差不多,都是n-queen的遞迴策略
    我後來想過,更好的作法是從最少可能性的格子去猜解答,這樣效率會更高
    不過那也是好幾年前的事情了,後來就做其他事情沒去解。

    反正寫數獨解答的人這麼多,也不差我一個啦XD
    還是寫些其他大家沒寫過的程式比較好。

    回覆刪除
  33. http://www.sudokuwiki.org/sudoku.htm 這個網頁把各種方式都掛在上面,還可以看一步一步的處理方式。感想:很強大...

    回覆刪除
  34. 可以下載下來嗎

    回覆刪除
  35. ​To 39樓匿名,

    你可以直接下載這個網頁來使用
    例如用Google Chrome的「另存網頁為...」下載,下載位置如下圖所示:
    https://lh5.googleusercontent.com/-AbsgXGiNopo/U8E-THF72tI/AAAAAAABeM4/ReViaST-fPk/s0/2014-07-12_21-55-23.png

    建議可以用MHT格式來儲存
    http://www.ubuntu-tw.org/modules/newbb/viewtopic.php?post_id=235354

    回覆刪除
  36. To 41樓匿名:

    請告訴我你的題目,以及如果有的話的正確解答,謝謝

    回覆刪除
  37. 感謝布丁布丁吃什麼,我用這個超好用的程式解了兩道五星的一個解了2400多次,一個解了將近30000多次的終於解完了。。。感謝感謝

    回覆刪除