如果确定了，fix值为1游戏图片素材，不确定则为0。int possible[82][10]第一维对应sd[82]中的每一个，第二维的下标为各个位置的可能值，如果可能则为第二维的下标，不可能则为-1。int stack[82]是一个类似“栈”数据结构的数组，它是实现“回溯”算法的关键。在回溯前，会把fix值为0的所有数据都存入stack数组中，也就是压入栈中。在回溯过程中，会逐步确定这些位置的值，如果无法确定（即1--9不适合），则要回滚到之前的位置并修改它们的fix值，以此类推。直到栈中所有值都确定（即问题完成），或者回滚到初始点之前的位置（表示问题错误）。算法设计程序可以考虑人工智能的算法，所谓人工智能算法，应该是算法设计者对游戏的特点有更深入的了解，根据其内部的联系，设计出类似人类思维的解决算法。但这似乎太复杂了，所以这里我们决定采用“回溯”法来解决数独问题。基本框架如下：“用回溯法计算数独，将数据从接口读到a[10][10]进行预处理，计算所有fix和可能的值，将a[10][10]中的数据传送到sd[82]中。”用回溯法计算数独，将数据从接口读到a[10][10]进行预处理数独游戏设计，计算所有fix和可能的值。 a[10][10]中的数据被传输到sd[82]中 5、数独程序代码： #includestdio.h //标准输入输出头文件 #includeconio.h //包含getch()的头文件 #includestdlib.h //包含rand()的头文件 #includeassert.h //包含assert()的头文件 #includetime.h //包含srand()的头文件 //五个全局变量数组 int a[10][10]; //用于接收输入数据的数组 int sd[82]; //处理题意，并保存最终结果 int fix[82]; //记录哪些位置是固定的，如果固定则为1，否则为0 int possible[82][10]; //记录所有未确定数字的可能性 int stack[82]; //用于放置填充数字的堆栈 void clssd() //初始化函数，所有位置都设置为0 {int i,j,k;for(i=0;i9;i++)for(j=0;j9;j++)a[i][j]=0;for(k=1;k=81;k++)sd[k]=0;}int line(int line,int value)//检查行{int i;for(i=1;i=9;i++){if(a[line][i]==value) return 0;}return 1;}int row(int row, int value)//测试列{int i;for(i=1;i=9;i++){if(a[i][row]==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(a[i][j]==value) return 0;}return 1;}//四个变换函数int transform_to_line(int i)//实现sd[i]-a[line][row]{int line;line=i/9+(i%9!=0);return line;}int transform_to_row(int i)//实现sd[i]-a[line][row]{int之间的变换row;row=i%9+9*(i%9==0);return row;}void transform_to_a(int i)//sd[i]-a[line][row]的转换{int l,r;l=transform_to_line(i);r=transform_to_row(i);a[l][r]=sd[i];}void transform_to_sd()//a[line][row]-sd[i]的转换{int line,row,i=1;for(line=1;line=9;line++)for(row=1;row= 9;row++)do{sd[i]=a[line][row];i++;break;}while(i=81);}//输出函数 void printAll(){int i;for(i=0;i81;i++){if(i%9==0)printf(\n\n\t\t);printf(%4d,sd[i+1]);}printf(\n\n\n);}void input()//输入数据到a[10][10]{system(cls);//清屏int b[3]={0,0,0},i,j;printf(请输入已知数据);printf(\n\n例如输入7 8 9，代表第8行第9列的值为7，其它的以此类推。
\n\n\n);do{printf(\n输入数据：按照值/行/列的顺序，以0结尾);for(i=0;i3;i++){j=getch()-48;if(j==0i==0) break;//执行以0结尾的语句if(j0j10){b[i]=j;printf(%3d,b[i]);}else i--;}a[b[1]][b[2]]=b[0];}while(j);transform_to_sd();printf(\n\n\n\t您输入的标题是:\n\n);//打印输入的数独printAll();}//三个重要函数bool beExist(int i,int j)//判断sd数组中位置i处的元素是否存在{int l,r;l=transform_to_line(i);r=transform_to_row(i);//if(sd[i]!=0) return 1; 关键错误！！！ if(line(l,j)*row(r,j)*square(l,r,j)==0) return 1;else return 0;}void setPb()//控制可能数组{int i,j;for(i=1;i=81;i++){for(j=1;j=9;j++){if(sd[i]!=0) possible[i][j]=-1;//如果sd[i]为已知输入数据，则将可能值设为-1else if( beExist(i,j)){possible[i][j]=-1;}//如果行、列、九宫格中有相同的值，则将可能值设为-1else{possible[i][j]=j;}//其它情况，将可能值存入可能数组}}}bool fixAll(int sd[],int fix[],int possible[82][10])//控制修复数组{int i,j;int k[82];for(i=1;i=81;i++)//将已经存在的数据对应的fix数组的数值设置为1，不存在则设置为0{if(sd[i]!=0) {fix[i]=1;}else {fix[i]=0;}}for(i=1;i=81;i++)//判断未确定空间处数值的可能性{if(sd[i]!=0) continue;if(fix[i]==0){for(j=1;j=9;j++)if(possible[i][j]!=-1)k[i]++;}if(k[i]==1)//如果只有一个可能的位置，就将fix[i]改为1fix[i]=1;sd[i]=possible[i][j];}for(i=1;i=81;i++)//判断是否只有一种可能的位置，如果没有，则return 0{if(k[i]==1) return 1;else return 0;}}//判断是否完成int isFull(int sd[]){int i;for(i=1;i=81;i++)if(sd[i]==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;i82;i++){if(fix[i]==0)stack[top++]=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(possible[stack[top]][j]!=-1!beExist(stack[top],j))//如果在top所示位置能插入值j，则{fix[stack[top]]=1;sd[stack[top]]=j;transform_to_a(stack[top]);//实现a[line][row]与sd[i]++top的同步变化;if(top=max) return 1;break;}if(j9)//这个空间所有可能的值都不行，所以后退{--top;if(top0) {printAll(); return 0;}flag=false;}}else{if(sd[stack[top]]==9)//说明当前top中没有数字可以选择，所以继续后退{fix[stack[top]]=0;sd[stack[top]]=0;transform_to_a(stack[top]);--top;if(top0) {printAll(); return 0;}}else{temp=sd[stack[top]];temp++;while(possible[stack[top]][temp]==-1||beExist(stack[top],temp)){temp++;if(temp9)break;}if(temp9)//没有改变当前节点的可能，所以继续后退{fix[stack[top]]=0;sd[stack[top]]=0;transform_to_a(stack[top]);--top;if(top0) {printAll(); return 0;}}else{sd[stack[top]]=temp;transform_to_a(stack[top]);++top;flag=true;//重置标志}}}}}voidsolve_problem()//解决问题{int p;system(cls); //清屏clssd(); //赋初值为0input(); //输入数据transform_to_sd(); //转换为sd[i]数组p=calculate(); //计算数独if(p==0)printf(\t题错了！！！);printf(\n\n\t答案是：\n);printAll();}void random()//从1-9中随机生成几个值inputsd[1] to sd[9]{int i,j,r;int change=1;int b[10]={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(b[r]==j) change=0;if(change==1){b[i]=j; i++;} }for(i=1;i=9;i++) {sd[i]=b[i];transform_to_a(i); }}void hide()//掩码函数{int i,f;printf(请输入难度:\n\n1.Easy\n\n2.Normal\n\n3.Hard\n\n4.So Hard\n\n5.Terrible Hard\n\n);do{f=getch()-48;}while(f5||f1);//共5个等级for(i=1;i=81;i++){if(rand()%6=f)//利用随机数的概率出题printf(%4d,sd[i]);elseprintf( 0);if(i%9==0)printf(\n\n);}}void make_problem()//出题函数{system(cls);//初始化clssd();random();//填写9个随机值calculate();//计算答案hide();//掩码，遮住部分值答案printf(\t\t\t注意：题目中的0代表需要填写的数据\n\n\t\t按空格键输出答案，其他键退出程序\n);int f;do{f=getch()-32;if(!f)printAll();else break;}while(f);}void main()//主函数{srand((unsigned)time(0));//设置时间种子为0system(cls);//清屏clssd();printf(\n\t数独游戏\n\n\t1、你出题，计算机解题\n\n\t2、计算机出题，你解题);int i;do{i=getch()-48;switch(i){case 1:solve_problem();break;case 2:make_problem();break;}}while(i2||i1);}调试报告整个程序最麻烦的地方就是二维数组a[10][10]与一维数组sd[82]之间的转换。
因为输入数据为了方便也符合人的思维，都是用类似数独的二维数组来输入的。但是回溯算法需要转换成一维数组进行操作。但是在回溯的时候，每次判断一个未知的数据是否可能或者存在，都需要用到a[10][10]这个数组来判断。所以a[10][10]的作用不仅仅是接受输入数据。更多的体现在回溯时的判断过程。所以在调试过程中，两个数组之间转换的操作很多。为了方便，特意建立了4个transform转换函数。在算法设计之初，并没有用到fix[82]数组，后来为了方便判断是否回溯，才引入了fix数组。思路清晰了很多，算法执行效率也提高了。在调试过程中，用到了一个宏命令assert(top=0)。top是栈顶元素的“指针”，用来操作栈中的元素。正常情况下top=0，如果出现异常情况assert函数会弹出对话框报错3D交通工具，意思是calculate函数的top值在回溯的时候永远会回到栈底元素。其实一开始因为beExist()函数中的判断方法错误，导致程序运行时总是到达top0，上一点提到了beExist()中使用了错误的判断语句（//if(sd[i]!=0) return 1）
