重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
玩过数独都知道数独做起来本来就很复杂,特别是到了最后还要猜数,验证
成都创新互联公司主营罗田网站建设的网络公司,主营网站建设方案,app软件开发,罗田h5微信小程序定制开发搭建,罗田网站营销推广欢迎罗田等地区企业咨询
你还在入门阶段就尝试这么复杂的问题真的很有挑战精神呢
机解数独的步骤:
建立一个数组
1:确定唯一数(没有集合做的很麻烦呢,不过笨办法还有有的,不详写),有些格子的数是唯一的,如果有唯一数,跳到第二步;
如果没有,则跳得到第三步;
2:将唯一数代入数组,跳到第一步;
3:做一个循环判定,如果是空位,确定数字的可能的情况(不详写),在做一个选择判断,
情况1:选择一个数字,跳到第一步;
情况2:选择第二个数字,跳到第一步;
........
分太少了,楼主好好努力吧
(哥们真的写了很久,一定要给分分啊。)
(两个测试过的文件为)
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8
第二个
写的太乱了,不抄了,程序正确性应该蛮高的,在测试的时候把逻辑有弄了一遍。
你看代码的话可能第一次有点累,请耐心点看吧。
希望我的努力能对你有所帮助。
你的算法有些问题
简单来说
1*2*3*4 = 24
但是1*1*1*24 = 24;
而你的题目并没有规定数字一定是各位数,且不能重复,所以用楼主的算法在这种情况下是不成立的。
我用我的方法写一下,写好了上传
#include stdio.h
int isDig(char a)
{
if(48=aa=57)
{
return 1;
}
return 0;
}
void read(FILE *txtF, int numArr[], int arrSize)
{
int digFlag, number, putFlag,i;
char c;
digFlag = 0;
putFlag = digFlag;
number = 0;
i=0;
while((c = getc(txtF))!=EOF)
{
if(isDig(c))
{
putFlag = digFlag = 1;
}
else
{
digFlag = 0;
}
if(putFlag != digFlag)
{
if(i=arrSize)
{
break;
}
else
{
numArr[i++] = number;
}
putFlag = digFlag;
number = 0;
}
if(digFlag)
{
number = number*10+(c-48);
}
}
if(number!= 0)
numArr[i] = number;
}
int check(int arr[])
{
int a[10] = {0};
int i,j;
for(i=1; i10; i++)
{
for(j=1; j10; j++)
{
if(arr[i-1] == j)
{
a[j] = 1;
break;
}
}
}
for(i=1; i10; i++)
{
if(a[i] == 0)
{
return 0;
}
}
return 1;
}
int rowCheck(int arr[])
{
int i,j,k;
int a[9];
for(i=0; i73; i+=9)
{
for(j=i, k=0; ji+9; j++,k++)
{
a[k] = arr[j];
}
if(!check(a))
{
printf("Row check fail at line %d\n", i+1);
return 0;
}
}
return 1;
}
int lineCheck(int arr[])
{
int i,j,k;
int a[9];
for(i=0; i9; i++)
{
for(j=i, k=0; j=i+72; j+=9, k++)
{
a[k] = arr[j];
}
if(!check(a))
{
printf("Line check fail at line %d\n", i+1);
return 0;
}
}
return 1;
}
int squareCheck(int arr[])
{
int i,j,h,k;
int a[9];
for(i=0; i61; i+=3)
{
for(j=i,k=0; ji+3; j++)
{
for(h=j; h=j+18; h+=9, k++)
{
a[k] = arr[h];
}
}
if(!check(a))
{
printf("Square check fails at the square start at %d\n", i+1);
return 0;
}
}
return 1;
}
int main(void)
{
void read(FILE*, int[], int);
int check(int[]);
int rowCheck(int[]);
int lineCheck(int[]);
int squareCheck(int[]);
FILE * fp;
int arr[81];
int i;
if((fp = fopen("data2.txt", "r"))==NULL)
{
printf("Open failed");
return 0;
}
read(fp, arr, 81);
for(i=0; i81; i++)
{
printf("%d ",arr[i]);
if((i+1)%9 == 0 )
printf("\n");
}
fclose(fp);
printf("Row Check: %d\n", rowCheck(arr));
printf("Line Check: %d\n", lineCheck(arr));
printf("Square Check: %d\n", squareCheck(arr));
}
/*
因为你说是数独 可是你只表述了行列相等,如果是数独应该对角线相加也相等,所以我写了两个判断函数,judge1为对角线也相等的情况,judge为你描述的行列和相等(情况太多了)
结题方案只需要做一次dfs就可以了,还需要配合一个栈来存储dfs的路径,将每个符合条件的路径做一次行列和是否相等的判断 然后输出就是要的结果!
*/
#includestdio.h
#includememory.h
#includestdbool.h
//stack
int a[9]={0};//a[0]--a[0][0] a[1]--a[0][1] and so on simulate stack
int len=0;
//dfs
int visited[10]={0};
bool judge()//行列相等
{
int i,j;
int tmp[6]={0};
for(i=0;i3;i++)
for(j=0;j3;j++)
tmp[i]+=a[3*i+j];
for(i=0;i3;i++)
for(j=0;j3;j++)
tmp[3+i]+=a[i+3*j];
int jud=tmp[0];
for(i=1;i6;i++)
{
if(jud!=tmp[i])
return false;
}
return true;
}
bool judge1()//行列相等 对角线也相等
{
int i,j;
int tmp[8]={0};
for(i=0;i3;i++)
for(j=0;j3;j++)
tmp[i]+=a[3*i+j];
for(i=0;i3;i++)
for(j=0;j3;j++)
tmp[3+i]+=a[i+3*j];
tmp[7]=a[0]+a[4]+a[8];
tmp[6]=a[2]+a[4]+a[6];
int jud=tmp[0];
for(i=1;i8;i++)
{
if(jud!=tmp[i])
return false;
}
return true;
}
void printa()
{
int t,p;
for(t=0;t3;t++)
{
for(p=0;p3;p++)
{
printf("%d ",a[3*t+p]);
}
printf("\n");
}
}
void dfs(int i,int v[])
{
if(i==10)//find one solution
{
if(judge1())//给你写了两个判断函数 如果对角线也相等那么用judge1()即可判断
printa();
return;
}
int j;
for(j=1;j=9;j++)
{
int tmp[10];
memcpy(tmp,v,10*sizeof(int));
if(tmp[j]==0)
{
tmp[j]=1;
a[len++]=j;
//printf("%d %d\n",len-1,a[len-1]);
dfs(i+1,tmp);
len--;
}
}
}
int main(void)
{
dfs(1,visited);
return 0;
}