[作品]數獨sudoku解答計算器
數獨sudoku，在每一個小九宮格中，分別填上1至9的數字，讓整個大九宮格每一列、每一行的數字都不重複。
這個程式的使用方法是：
- 先填入題目
- 按下「開始計算」
- 等待計算完畢，你可以看到計算的過程喔！
- 解答出來囉
不管怎麼說，來玩玩看吧！這邊也提供一個從報紙上抄下來的範例作為題目，按下「範例1」就會自動填入喔！
這個演算法是很基礎的N-QUEEN回溯法，計算方式如下
- 從第一格開始判斷，方向為前進
- 將該格數字+1並模數10，進行檢查是否符合規則
- 檢查通過，跳下一格，方向為前進
- 如果數字為0(即10 mod 10)，則代表所有可能都計算過，這格沒有可能解，必須退回檢查上一格
- 如果該格為題目，則跳下一格(方向為前進)或上一格(方向為後退)
詳細演算法可以自行查詢本網頁的原始碼當中JavaScript的sudoku這個函式。
不過，這個演算法只能說是基礎，還有更好的作法：先列出每一格當中的可能數字，先從擁有最少可能的數字開始進行運算測試，再做下一個，這樣不斷地到所有格子都完成。這跟基礎演算法關鍵性的不同是：進階演算法是利用最可能取得答案的那格開始計算，基礎演算法只是很笨地從第一格開始計算而已。這個程式撰寫時，我也已經留好寫入進階演算法的空間，改天會把它完成吧。
接下來閒聊一下。
數獨sudoku(数獨‧看發音儼然是日文)，這玩意兒不知為何在各個場所流行起來了。不僅班上同學特地買了書來玩，連各大報紙每天都有不同的數獨題目。在這個9*9的小空間裡面，數獨的變化可說是變化無窮。
我個人對這種東西就有點不行了，比起花時間向機器般地推敲這個遊戲，我可能比較喜歡玩東方永夜抄訓練手指(汗)。
話說回來，最近演算法上到回溯，可說是越聽越不懂啦。之前的演算法，大部分我都可以直接轉換成程式語言來實作。可是這個回溯的道理雖然簡單，但是要實作起來可就麻煩了。
昨晚吃晚餐的時候，隨意拿起了身邊的報紙來看，又是數獨。之前我就有想過要來寫個簡單的小程式來解數獨了，吃飯的時候跟隆基討論了一下演算法，然後就上機實作當作飯後消化吧。最後是花了三個多小時完成了，之間發生很多無所謂的Bug就不說了，總之完成的那種感覺很爽。
趁月圓的時候，買罐飲料向月亮舉杯，慶賀一下吧XD。
問題發現：回溯到第一格的時候，會造成判斷錯誤。也就是如果第一格第一次判斷失誤的話，那就沒辦法判斷第二次了。
回覆刪除同样对数独比较感兴趣，在做一个数独的project，比较不同的数独推算法的解题能力，进而比较不同算法的优劣
回覆刪除想引入的是：人解数独的时候有逻辑的推理，就想你说的第二种方法，不仅仅是简单的简化版，有很多推理的结果是建立在推理的基础上的，这是目前的程序做不到的，如何改进在进一步的逻辑推理呢？
ps: 个人还在找最难和最简化的数独，目前已知的最少的数独是17个已知数字
不好!我尝试着算一个数独,算了93032次,最后告诉我无法计算!晕!
回覆刪除可以把題目寫給出來，讓我改良看看嗎？
回覆刪除我的题目算了101224次,也是无法计算,!
回覆刪除唉呀，畢竟只是隨手寫寫的程式，不可能盡善盡美啦
回覆刪除可以把題目貼給我參考看看嗎？
可能题目本身就错误,我做过N个了,没出过问题,这个运算器还是比较好的,应该没有不能破的题,除非题就有错
回覆刪除喔喔，也許是這樣沒錯喔
回覆刪除不過我還是想看看題目確認一下，如果可以的話請POST上來借我研究研究吧！
呵,我几乎每天都在做,我做了个超大型程式...哈哈这算算半天啊
回覆刪除16格的,有兴趣可以问我要了拿去做做看哦
回覆刪除哈哈,我发现了,有个程式这个计算器说不能算,哈哈...但我自己算倒算的出来
回覆刪除-3-1-26--
1----7389
56--8----
--3--6--8
4-679---3
-8-2---56
3-18-5967
--593---2
-9-------
测试后才知道,可能因为第一排数字排列的运算几率可能性太小,且由高到低,运算时的排序方法编程需改进.
回覆刪除出現高手了！
回覆刪除...我是上面那个匿名的...什么高手吖...
回覆刪除XD
回覆刪除-1---3--7
回覆刪除-3--8--46
--7---2--
6--8-1---
-8---3-5-
---4-7--9
--6---5--
57--2--9-
---1---7-
好了..這題目也無法計算。
你這題根本錯誤還怪人家計算機
回覆刪除哎呀XD
回覆刪除總是會有遇到無法解的錯誤題目的時候，就跟人生很多問題是找不到解答一樣。
放寬心吧。
是說有解答可供參考嗎？
回覆刪除-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-
题目错误，无解
我的題目也有算不出來的
回覆刪除有題目跟解答讓我方便偵錯嗎？
回覆刪除以我的經驗,台灣某一些出版社的數獨書是亂出題目騙錢的,題目根本不能解出答案,要不然就是一題多個解答,如果用這類題目測試解答計算器,當然是會失望的.我用一些正確題目測試的結果,解答計算器都能跑出唯一且正確的解答.
回覆刪除好，修正了之前一直就有的bug。
回覆刪除匿名講到的題目，我把它做成範例2的按鈕，而現在也能夠正常地運算啦。
它會算出匿名講到的三個解答中的第一個。
雖然感謝Thomas Ti幫我護航，可是之前的確是有bug。
現在修正了，歡迎大家再來挑戰。
沒想到這個大學時在演算法課堂中無聊實作的一支小程式，到現在都還有人在使用
真是讓人感到欣慰
有問題歡迎提出喔！
4x4的數獨有人 會嗎?????
回覆刪除(1~16)
如有發現，請相告，急需~~~>_<
謝謝!!!!!!!!!
這還真的是相當特別的要求呢。
回覆刪除我並不會解4x4數獨，不過程式修改一下邏輯的話，應該就能夠做到。
我比較好奇的是，為什麼會需要解4x4數獨呢？
因為我要考奧林匹亞
回覆刪除嗯……那你要的應該是解4x4數獨的方法，而不是程式或人？
回覆刪除是說，不能用解3x3的方法去解4x4嗎？
恩
回覆刪除验证次数：495276
回覆刪除To 28樓的匿名：
回覆刪除似乎是很難的題目呢，最後有解答出來嗎？
---8-9---
回覆刪除5-----71-
--2--3---
-1--2----
------4--
-3---85-9
-54------
--1---2--
---9-2---
誰能給我正解
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
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
有人會期待我做出改善後的演算法嗎？
雖然現在已經有很多網站都有數獨解答器的功能了耶？
謝謝原作者。
回覆刪除老二考完期末，從學校拿回來個課外作業就是個數獨。自己和老大搞了很久都搞不出來，最後用這個工具算出來了，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萬多次就搞定
To 33樓匿名，
回覆刪除感謝提供了一個相當有挑戰性的題目
我只是有點意外到現在這個工具還如此受人歡迎XD
http://blog.yam.com/ewestein/article/16409663
回覆刪除To 38樓的匿名先生：
回覆刪除我本來以為這是廣告連結，結果打開之後卻是另一個數獨解答器
不過邏輯上似乎還有待加強，畢竟是物件導向的時代了，把包很多層的迴圈拆成多個方法，會讓人比較容易理解。
然而這解答器跟我的作法差不多，都是n-queen的遞迴策略
我後來想過，更好的作法是從最少可能性的格子去猜解答，這樣效率會更高
不過那也是好幾年前的事情了，後來就做其他事情沒去解。
反正寫數獨解答的人這麼多，也不差我一個啦XD
還是寫些其他大家沒寫過的程式比較好。
http://www.sudokuwiki.org/sudoku.htm 這個網頁把各種方式都掛在上面，還可以看一步一步的處理方式。感想：很強大...
回覆刪除To 37樓匿名，
回覆刪除感謝分享。
可以下載下來嗎
回覆刪除To 39樓匿名，
回覆刪除你可以直接下載這個網頁來使用
例如用Google Chrome的「另存網頁為...」下載，下載位置如下圖所示：
建議可以用MHT格式來儲存
http://www.ubuntu-tw.org/modules/newbb/viewtopic.php?post_id=235354
解不了QAQ
回覆刪除To 41樓匿名：
回覆刪除請告訴我你的題目，以及如果有的話的正確解答，謝謝
感謝布丁布丁吃什麼，我用這個超好用的程式解了兩道五星的一個解了2400多次，一個解了將近30000多次的終於解完了。。。感謝感謝
回覆刪除不客氣XD
回覆刪除那個,如果說發覺自己的數字一直不斷和縱軸的數字重複那該怎麼辦?
回覆刪除把你的題目貼出來看看？
回覆刪除根據上面的討論，有些時候是題目本身自己就有問題了