资源预览内容
第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
第6页 / 共17页
第7页 / 共17页
第8页 / 共17页
第9页 / 共17页
第10页 / 共17页
亲,该文档总共17页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构大型作业实验报告书设计题目:“数独”游戏设计与求解一 题目说明 数独的游戏规则:1、 在99的大九宫格内,已给定若干数字,其他宫位留白,玩家需要自己按照逻辑推敲出剩下的空格里是什么数字。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五数独程序代码:#includestdio.h /标准输入输出头文件#includeconio.h /包含getch()的头文件#includestdlib.h /包含rand()的头文件#includeassert.h /包含assert()的头文件#includetime.h /包含srand()的头文件/五个全局变量数组int a1010;/用来接收输入数据的数组int sd82;/处理题目以及保存最终结果int fix82;/记录哪些位置是确定的,确定为1,否则为0int possible8210;/记录所有未确定数字的可能性int stack82;/用来放置填入的数的栈void clssd()/初始化函数,所有位置设为0int i,j,k;for(i=0;i9;i+)for(j=0;j9;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;jalinerow之间的转换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;i81;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;i0&j10)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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号