爱杀数独 2.0 破J数独的小软件

APPLEUFO · 发表于 2014-10-12 08:42:39

本帖最后由宇智波·佐助于 2014-10-20 22:17 编辑

这是根据《码农》杂志第8期里面 Dennis E. Shasha 教授的算法写的数独破J软件
(简化并用广度搜索)

算法：
用广度优先搜索，由1，搜索得到234，搜索234，得到5678，这样不断搜索下去，只要数独是可解的，一定会得到结果建立一个名为数独的自定义数据类型，成员是9*9 ，这样两个两个循环就能遍历它
搜索一个数独，会由某个未填写点分裂出N个结果，并填写可用数字，保存N个结果
继续搜索N1数独，由某个未填写点，继续分裂出M个结果，并填写可用数字
不断循环这个步骤，会分裂得到成千上万的结果

其中需要去除无效的数独结果，而判断数独是否有效，则靠下面
数独有每个点横纵或者每个小三宫都有1-9的特性（也就是直观法，当然还有其他更复杂的，但都太麻烦了|||）

建立一排9个桶子，编号1-9，桶子里面的数字初始是0
扫描某个点，得到横纵与三宫的数字，然后在相同编号的桶子里加1
然后扫描这一排桶子，桶子数字为0的编号就是这点可填写的数字，有时有好几个
若是完全没有为数字0的桶子，说明这个数独是失败的，1-9都填完了，写入什么数字都是失败的了
剔除这个数独，这时候由广度优先搜索而分裂的结果们才会开始收束
直到数独都填写完毕了，然后剩下的数独就是正解了（有时候可能会剩很多结果，数独题目的结果不是唯一的，这些结果都是正解，随机选一个出来就是）

PS：每次都是填写一步，所以每次迭代搜索的数独进度全都是一样的
每次都是从头到尾扫描，看是否有可填写数字为0的点，有的话，这个数独是失败的，需剔除，无需再算下去了
------------------------------
爱杀数独2.0

使用方法：
读取：手动输入或者将导入一个9*9的数独文本到软件中（空的数字用0填充）
数独的文本格式是：每行9个数字，共9行，这样来表示一个数独

保存：则是将破J后的结果到处到TXT文本中

更换背景：随便扔喜欢的图像到文件夹，可更换背景图片为自己喜欢的

2.0更新
软件界面缩小
整理代码，优化算法，加速50%
添加清空与检查数独是否正确的按钮
更方便的自定义背景图片，可把喜欢的图片放进“背景图片”文件夹内即可
爱杀数独 2.0 编译版
http://pan.baidu.com/s/1bn4HpRT

爱杀数独 2.0 源代码
http://pan.baidu.com/s/1hqoYbq8
码农8 杂志与算法文本下载
http://pan.baidu.com/s/1gdmsoIv

例如这个数独的左上角第一个点，不考虑去找唯一可写值的时候，就能分裂出5个数独
而5个数独里面，每一个横1，纵3这个点，又可以根据所填数字，分裂出好几个数独，重复第一步