数独游戏设计与源码

数据结构大型作业实验报告书设计题目：“数独”游戏设计与求解一 题目说明 数独的游戏规则：1、 在9×9的大九宫格内，已给定若干数字，其他宫位留白，玩家需要自己按照逻辑推敲出剩下的空格里是什么数字。2、必须满足的条件：每一行与每一列都有1到9的数字，每个小九宫格里也有1到9的数字，并且一个数字在每行、每列及每个小九宫格里只能出现一次，既不能重复也不能少。3、每个数独游戏都可根据给定的数字为线索，推算解答出来。 按照数独的游戏规则，用计算机实现已知数独的求解和数独题目的出题。二 数据结构说明数据结构一维数组、二维数组以及类似于“栈”的数据结构。主要操作有：进栈，出栈，栈顶元素的操作等等三 抽象数据类型(Abstract Data Type 简称ADT) 五个全局变量数组，其中两个二维数组，三个一维数组。int a1010接受输入数据，空白处则初始化为0。之所以把数组范围设计为10*10，是为了程序的可读性。符合人的习惯思维。int sd82在实现“回溯”算法的时候，因为要用到栈的数据结构，所以把a1010二维数组中的数据转换储存进sd82一维数组。方便处理题目以及保存最后结果。int fix82对应于sd82，记录哪些位置已经确定。确定则fix值为1，未确定为0。int possible8210第一维对应着sd82中的每一个，第二维的下标为每个位置的可能值。有可能则为第二维的下标，不可能则为-1。int stack82类似于“栈”数据结构的数组，实现“回溯”算法的关键所在。回溯之前，把所有fix值为0的数据存如stack数组中，即进栈。回溯中逐渐确定这些位置的数值，无法确定者（即1-9都不适合的）则应回退到前一位置，修改其fix值，以此类推。直至stack中所有的值都确定下来（即题目完成），或者回退到了最初点的前一位置（说明题目有误）。四 算法设计程序可以考虑人工智能的算法。所谓人工智能的算法，应当是算法设计者对该游戏的特性有较为深入的了解，依据其内在联系设计出的和人类思维相似的解决算法。但这似乎太过复杂，所以这里决定采用“回溯”的方法解决数独问题。基本框架如下：“回溯法"计算数独从界面读取数据到a1010预处理，算出所有fix和possible值将a1010中数据转存入sd82五数独程序代码：#include"stdio.h" /标准输入输出头文件#include"conio.h" /包含getch()的头文件#include"stdlib.h" /包含rand()的头文件#include"assert.h" /包含assert()的头文件#include"time.h" /包含srand()的头文件/五个全局变量数组int a1010;/用来接收输入数据的数组int sd82;/处理题目以及保存最终结果int fix82;/记录哪些位置是确定的，确定为1，否则为0int possible8210;/记录所有未确定数字的可能性int stack82;/用来放置填入的数的栈void clssd()/初始化函数，所有位置设为0int i,j,k;for(i=0;i<9;i+)for(j=0;j<9;j+)aij=0;for(k=1;k<=81;k+)sdk=0;int line(int line,int value)/检验行int i;for(i=1;i<=9;i+)if(alinei=value) return 0;return 1;int row(int row,int value)/检验列int i;for(i=1;i<=9;i+)if(airow=value) return 0;return 1;int square(int line,int row,int value)/检验3*3的九宫int L,R,i,j;L=(line%3!=0)+line/3;/L表示所在九宫的行数R=(row%3!=0)+row/3;/R表示所在九宫的列数for(i=(L-1)*3+1;i<=L*3;i+)for(j=(R-1)*3+1;j<=R*3;j+)if(aij=value) return 0;return 1;/四个转换函数int transform_to_line(int i)/实现sdi->alinerow之间的转换int line;line=i/9+(i%9!=0);return line;int transform_to_row(int i)/实现sdi->alinerow之间的转换int row;row=i%9+9*(i%9=0);return row;void transform_to_a(int i)/sdi->alinerow的转换int l,r;l=transform_to_line(i);r=transform_to_row(i);alr=sdi;void transform_to_sd()/实现alinerow->sdi的转换int line,row,i=1;for(line=1;line<=9;line+)for(row=1;row<=9;row+)dosdi=alinerow;i+;break;while(i<=81);/输出函数void printAll()int i;for(i=0;i<81;i+)if(i%9=0)printf("nntt");printf("%4d",sdi+1);printf("nnn");void input()/输入数据到a1010system("cls");/清屏int b3=0,0,0,i,j;printf("请输入已知数据");printf("nn例如输入7 8 9，表示第8行 第9列的数值为7，以此类推。nnn");doprintf("n输入数据：按照 值 / 行 / 列的顺序，以0结束");for(i=0;i<3;i+)j=getch()-48;if(j=0&&i=0) break;/实现按0结束语句if(j>0&&j<10)bi=j;printf("%3d",bi);else i-;ab1b2=b0;while(j);transform_to_sd();printf("nnnt您输入的题目为:nn");/打印输入的数独printAll();/三个重要函数bool beExist(int i,int j)/判断 sd 数组中位置为 i 的元素是否存在int l,r;l=transform_to_line(i);r=transform_to_row(i);/if(sdi!=0) return 1; 关键的错误所在！if(line(l,j)*row(r,j)*square(l,r,j)=0) return 1;else return 0;void setPb()/控制possible数组int i,j;for(i=1;i<=81;i+)for(j=1;j<=9;j+)if(sdi!=0) possibleij=-1;/如果sdi为已知输入数据，则将可能值设为-1else if( beExist(i,j)possibleij=-1;/若在行、列、九宫内，存在相同数值则possible设为-1else possibleij=j;/其他情况讲可能值保存进possible数组bool fixAll(int sd,int fix,int possible8210)/控制fix数组int i,j;int k82;for(i=1;i<=81;i+)/将已经存在的数据对应fix数组中的值设为1，不存在设为0if(sdi!=0) fixi=1;else fixi=0;for(i=1;i<=81;i+)/判断未确定空格处值的可能性if(sdi!=0) continue;if(fixi=0)for(j=1;j<=9;j+)if(possibleij!=-1)ki+;if(ki=1)/如果存在只有一种可能的位置则将fixi改为1fixi=1;sdi=possibleij;for(i=1;i<=81;i+)/判断是否存在只有一种可能的位置，若没有返回0if(ki=1) return 1;else return 0;/判断是否完成int isFull(int sd)int i;for(i=1;i<=81;i+)if(sdi=0) return 0;return 1;void preDo()/预处理while(1)setPb();if(!fixAll(sd,fix,possible) /即不存在只有一种可能性的位置break;if(isFull(sd) /若已经推出全部结果break;if(isFull(sd)printAll();/打印结果int calculate()/填数独 (关键算法!)preDo();/预处理,找出所有的位置的可能数值if(isFull(sd) return 1;int top=0;/将所有为0的位置入栈for(int i=1;i<82;i+)if(fixi=0)stacktop+=i;int max=top;/记录最大数目加1top=0;/指向栈顶int temp;bool flag=true;/该标志位说明了当前是正常入栈while(1)assert(top>=0);/宏定义，调试程序之用if(flag)int j;for(j=1;j<=9;j+)if(possiblestacktopj!=-1&&!beExist(stacktop,j)/若top所示的位置上，可以安插j这个数值，则fixstacktop=1;sdstacktop=j;transform_to_a(stacktop);/实现alinerow与sdi同步变化+top;if(top>=max) return 1;break;if(j>9)/该空所有可能值都不可以，则退一格-top;if(top<0) printAll(); return 0;flag=false;elseif(sdstacktop=9)/说明当前这个top也没有可以选择的数，继续回退fixstacktop=0;sdstacktop=0;transform_to_a(stacktop);-top;if(top<0) printAll(); return 0;elsetemp=sdstacktop;temp+;while(possiblestacktoptemp=-1|beExist(stacktop,temp)temp+;if(temp>9)break;if(temp>9)/当前节点没有更换的可能性，继续退回fixstacktop=0;sdstacktop=0;transform_to_a(stacktop);-top;if(top<0) printAll(); return 0;elsesdstacktop=temp;transform_to_a(stacktop);+top;flag=true;/重新设定flagvoid solve_problem()/解题int p;system("cls"); /清屏clssd(); /赋初值为0input(); /输入数据transform_to_sd(); /转换为sdi数组p=calculate(); /计算数独if(p=0)printf("t题目有误! ");printf("nnt答案为：n");printAll();void random()/从1-9中随机产生几个值输入sd1至sd9int i,j,r;int change=1;int b10=0,0,0,0,0,0,0,0,0,0; for(i=1;i<=9;)/从1-9中随机产生几个值 change=1;j=1+rand()%9;for(r=1;r<=9;r+) if(br=j) change=0;if(change=1)bi=j; i+; for(i=1;i<=9;i+) sdi=bi;transform_to_a(i); void hide()/遮罩函数int i,f;printf("请输入难度:nn1.Easynn2.Normalnn3.Hardnn4.So Hardnn5.Terrible Hardnn");dof=getch()-48;while(f>5|f<1);/一共5个级别for(i=1;i<=81;i+)if(rand()%6>=f)/利用随机数出现的概率出题printf("%4d",sdi);elseprintf(" 0");if(i%9=0)printf("nn");void make_problem()/出题函数system("cls");/初始化clssd();random();/填9个随机值calculate();/算出答案hide();/遮罩，将答案中一些数值遮住printf("ttt注意：题目中0代表待填数据nntt 按空格键输出答案,其他键退出程序n");int f;dof=getch()-32;if(!f)printAll();else break;while(f);void main()/主函数srand(unsigned)time(0);/设置时间种子为0system("cls");/清屏clssd();printf("nt数独游戏nnt1.你出题，电脑来解nnt2.电脑出题，你来解");int i;doi=getch()-48;switch(i)case 1:solve_problem();break;case 2:make_problem();break;while(i>2|i<1);六 调试报告1. 整个程序最麻烦的地方是二维数组a1010与一维数组sd82之间的转换。因为输入数据为了方便和符合人类的思维采用了与数独相似的二维数组进行输入。但是回溯算法要求转换成一维数组进行操作。但是在回溯时每次判断是否一个未知数据是否可能或者是否存在的时候，均需要利用a1010数组进 行判断。所以a1010的功能不仅是接受输入数据。更加体现在回溯时的判断过程。所以调试过程中进行了很多两种数组之间转换的操作。为了方便，还专门建立了4个transform转换函数。2. 设计算法之初，是没有用到fix82数组的。后来在判断回溯与否时方便起见，引入了fix数组。思路清晰了许多，也提高了算法执行效率。3. 调试过程中，用到了一个宏命令assert（top>=0）top是栈顶元素的“指针”，用来操控栈中元素。正常情况下top>=0的。如果出现异常情况，则assert函数会弹出对话框报错。这表示calculate函数在回溯的时候top值总是会回到栈底元素之前。事实上，开始因为在beExist()函数中用了错误的判断方式，运行程序时总是会使得top<0。4. 上面一条提到的，beExist()中用到了错误的判断语句(/if(sdi!=0) return 1;)，这就是关键的错误所在。调试程序的时候总是会导致top<0却一直找不到为什么。开始以为是possible的值没有随着回溯算法的进行跟随sd的变化而变化，于是在每次sd变化之后都加上了一个setPb()函数，使得possible值每填一个数据就变化一次。但是导致的结果却是一旦开始回溯，必定会回溯到栈底之前。运用调试工具观察possible和top值的变化才发现。回溯的时候，之前填的空格处possible值都为-1，所以top每次都将回到栈底之前。于是以为是setPb()用的太多了，又重新删掉多余setPb()函数，结果还是一样。又经过几个小时的调试，终于发现是在calculate函数执行时，判断每次判断是否回溯都会运行函数beExist( )，调试时，进入beExist()函数发现，自己之前在写这个函数的时候想当然的把sdi!=0当作了判断已经存在（即beExist为真）的条件。直接导致top回溯到了栈底。于是屏蔽掉这条/if(sdi!=0) return 1之后，程序就基本可以正常运行了。5. 上一条中的错误之所以会出现，是因为在设计程序之初没有想好，不够完善。于是出现了，自己设计的判断方法与计算数独矛盾的结果。得到的教训是，动手之前应该先考虑清楚完整的架构和应该考虑到的细节。七 测试结果分析下面为规定测试数据：342172914579576231543182725419732531376852361