资源描述:
《数独游戏 c++ 回溯法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、indoc.in数独游戏C++回溯法 数独游戏的规则: 1每个数字在每一行只能出现一次 2每个数字在每一列只能出现一次 3每个数字在每一区只能出现一次 下面的input.txt是一个例子的约束条件第一列表示每一个数所在的行第二列表示每一个数所在的列,第三个这个位置上的值。 Input.txt 117 141 188文章内容版权归原作者所有VICHU.NETindoc.in 193 214 232 257 263 344 355 382 397 437 473文章内容版权
2、归原作者所有VICHU.NETindoc.in 481 492 524 533 548 635 659 722 731 758 823文章内容版权归原作者所有VICHU.NETindoc.in 842 861 878 972 986 991 一回溯法 //============================================ #include #include usingnamespacestd;文章内容版权归原作者所有VICHU.NETindoc
3、.in intState[9][9]; ///------------------------------ voidInitState() { for(inti=0;i<9;i++) { for(intj=0;j<9;j++) { State[i][j]=0; } }文章内容版权归原作者所有VICHU.NETindoc.in } //------------------------------- voidLoad() { freopen("input.txt","r",stdi
4、n);//输入从input.txt intx,y,value; inttemp=0; while(scanf("%d%d%d",&x,&y,&value)!=EOF) { State[x-1][y-1]=value; }文章内容版权归原作者所有VICHU.NETindoc.in } //--------------------------------- //检查每一个小区内只能出现一次 boolChechZone(intx,inty,inti) { intxZone=3*(x/3);/
5、/找到每个小区的位置 intyZone=3*(y/3); intj=0; intk=0; boolflag=true; for(j=xZone;j
{文章内容版权归原作者所有VICHU.NETindoc.in for(k=yZone;k<> { //if(x==j&&y==k) //{ //continue; //} if((x!=j
6、
7、y!=k)&&State[j][k]==i) { flag=false; gotoA1; }文章内容版权归原作者所有VICHU.NET
8、indoc.in } } A1: returnflag; } //-------------------------------- //检查是否符合条件 boolChechAssign(intx,inty,inti) { boolflag=true;文章内容版权归原作者所有VICHU.NETindoc.in for(intk=0;k<9;k++) { if(k!=y&&i==State[x][k]) { flag=false; } if(k!=x&&i==State[k][y
9、]) { flag=false; } if(!ChechZone(x,y,i))文章内容版权归原作者所有VICHU.NETindoc.in { flag=false; } } returnflag; } ///------------------------------ intSearch(intdepth) { if(depth>=81) {文章内容版权归原作者所有VICHU.NETindoc.in //returnChech(); return1; } intx,y;
10、 x=depth/9; y=depth%9; //检查xy有没有被赋值 if(0!=State[x][y]) { returnSearch(depth+1); }文章内容版权归原作者所有VICHU.NETindoc.in else//尝试赋值 { for(inti=1;i<=9;i++) { //检查是否违反约束条件 State[x][y]=i; if(ChechAssi