主题：数独(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个回复）
61 楼
tianran1011 [专家分：60] 发布于 2008-02-19 01:05:00
000000000000010200032005008000901400400760082000204600023008001000030800000000004
这个你的程序解了半天没解出来，我没等了。你看看能不能优化还是怎么的。
我的程序还是老是出那个not enough memory。什么时候有空帮我查不……我写的绝对是可读性很高的，都用最基本的语句，不像你那些故意折磨人的超短程序……
62 楼
tianran1011 [专家分：60] 发布于 2008-02-19 01:13:00
[img]http://hiphotos.baidu.com/tianran1011/pic/item/f2ac760067861897e850cd7f.jpg[/img]
看那个I1
隐性数对删减法：在第2个区块里候选数对3,8所在格子里不存在其它候选数
隐性数对删减法：在第4个区块里候选数对7,8所在格子里不存在其它候选数
隐性数对删减法：在第9个区块里候选数对3,7所在格子里不存在其它候选数
区块删减法：第2列与中间区块公共元素9不可能在该列和该区块其它地方
关连数删减法：在I1中只可以填数值3
63 楼
雨中飞燕 [专家分：18980] 发布于 2008-02-19 12:29:00
哦，求解过程的数据记录出现bug，但solve本身没有错的
问题已经修正好了，重新下载一个就行
64 楼
雨中飞燕 [专家分：18980] 发布于 2008-02-20 11:25:00
呵呵，第11版跳过了一个版本没发上来，主要是因为接口的测试
如果你有mingw编译器（也可以用devcpp自带的），那就可以使用本软件接口功能了
如果你想测试，可以尝试使用以下代码（简单纯逻辑法做的）：
[code=c]
#include<stdio.h>
#include<string.h>
#include<time.h>
struct{
int ok[10];
int num;
} x[10][10];
int s[3][10][10];
char strOut[10240] = "\n";
int work(int i,int j)
{
int k,l;
if(x[i][j].num)
{
for(k=1;k<10;k++)
{
x[i][k].ok[x[i][j].num]=0;
x[k][j].ok[x[i][j].num]=0;
}
for(k=(i-1)/3*3+1;k<(i-1)/3*3+4;k++)
for(l=(j-1)/3*3+1;l<(j-1)/3*3+4;l++)
x[k][l].ok[x[i][j].num]=0;
}
}
int cuts()
{
int i,j,k;
memset(s,0,sizeof(s));
for(i=1;i<10;i++)
for(j=1;j<10;j++)
for(k=1;k<10;k++)
if(x[i][j].ok[k])
{
s[0][i][k]++;
s[1][j][k]++;
s[2][(i-1)/3*3+(j-1)/3+1][k]++;
}
}
int search()
{
int i,j,k,l,m;
int count;
int flag=0;
int list[3];
int r[10];
for(i=1;i<10;i++)
for(j=1;j<10;j++)
if(!x[i][j].num)
{
count=0;
for(k=1;k<10;k++)
if(x[i][j].ok[k])
if(!count)
count=k;
else break;
if(count && k==10)
{
x[i][j].num=count;
flag++; work(i,j);
char c[100];
sprintf(c,"唯一数：在%c%d中只能填%d\n",i+'A'-1,j,count);
strcat(strOut, c);
}
else
{
for(k=1;k<10;k++)
{
list[0]=s[0][i][k];
list[1]=s[1][j][k];
list[2]=s[2][(i-1)/3*3+(j-1)/3+1][k];
for(l=0;l<3;l++)
if(list[l]==1 && x[i][j].ok[k])
{
memset(x[i][j].ok,0,sizeof(x[i][j].ok));
x[i][j].num=k; x[i][j].ok[k]=-1;
flag++; work(i,j);
char c[100];
sprintf(c,"隐含唯一数：在%c%d所在的%s仅可填%d\n",i+'A'-1,j,l==0 ? "行" : l==1 ? "列" : "区块",k);
strcat(strOut, c);
break;
}
}
}
}
return flag;
}
int main(void)
{
int i,j,k,l;
long time,flag;
memset(x,0,sizeof(x));
for(i=1;i<10;i++)
for(j=1;j<10;j++)
{
scanf("%1d",&x[i][j].num);
if(!x[i][j].num)
memset(x[i][j].ok,-1,sizeof(x[i][j].ok));
}
time=clock();
for(i=1;i<10;i++)
for(j=1;j<10;j++) work(i,j);
do cuts(); while(search());
time=clock()-time;
flag=1;
for(i=1;i<10;i++)
for(j=1;j<10;j++)
if(!x[i][j].num) { flag=0; break; }
for(i=1;i<10;i++)
for(j=1;j<10;j++)
putchar(x[i][j].num+'0');
putchar('\n');
printf("解答%s\n",flag ? "成功" : "失败");
printf(" ");
for(j=1;j<10;j++)
printf("%d ",j);
printf("\n\n");
for(i=1;i<10;i++)
{
printf("%c ",'A'+i-1);
for(j=1;j<10;j++)
printf("%d ",x[i][j].num);
printf("\n");
}
puts(strOut);
printf("Total time: %dms\n",time);
return flag;
}[/code]
65 楼
雨中飞燕 [专家分：18980] 发布于 2008-02-22 14:12:00
If no body reply this post from now on, I will not update it on this page any longer
一过了数模比赛，那些人所谓的“比赛后会继续研究”，98%都是空话，这些人就这么的功利
更新了一下，增加五种推理方法（隐三数集，三链数，XY形态法，XYZ形态法，染色法（旧版本的染色法改名为“关键数法”）），软件的生成功能生成的题目平均难度增加，修正旧矩形顶点算法的问题
最近和网友研究生成的方法，当中提及到一个快速搜索解题的方法，叫Dancing-Link，
迟些的版本会加上这个快速算法，解题速度和生成的速度可以再提升很多
66 楼
林杰杰 [专家分：8970] 发布于 2008-02-25 13:46:00
俺有一本关于数独的电子书，《programming sudoku》，讲的是怎么样用VB来解决数独的。
需要的请来函咨询。
67 楼
yfbsg [专家分：30] 发布于 2008-02-26 07:49:00
我下了一个，界面很友好，我有一个意见你看看对不对
如果这么输入：
０００００００００
０００００００３０
００００３００００
０００００００００
０００００００００
００３００００００
０００００００００
０００００００００
０３０００００００
那么（１，A）这个位置应该可以唯一确定是一了
可是没有显示
68 楼
yfbsg [专家分：30] 发布于 2008-02-26 07:50:00
不好意思发错了 （１，Ａ）可以确定是３
69 楼
yfbsg [专家分：30] 发布于 2008-02-26 07:58:00
我认为确定唯一有以下几点：
１：当一行或一列或一个九宫格中只剩一个位置没有数字添入，
那么这个位置的数字唯一
２：当一行或一列或一个九宫格中只有一个位置可以添某数Ａ，而其他位置都不可以
那么这个位置的数字唯一
３：当一个位置的所在行，所在列，九宫格中，不重复数字的个数是８个
那么这个位置的数字唯一
70 楼
雨中飞燕 [专家分：18980] 发布于 2008-02-26 11:21:00
[quote]我下了一个，界面很友好，我有一个意见你看看对不对
如果这么输入：
０００００００００
０００００００３０
００００３００００
０００００００００
０００００００００
００３００００００
０００００００００
０００００００００
０３０００００００
那么（１，A）这个位置应该可以唯一确定是一了
可是没有显示[/quote]
是吗？但我测试过是正常的，已经是第15版
这上面的版本是几天前的了
新版本下载链接请看：
[url]http://yzfy.org/bbs/viewthread.php?tid=679[/url]
我来回复
您所在位置：