作者no1kk (心中在下雨)
看板Ajax
標題Re: [心得] 用javascript + jQuery 寫的數獨解題器
時間Sat Dec 25 01:47:14 2010
說明一下解題邏輯好了
先定義一下名詞
直的是欄
橫的是列
一組九宮格是一群
確定的數字是正解
可能是答案的數字叫可能數字
一共有五個步驟
1.假設知道某格的正解是5
則將同一欄、列、群其他格的可能數字5刪除
在每次取得正解時會執行此項 (包含一開始輸入題目)
2.
a假設某一欄、列、群的某一個可能數字只剩下一個則他就是正解
b假設某一格的可能數字只剩下一個，則這個可能數字是正解
3.某一群的可能數字(同一號碼)，集中在同一欄或列
則該欄或列的其他位置不會再出現那個可能數字
4.
a某一欄、列、群的其中兩格只有兩個一樣的可能數字
則該欄、列、群的其他位置不會再出現這兩個可能數字
b某一欄、列、群有兩個數字只出現在某兩格
則這兩格不會再有其他可能數字
5.
假設某一欄只有兩格可能數字是5
而某另一欄的可能數字5也只出現在相同列的那兩格之中
則那兩列的其他位置就不會再出現可能數字5
同理可證列
按下按鈕後開始執行2
2有結果 -> 2
沒結果 -> 3
3有結果 -> 2
沒結果 -> 4
4有結果 -> 2
沒結果 -> 5
5有結果 -> 2
沒結果 -> 結束
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.85.197.5
※ 編輯: no1kk 來自: 219.85.197.5 (12/25 01:48)
1F：→ TonyQ:就是check_1 , check_3 , check_4 ... function XD 12/25 01:52
2F：→ tomin:我看成 真的是欄 好！我相信你XD 12/25 02:00
3F：→ TonyQ:我剛在build test case 時發現這個就解不出來 12/25 16:28
5F：→ no1kk:剛剛研究了這題，的確解不出來，可能必須用假設的，或是其他 12/25 22:36
6F：→ no1kk:解題邏輯才能解開...預設的五種解題方式無法.. 12/25 22:36
7F：→ TonyQ:看起來是 12/25 23:32
8F：→ TonyQ:因為我在重構解題邏輯的部份 需要有測試案例來驗證 XD 12/25 23:32
9F：→ TonyQ:我快整理完了 :P 12/25 23:32
10F：→ TonyQ:先放出來整理過得版本 12/26 00:58
12F：→ TonyQ:不過還有一些最佳化還沒做，像是getCells 。 12/26 00:58
13F：→ TonyQ:應該從 test2.html/main.html 開始看 比較容易進入狀況 12/26 01:20
14F：→ TonyQ:輸入驗證的 validation 做完了 接著做 export :P 12/26 02:56