作者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