还剩15页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构大型作业实验报告书设计题目“数独”游戏设计与求解1.题目说明数独的游戏规则
1、在9×9的大九宫格内,已给定若干数字,其他宫位留白,玩家需要自己按照逻辑推敲出剩下的空格里是什么数字
2、必须满足的条件每一行与每一列都有1到9的数字,每个小九宫格里也有1到9的数字,并且一个数字在每行、每列及每个小九宫格里只能出现一次,既不能重复也不能少
3、每个数独游戏都可根据给定的数字为线索,推算解答出来按照数独的游戏规则,用计算机实现已知数独的求解和数独题目的出题2.数据结构说明数据结构一维数组、二维数组以及类似于“栈”的数据结构主要操作有进栈,出栈,栈顶元素的操作等等3.抽象数据类型AbstractDataType简称ADT五个全局变量数组,其中两个二维数组,三个一维数组inta
[10]
[10]接受输入数据,空白处则初始化为0之所以把数组范围设计为10*10,是为了程序的可读性符合人的习惯思维intsd
[82]在实现“回溯”算法的时候,因为要用到栈的数据结构,所以把a
[10]
[10]二维数组中的数据转换储存进sd
[82]一维数组方便处理题目以及保存最后结果intfix
[82]对应于sd
[82],记录哪些位置已经确定确定则fix值为1,未确定为0intpossible
[82]
[10]第一维对应着sd
[82]中的每一个,第二维的下标为每个位置的可能值有可能则为第二维的下标,不可能则为-1intstack
[82]类似于“栈”数据结构的数组,实现“回溯”算法的关键所在回溯之前,把所有fix值为0的数据存如stack数组中,即进栈回溯中逐渐确定这些位置的数值,无法确定者(即1--9都不适合的)则应回退到前一位置,修改其fix值,以此类推直至stack中所有的值都确定下来(即题目完成),或者回退到了最初点的前一位置(说明题目有误)4.算法设计程序可以考虑人工智能的算法所谓人工智能的算法,应当是算法设计者对该游戏的特性有较为深入的了解,依据其内在__设计出的和人类思维相似的解决算法但这似乎太过复杂,所以这里决定采用“回溯”的方法解决数独问题基本框架如下五.数独程序代码#includestdio.h//标准输入输出头文件#includeconio.h//包含getch的头文件#includestdlib.h//包含rand的头文件#includeassert.h//包含assert的头文件#includetime.h//包含srand的头文件//五个全局变量数组inta
[10]
[10];//用来接收输入数据的数组intsd
[82];//处理题目以及保存最终结果intfix
[82];//记录哪些位置是确定的,确定为1,否则为0intpossible
[82]
[10];//记录所有未确定数字的可能性intstack
[82];//用来放置填入的数的栈voidclssd//初始化函数,所有位置设为0{intijk;fori=0;i9;i++forj=0;j9;j++a[i][j]=0;fork=1;k=81;k++sd[k]=0;}intlineintlineintvalue//检验行{inti;fori=1;i=9;i++{ifa[line][i]==valuereturn0;}return1;}introwintrowintvalue//检验列{inti;fori=1;i=9;i++{ifa[i][row]==valuereturn0;}return1;}intsquareintlineintrowintvalue//检验3*3的九宫{intLRij;L=line%3!=0+line/3;//L表示所在九宫的行数R=row%3!=0+row/3;//R表示所在九宫的列数fori=L-1*3+1;i=L*3;i++{forj=R-1*3+1;j=R*3;j++ifa[i][j]==valuereturn0;}return1;}//四个转换函数inttransform_to_lineinti//实现sd[i]-a[line][row]之间的转换{intline;line=i/9+i%9!=0;returnline;}inttransform_to_rowinti//实现sd[i]-a[line][row]之间的转换{introw;row=i%9+9*i%9==0;returnrow;}voidtransform_to_ainti//sd[i]-a[line][row]的转换{intlr;l=transform_to_linei;r=transform_to_rowi;a[l][r]=sd[i];}voidtransform_to_sd//实现a[line][row]-sd[i]的转换{intlinerowi=1;forline=1;line=9;line++forrow=1;row=9;row++do{sd[i]=a[line][row];i++;break;}whilei=81;}//输出函数voidprintAll{inti;fori=0;i81;i++{ifi%9==0printf\n\n\t\t;printf%4dsd[i+1];}printf\n\n\n;}voidinput//输入数据到a
[10]
[10]{systemcls;//清屏intb
[3]={000}ij;printf请输入已知数据;printf\n\n例如输入789,表示第8行第9列的数值为7,以此类推\n\n\n;do{printf\n输入数据按照值/行/列的顺序,以0结束;fori=0;i3;i++{j=getch-48;ifj==0i==0break;//实现按0结束语句ifj0j10{b[i]=j;printf%3db[i];}elsei--;}a[b
[1]][b
[2]]=b
[0];}whilej;transform_to_sd;printf\n\n\n\t您输入的题目为:\n\n;//打印输入的数独printAll;}//三个重要函数boolbeExistintiintj//判断sd数组中位置为i的元素是否存在{intlr;l=transform_to_linei;r=transform_to_rowi;//ifsd[i]!=0return1;关键的错误所在!!!iflinelj*rowrj*squarelrj==0return1;elsereturn0;}voidsetPb//控制possible数组{intij;fori=1;i=81;i++{forj=1;j=9;j++{ifsd[i]!=0possible[i][j]=-1;//如果sd[i]为已知输入数据,则将可能值设为-1elseifbeExistij{possible[i][j]=-1;}//若在行、列、九宫内,存在相同数值则possible设为-1else{possible[i][j]=j;}//其他情况讲可能值保存进possible数组}}}boolfixAllintsd[]intfix[]intpossible
[82]
[10]//控制fix数组{intij;intk
[82];fori=1;i=81;i++//将已经存在的数据对应fix数组中的值设为1,不存在设为0{ifsd[i]!=0{fix[i]=1;}else{fix[i]=0;}}fori=1;i=81;i++//判断未确定空格处值的可能性{ifsd[i]!=0continue;iffix[i]==0{forj=1;j=9;j++ifpossible[i][j]!=-1k[i]++;}ifk[i]==1//如果存在只有一种可能的位置则将fix[i]改为1fix[i]=1;sd[i]=possible[i][j];}fori=1;i=81;i++//判断是否存在只有一种可能的位置,若没有返回0{ifk[i]==1return1;elsereturn0;}}//判断是否完成intisFullintsd[]{inti;fori=1;i=81;i++ifsd[i]==0return0;return1;}voidpreDo//预处理{while1{setPb;if!fixAllsdfixpossible//即不存在只有一种可能性的位置break;ifisFullsd//若已经推出全部结果break;}ifisFullsdprintAll;//打印结果}intcalculate//填数独关键算法!!!{preDo;//预处理找出所有的位置的可能数值ifisFullsdreturn1;inttop=0;//将所有为0的位置入栈forinti=1;i82;i++{iffix[i]==0stack[top++]=i;}int__x=top;//记录最大数目加1top=0;//指向栈顶inttemp;boolflag=true;//该标志位说明了当前是正常入栈while1{asserttop=0;//宏定义,调试程序之用ifflag{intj;forj=1;j=9;j++ifpossible[stack[top]][j]!=-1!beExiststack[top]j//若top所示的位置上,可以安插j这个数值,则{fix[stack[top]]=1;sd[stack[top]]=j;transform_to_astack[top];//实现a[line][row]与sd[i]同步变化++top;iftop=__xreturn1;break;}ifj9//该空所有可能值都不可以,则退一格{--top;iftop0{printAll;return0;}flag=false;}}else{ifsd[stack[top]]==9//说明当前这个top也没有可以选择的数,继续回退{fix[stack[top]]=0;sd[stack[top]]=0;transform_to_astack[top];--top;iftop0{printAll;return0;}}else{temp=sd[stack[top]];temp++;whilepossible[stack[top]][temp]==-1||beExiststack[top]temp{temp++;iftemp9break;}iftemp9//当前节点没有更换的可能性,继续退回{fix[stack[top]]=0;sd[stack[top]]=0;transform_to_astack[top];--top;iftop0{printAll;return0;}}else{sd[stack[top]]=temp;transform_to_astack[top];++top;flag=true;//重新设定flag}}}}}voidsolve_problem//解题{intp;systemcls;//清屏clssd;//赋初值为0input;//输入数据transform_to_sd;//转换为sd[i]数组p=calculate;//计算数独ifp==0printf\t题目有误!!!;printf\n\n\t答案为\n;printAll;}voidrandom//从1-9中随机产生几个值输入sd
[1]至sd
[9]{intijr;intchange=1;intb
[10]={0000000000};fori=1;i=9;//从1-9中随机产生几个值{change=1;j=1+rand%9;forr=1;r=9;r++ifb[r]==jchange=0;ifchange==1{b[i]=j;i++;}}fori=1;i=9;i++{sd[i]=b[i];transform_to_ai;}}voidhide//遮罩函数{intif;printf请输入难度:\n\n
1.Easy\n\n
2.Nor__l\n\n
3.Hard\n\n
4.SoHard\n\n
5.TerribleHard\n\n;do{f=getch-48;}whilef5||f1;//一共5个级别fori=1;i=81;i++{ifrand%6=f//利用随机数出现的概率出题printf%4dsd[i];elseprintf0;ifi%9==0printf\n\n;}}void__ke_problem//出题函数{systemcls;//初始化clssd;random;//填9个随机值calculate;//算出答案hide;//遮罩,将答案中一些数值遮住printf\t\t\t注意题目中0代表待填数据\n\n\t\t按空格键输出答案其他键退出程序\n;intf;do{f=getch-32;if!fprintAll;elsebreak;}whilef;}void__in//主函数{srandunsignedtime0;//设置时间种子为0systemcls;//清屏clssd;printf\n\t数独游戏\n\n\t
1.你出题,电脑来解\n\n\t
2.电脑出题,你来解;inti;do{i=getch-48;switchi{case1:solve_problem;break;case2:__ke_problem;break;}}whilei2||i1;}6.调试报告
1.整个程序最麻烦的地方是二维数组a
[10]
[10]与一维数组sd
[82]之间的转换因为输入数据为了方便和符合人类的思维采用了与数独相似的二维数组进行输入但是回溯算法要求转换成一维数组进行操作但是在回溯时每次判断是否一个未知数据是否可能或者是否存在的时候,均需要利用a
[10]
[10]数组进行判断所以a
[10]
[10]的功能不仅是接受输入数据更加体现在回溯时的判断过程所以调试过程中进行了很多两种数组之间转换的操作为了方便,还专门建立了4个transform转换函数
2.设计算法之初,是没有用到fix
[82]数组的后来在判断回溯与否时方便起见,引入了fix数组思路清晰了许多,也提高了算法执行效率
3.调试过程中,用到了一个宏命令assert(top=0)top是栈顶元素的“指针”,用来操控栈中元素正常情况下top=0的如果出现异常情况,则assert函数会弹出对话框报错这表示calculate函数在回溯的时候top值总是会回到栈底元素之前事实上,开始因为在beExist函数中用了错误的判断方式,运行程序时总是会使得top
04.上面一条提到的,beExist中用到了错误的判断语句//ifsd[i]!=0return1;,这就是关键的错误所在调试程序的时候总是会导致top0却一直找不到___开始以为是possible的值没有随着回溯算法的进行跟随sd的变化而变化,于是在每次sd变化之后都加上了一个setPb函数,使得possible值每填一个数据就变化一次但是导致的结果却是一旦开始回溯,必定会回溯到栈底之前运用调试工具观察possible和top值的变化才发现回溯的时候,之前填的空格处possible值都为-1,所以top每次都将回到栈底之前于是以为是setPb用的太多了,又重新删掉多余setPb函数,结果还是一样又经过几个小时的调试,终于发现是在calculate函数执行时,判断每次判断是否回溯都会运行函数beExist,调试时,进入beExist函数发现,自己之前在写这个函数的时候想当然的把sd[i]!=0当作了判断已经存在(即beExist为真)的条件直接导致top回溯到了栈底于是屏蔽掉这条//ifsd[i]!=0return1之后,程序就基本可以正常运行了
5.上一条中的错误之所以会出现,是因为在设计程序之初没有想好,不够完善于是出现了,自己设计的判断方法与计算数独矛盾的结果得到的教训是,动手之前应该先考虑清楚完整的架构和应该考虑到的细节7.测试结果分析下面为规定测试数据342172914579576231543182725419732531376852361“回溯法计算数独从界面读取数据到a
[10]
[10]预处理,算出所有fix和possible值将a
[10]
[10]中数据转存入sd
[82]。