C语言数独游戏的求解方法
更新时间:2020年4月25日 17:26 点击:1687
数独游戏的解法:
先将数独分为九个格子,用一个数组将每个小九宫格的候选数存放下来,将候选数挨个放进数独里的空位,如果这一行和这一列都没有这个数字,继续放入下一个,如果不能放入的话就回到上一步继续尝试,直到成功求出数独的解为止;
比如这个数独第一个九宫格的候选数就有1,2,7,8,9,我们需要从1开始放入第一个格子挨个尝试直到8的时候发现剩下的两个格子都不能放入
这个时候我们就要撤回上一个插入的7,发现8仍然不能放入,就继续撤回2,发现8可以放入,就将8放入3号位置,然后将9插入
这个时候我们发现2不能放入剩下的两格,我们就继续撤回到1插入的时候,将2放入1号位置,然后挨个放入剩下的数
循环这一过程,直到数独求出解为止;
这个方法比较容易想到,操作也比较容易实现
下面是代码
代码大多数都写了备注便于理解
题目需要的1000道题放在下面了,将这1000个txt文件拷到EXE文件同一目录就可以了
题目链接:数独题目
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 81 typedef struct asd{ int x;//待测试的值的x坐标 int y;//待测试的值的y坐标 int p;//待测试的值的位置(1道9代表在九宫格里的位置) int n;//待测试的值 }A; A zhan[MAX];//存放每个放进题目数组测试的数据 void kongque(int queshi[9][9],int aa[9][9]);//函数将候选数数组里去除题目中有的数字 void shuchu(int aa[9][9],int q);//输出整个数组到文件中 int end(int aa[9][9]); //判断是否结束 int next(int queshi[9][9],int m,int n,int *x,int *y,int aa[9][9]);//查找下一个应该放进九宫格测试的数据 int chazhao(int aa[9][9],int m,int n,int num);//查找同一行同一列是否有相同的值 int nfrz(int queshi[9][9],int aa[9][9],int m,int n,int *p);//判断是否满足入栈条件(就是当前值是否可以插入九宫格) int rz(int *t,int x,int y,int p,int num);//入栈操作 int cz(int *t,int *x,int *y,int *p,int *num);//出栈操作 void aaaa(char aa[10],int a);//计算题目文件的文件名 void bbbb(char aa[10],int a);//计算答案文件的文件名 int main(){ int i;//记录该调用哪道题 for(i=0;i<1000;i++){ int aa[9][9],j,k;//aa数组存放的是题目数独 int queshi[9][9];//存放的是每个九宫格的待选数 int end=0;//判断循环结束条件 int h=0,l=0,p=1;//h是候选数的行坐标,l是候选数的列坐标,p代表当前测试数属于小九宫格的位置 int t=-1;//栈的长度 int s=0,num; FILE *u; char qwe[10]; for(j=0;j<9;j++)//将数组置为每行都是(1到9) for(k=0;k<9;k++) queshi[j][k]=k+1; aaaa(qwe,i); u=fopen(qwe,"r"); for(j=0;j<9;j++){//读入题目 for(k=0;k<9;k++){ fscanf(u,"%d",&aa[j][k]); } } fclose(u); memset(zhan,0,sizeof(zhan));//将栈的数据全部置为0 kongque(queshi,aa); while(end!=1){//开始求解 s=next(queshi,h,l,&h,&l,aa);//查找下一个应该放进九宫格测试的数据 if(s==0){//如果找到则进入下一层 s=nfrz(queshi,aa,h,l,&p);//判断能否插入数独里 if(s==0){//如果可以则将插入的数据存放到栈里(入栈) s=rz(&t,h,l,p,queshi[h][l]); if(s==0){ //如果入栈成功则写入数独 aa[h/3*3+(p-1)/3][h%3*3+(p-1)%3]=queshi[h][l]; l++;//待选数跳到下一个 p=1;//重新从第一个小格子开始判断是否插入 } else{ end=1;//循环结束 } } else{ s=cz(&t,&h,&l,&p,&num); if(s==0){//如果出栈成功则擦除插入的数据 aa[h/3*3+(p-1)/3][h%3*3+(p-1)%3]=0; p++; } else end=1; } } else if(s==-1){ shuchu(aa,i);//输出求解完毕的数独 end=1; } else{ printf("发生未知错误"); end=1; } } } return 0; } //函数将候选数数组里去除题目中有的数字 void kongque(int queshi[9][9],int aa[9][9]){ int i,j,x,y; for(i=0;i<j;i++){ for(j=0;j<9;j++){ if(aa[i][j]){ x=i/3*3+j/3;//数独数组和候选数数组的坐标转换 y=aa[i][j]-1; queshi[x][y]=0; } } } } //输出整个数组到文件中 void shuchu(int aa[9][9],int q){ int i,j; FILE *p; char qq[10]; bbbb(qq,q); p=fopen(qq,"w"); for(i=0;i<9;i++){ for(j=0;j<9;j++){ fprintf(p,"%d ",aa[i][j]); } fprintf(p,"\n"); } fclose(p); } //判断是否结束 int end(int aa[9][9]){ int i,j,num=0; for(i=0;i<9;i++){ num=0; for(j=0;j<0;j++){ num+=aa[i][j];//检查每一行是否为1到9 } if(num!=45) return -1; } for(j=0;j<9;j++){//检查每一列是否为1到9 num=0; for(i=0;i<9;i++){ num+=aa[i][j]; } if(num!=45) return -1; } return 0; } //查找下一个应该放进九宫格测试的数据 int next(int queshi[9][9],int m,int n,int *x,int *y,int aa[9][9]){ int qqq=0; if(n>8){//如果当前小九宫格填写完毕则进入下一个九宫格 n=0; m++; } if(m>8){ qqq=end(aa);//判断是否结束 if(qqq!=0) return -1; else return 1; } while(queshi[m][n]==0){ if(n<8) n++; else{ n=0; m++; if(m>8){ qqq=end(aa); if(qqq!=0) return -1; else return 1; } } } *x=m;//重新获取测试的值的x坐标和y坐标 *y=n; return 0; } //查找同一行同一列是否有相同的值 int chazhao(int aa[9][9],int m,int n,int num){ int i; for(i=0;i<9;i++){//查找行 if(aa[m][i]==num) return -1; } for(i=0;i<9;i++){//查找列 if(aa[i][n]==num) return -1; } return 0; } //判断是否满足入栈条件(就是当前值是否可以插入九宫格) int nfrz(int queshi[9][9],int aa[9][9],int m,int n,int *p){ int s=*p; int i,t1,t2,num; num=queshi[m][n]; for(i=s;i<10;i++){ t1=(m/3)*3+(s-1)/3; t2=(m%3)*3+(s-1)%3; if(aa[t1][t2]!=0){ s++; continue; } if(chazhao(aa,t1,t2,num)!=0){ s++; continue; } else{ *p=s; return 0; } } return -1; } //入栈操作 int rz(int *t,int x,int y,int p,int num){ if(*t>=MAX){ return -1; } else{ (*t)++; zhan[*t].x=x; zhan[*t].y=y; zhan[*t].p=p; zhan[*t].n=num; return 0; } } //出栈操作 int cz(int *t,int *x,int *y,int *p,int *num){ if(*t==-1){ return -1; } else{ *x=zhan[*t].x; *y=zhan[*t].y; *p=zhan[*t].p; *num=zhan[*t].n; (*t)--; return 0; } } //计算题目文件的文件名 void aaaa(char aa[10],int a){ if(a>=0&&a<10){ aa[0]='0'; aa[1]='0'; aa[2]='0'; aa[3]=a+'0'; } else if(a<100){ aa[0]='0'; aa[1]='0'; aa[2]=a/10+'0'; aa[3]=a%10+'0'; } else if(a<1000){ aa[0]='0'; aa[1]=a/100+'0'; aa[2]=a/10%10+'0'; aa[3]=a%10+'0'; } aa[4]='.'; aa[5]='t'; aa[6]='x'; aa[7]='t'; aa[8]='\0'; } //计算答案文件的文件名 void bbbb(char aa[10],int a){ if(a>=0&&a<10){ aa[0]='a'; aa[1]='0'; aa[2]='0'; aa[3]=a+'0'; } else if(a<100){ aa[0]='a'; aa[1]='0'; aa[2]=a/10+'0'; aa[3]=a%10+'0'; } else if(a<1000){ aa[0]='a'; aa[1]=a/100+'0'; aa[2]=a/10%10+'0'; aa[3]=a%10+'0'; } aa[4]='.'; aa[5]='t'; aa[6]='x'; aa[7]='t'; aa[8]='\0'; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
上一篇: C语言实现车辆出租管理系统
下一篇: C++为什么要用指针而不直接使用对象?
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04