主题:数独(sudoku)求解和生成★(第16版3月5日修改)
雨中飞燕
[专家分:18980] 发布于 2008-02-12 13:08:00
我写了一个数独求解程序(看本文最后面),首先在最顶的文本框输入
700100400030080070006004001800700600070090020002003007500900200090060040001005008
共81个数字,表示一个9*9数独,再按一下init(initialize)按钮,
就用这些数字初始化了下面的矩阵,
然后再按solve按钮就是可算出结果了。
有唯一解就会给出唯一解,如果有多解就填入能唯一确定的数值。
当然你可以自己构造一组数据来输入。
copy按钮是把矩阵的结果复制到上面的文本框(方便复制)
Hint按钮是提示功能,提示当前可以进行的操作
帮忙找找有没有什么bug,找到的话高分相赠,谢谢。
主要是软件计算方面,有没有本应唯一解的却解不出,
多解的当成唯一解,或者无解的出现错解等等。。。。
------------------------------------------------------------------
第三版更新:增加推理过程显示
第四版更新:界面友好化
第五版更新:增加推理条件,算法加强
第六版更新:增加推理条件,算法加强,加强无解判定,推理过程显示有少量修改
第七版更新:增加推理条件(三数集法等),界面显示有修改,推理过程内容显示有修改
第八版更新:增加推理条件(简单染色法),推理过程内容显示增加英文
第九版更新:增加了题目生成功能和题目难度判断功能,本功能还在测试中。
第十版更新:算法加强,特别加强了唯一性判定,特别难题目自动加深搜索
第11版更新:算法加强,特别增加即时代码编译运行接口
第12版更新:算法加强,多解、无解判定速度加快,生成题目速度加快,本版本保证不会误判解的情况。
第13版更新:算法加强,修正多解判定时一个会导致计算过慢的问题,增加了五种推理方法,难度计算有修改
第14版更新:算法加快,判断解的情况的算法速度再次提高,修正计算难度的Bug
第15版更新:主要是Bug修正,较14版和13版稳定
第16版更新:求解广度修正,内存泄露问题修正,增加求解时间统计,
生成的题目50%以上是难题(以笔算为准)。
关于这个新增加的接口,有Solve和Make两个不同程序,通过标准输入和输出交互,
Solve程序的main返回值表示解答结果,需要使用MinGW编译器编译运行。
使用时只要在本软件里直接输入C++代码,就可以编译链接成一个Shell随时调用,
你可以把自己的Solve代码或者Make代码写进去作为本软件的一个扩展功能。
详细接口信息见软件内说明(option按钮)。
点这里进入本软件下载页面[url]http://yzfy.org/bbs/viewthread.php?tid=679[/url]
最后更新于:2008-03-06 22:18:00
回复列表 (共86个回复)
71 楼
雨中飞燕 [专家分:18980] 发布于 2008-02-26 12:27:00
[quote]
我认为确定唯一有以下几点:
1:当一行或一列或一个九宫格中只剩一个位置没有数字添入,
那么这个位置的数字唯一
2:当一行或一列或一个九宫格中只有一个位置可以添某数A,而其他位置都不可以
那么这个位置的数字唯一
3:当一个位置的所在行,所在列,九宫格中,不重复数字的个数是8个
那么这个位置的数字唯一[/quote]
你这个是简单的逻辑推理,而我所说的唯一是当前题目是否唯一解
72 楼
yfbsg [专家分:30] 发布于 2008-02-27 06:52:00
不好意思啊,理解错了
73 楼
tianran1011 [专家分:60] 发布于 2008-03-06 20:39:00
你的程序已经相当完美了,不过你还没有说明你的生成数独的算法,也许是我没找到?我比赛时用的成才的算法自我感觉很不好。你能介绍一下吗?
74 楼
雨中飞燕 [专家分:18980] 发布于 2008-03-06 22:12:00
你用的是什么算法?
我用的算法是很简单的挖洞,不过算法上有变形
75 楼
tianran1011 [专家分:60] 发布于 2008-03-07 23:03:00
我们也没有想出来什么好的办法。也是简单的挖洞,边挖边检验,如果要生成指定的比较高难度的要反复尝试N久。
还想过用解空数独的方法,理论上应该可以找到所有的忧唯一解的数独,不过运算量也太大。
76 楼
tianran1011 [专家分:60] 发布于 2008-03-07 23:06:00
还有你的难度级别最高可以达到100多级别或者更高,如果说是按照人的思维来想,通常不用分这么细吧……而且很多题目一旦到了要用试探的方法后,人只要愿意用纸笔多记数字,都只是时间问题,不应该算是什么超级难题。
77 楼
tianran1011 [专家分:60] 发布于 2008-03-07 23:11:00
你的最新版本是不是不再判断难度级别了?这次mcm重点不是怎么解,是怎么定难度,我感觉定难度比解要麻烦,解的方法去找找就那么些用个十几二十个就差不多了,自己想新方法基本不可能。定难度才是有点东西研究的。
78 楼
雨中飞燕 [专家分:18980] 发布于 2008-03-08 13:09:00
新版本不是没有难度级别,是换了个方式,不使用level,而改成难度积分
定难度我不觉得是主要的,你把逻辑法写得7788就能够定难度了
79 楼
rickone [专家分:15390] 发布于 2008-05-07 00:49:00
飞燕大姐,你用的什么算法求解的?有一些问题想和你交流,最好是能看到你的源码,可以吗?我现在想解大型数独,还要你的帮忙才行。。。
rickone@sina.com
80 楼
rickone [专家分:15390] 发布于 2008-05-07 00:49:00
BTW:你的网站里的头像好性感~
我来回复