数独程序设计与相关代码.

1、数独程序设计：l 主要思想是：先设计出一个符合规则的终局，再覆盖掉其中的一些数据作为初局，以已知数据的数目区分等级l 主要过程是：l 用a1010 来接收输入数据的数组，先初始化为0l 用一维数组deal82处理题目，并且保存最终结果l 用fix82记录哪些位置是确定的，确定为1，否则为0l 用nsure8210记录所有未确定数字的可能性，第一维下标是元素在deal中的位置，第二维是此元素的可能值l 用b82 来放置fix为0即未确定元素的位置,实现回溯算法数独程序代码：l #includel #includel #includel int a1010;l int deal82;l int f

2、ix82;l int nsure8210;l int b82;l int main()/主函数l l srand(time(0);/设置时间种子为0l start(); /出题函数l return 0;l l void set()/初始化函数，所有位置设为0l l int i,j,k;l l for(i=0;i9;i+)l for(j=0;j9;j+)l aij=0;l for(k=1;kalinerow的转换l l int l,r;l l= transform_to_line(i) ; /获得i所在的行l r= transform_to_row(i) ; /获得i所在的列l alr=deal

3、i;l l void random()/从1-9中随机产生几个值输入deal1至deal9l l int i,j,r;l int change=1;/标记l int b10=0,0,0,0,0,0,0,0,0,0;l for(i=1;i=9;)/从1-9中随机产生9个不同的值l l change=1;l j=1+rand()%9;/产生一个19的数l for(r=1;r=9;r+)l if(br=j) change=0;/有重复的就舍弃l if(change=1)l bi=j; i+;l l for(i=1;i=9;i+)l l deali=bi;/将b中元素存入deal中l transfor

4、m_to_a(i);/deal中数存入al l l int line(int line,int value)/检验行l l int i;l for(i=1;i=9;i+)l l if(alinei=value) return 0;/不符合规则返回0l l return 1;l l int row(int row,int value)/检验列l l int i;l for(i=1;i=9;i+)l l if(airow=value) return 0;l l return 1;l l int square(int line,int row,int value)/检验3*3的九宫l l int L

5、,R,i,j;l L=(line%3!=0)+line/3;/L表示所在九宫的行数l R=(row%3!=0)+row/3;/R表示所在九宫的列数l for(i=(L-1)*3+1;i=L*3;i+)l l for(j=(R-1)*3+1;j=R*3;j+)l if(aij=value) return 0;l l return 1;l l int beExist(int i,int j)/判断数组中位置为 i 的元素是否已确定l l int l,r;l l=transform_to_line(i); /获得第i个数在a中的行l r=transform_to_row(i); /获得第i个数在a中

6、的列l if( line (l,j)*row(r,j)*square(l,r,j)=0 ) l return 1;/不合规则返回1l else l return 0;l l void setPb()/通过nsure数组确定各个位置的可能值l l int i,j;l for(i=1;i=81;i+)/i为deal中位置为i的元素l l for(j=1;j=9;j+)/j为19的可能值，不可能为j的设为-1l l if(deali!=0) nsureij=-1;/若deali已输入数据，则将可能值设为-1l l else if( beExist(i,j) ;/若在行、列、九宫内，存在相同数值则ns

7、ure设为-1（即j不可能）l nsureij=-1; l l elsel nsureij=j;/其他情况将可能值保存进nsure数组l l l l /通过fix标记已确定位置，确定部分deal中元素的值，判断是否存在只有一种可能性的位置l int fixAll(int b,int fix,int nsure8210)l l int i,j;l int k82;/记录位置为i的元素可能值个数l for(i=1;i=81;i+)/将已经存在的数据对应fix数组中的值设为1，不存在设为0l l if(deali!=0)l fixi=1;l elsel fixi=0;l l for(i=1;i=81

8、;i+)/判断未确定空格处值的可能性l l if(fixi=0)l l for(j=1;j=9;j+)l if(nsureij!=-1)l ki+;l if(ki=1)/如果存在只有一种可能的位置则将fixi改为1l l fixi=1;l deali=nsureij;/将该可能值存入deall l l l for(i=1;i=81;i+)/判断是否存在只有一种可能的位置，若没有返回0l l if(ki=1) l return 1;l else l return 0;l l l /判断是否完成l int isFull(int deal)l l int i;l for(i=1;i=81;i+)l

9、if(deali=0) return 0;l return 1;l l /输出函数l void print()l l int i;l for(i=0;i81;i+)l l if(i%9=0)l printf(nntt);l printf(%4d,deali+1);l l printf(nnn);l l void preDo()/预处理，结果是已推出全部结果或已填满只有一种可能性的位置l l while(1)l l setPb();/ 获得各个位置的可能值，不断更新nsure中的值l if(!fixAll(deal,fix,nsure) /即不存在只有一种可能性的位置l break;l if(i

10、sFull(deal) /若已经推出全部结果l break;l l if(isFull(deal)l print(); /打印结果l l int complete() /填数独l l int top=0,max,temp,flag=1,i;l preDo(); /找出所有的位置的可能数值l if( isFull(deal) ) return 1;l for(i=1;i82;i+)/找出所有未确定元素的位置l l if(fixi=0)l btop+=i;l l max=top;/记录最大数目加1l top=0;/指向栈顶l while(1)l l if(flag)l l int j;l for(

11、j=1;j=max) return 1;l break;l l if(j9)/该空所有可能值都不可以，则退一格l l -top;l if(top0) print(); return 0;l flag=0;l l l elsel l if(dealbtop=9)/说明当前这个top也没有可以选择的数，继续回退l l fixbtop=0;l dealbtop=0;l transform_to_a(btop);l -top;l if(top9)l break;l l if(temp9)/当前节点没有更换的可能性，继续退回l l fixbtop=0;l dealbtop=0;l transform_t

12、o_a(btop);l -top;l if(top0) print(); return 0;l l elsel l dealbtop=temp;l transform_to_a(btop);l +top;l flag=1;/重新设定flagl l l l l l void hide()/遮罩函数l l int i,f;l printf(请选择难度:nn1.初级nn2.中级nn3.高级nn);/一共3个级别l f=getchar()-48;l for(i=1;i=f)/利用随机数出现的概率，05的数分别比1,2,3大的概率l printf(%4d,deali);l elsel printf( 0);l if(i%9=0)l printf(nn);l l l void start()/出题函数l l int f;l set();