回 帖 发 新 帖 刷新版面

主题:数独(sudoku)求解和生成★(第16版3月5日修改)

我写了一个数独求解程序(看本文最后面),首先在最顶的文本框输入
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]

回复列表 (共86个回复)

81 楼

求解方式有两种,一种是搜索法,一种是逻辑法,
当中用的逻辑法,一种就一个算法。。。但比较专用
搜索法用的是DancingLinks用来高速判定解的情况用的

你所谓的大型数独有多大?

82 楼

我想知道搜索法,你怎么做到的,就是那个dancing links,可以讲一下不?我下了论文可是e文不太好~

大型数独?原则上n>3就是,但是这是npc的,就是不同的程序能解的上限不同,你试下你的程序吧,最大到几,在可以接受的时间内,

n=3 n2=9 9*9 数独
n=4 n2=16 16*16 
...

83 楼

哈哈哈,太牛X了!!!五体投地啊!!!

84 楼

你的推理方法一共有哪些啊,能不能全部列出来?

85 楼

这个算法要讲解起来也很麻烦。。。。
偶还得看看什么时候有空。。。。

86 楼

我发现一个问题,我在测试这组数据的时候。

300105827
018030560
075080300
500904008
080503090
700608005
806040103
020350080
400801002

解题提示:

开始
区块删减法:第1列与上边区块公共元素2不可能在E1
区块删减法:第5列与中间区块公共元素7不可能在I5
区块删减法:第7列与下边区块公共元素9不可能在H9
数对删减法:格子D8不能是8列第G和I行中数对的任一个
[color=800000]数对删减法:格子F3不能是C6,I6这个格子中数对的任一个
数对删减法:格子I3不能是C6,I6这个格子中数对的任一个[/color]
。。。(下面的省略)

这个数对删减法,提示F3不是C6,I6这个格子中数对中的任何一个,算出来的结果F3为9,是在C6的数对中,是我理解错误么?

我来回复

您尚未登录,请登录后再回复。点此登录或注册