数独sudoku的生成与破解.docx
- 文档编号:17196014
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:23
- 大小:74.63KB
数独sudoku的生成与破解.docx
《数独sudoku的生成与破解.docx》由会员分享,可在线阅读,更多相关《数独sudoku的生成与破解.docx(23页珍藏版)》请在冰点文库上搜索。
数独sudoku的生成与破解
数独(sudoku)的生成与破解
一、数独游戏的规则
数独(sudoku),起源于瑞士,于1970年代由美国的一家数学逻辑游戏杂志首先发表,当时名为NumberPlace。
及后在日本大力推广下得以发扬光大,于1984年取名“数独”,即“独立的数字”的省略,在一个9×9的方格中,有81个小方格组成,然后又分9个大块,每块由3x3的方格组成,就是中国的九宫阵。
游戏规则:
“九宫阵”是一个9×9的方阵,它是由九个“九宫格”(图中黑色实线围住的3×3的方阵)构成的,每个九宫格又是由九个小格子构成的,在每个小格子里面填上1~9中的数字,使得每个数字在“九宫阵”的每行、每列、每个九宫格中均只出现一次。
游戏开始前会有一些格子上写好了数,你需要在剩下的格子里填数,真到把所有格子填满,并且要求,任何一行或一列或者一个小九宫中没有相同的数字,当然你只能用1~9之间的9个数字。
如下图就是一个数独游戏。
题 目 答 案
二、数独(sudoku)的生成
基本思路:
为了保证生成的数独一定有解,就要先得到了一个完整的数独(可以想象所有满足条件的组合是很多的),然后从格子里面随机挖掉一些数字就可以了。
那么如何得到一个完整数独呢?
我们可以这样想先给每一行(或列)填入一个不同的数,然后用“数独破解”的方法去完成,这就OK了。
步骤如下:
1.在第i行(i=0~8)随机找个格子map[i][j](j=0~8)填入本行数i+1;
2.用“数独求解”(见数独(sudoku)的生成)的方法产生一个完整数独;
3.从81个格子里面随机挖去n个数字。
三、数独(sudoku)的破解
我们可以想象每个格子可填入的数字是可以得知的,但这不是唯一的,应先填入哪个数字就是个问题,另外先填哪一个格子也是不确定的,那么如何开始填才最佳呢?
这里我们需要引入一个概念——格子的不确定度,一个格子可以填的数字的个数称为它的不确定度。
所以我们需要用递归下面的做法:
1.我们去寻找不确定度最小的格子;
2.确定这个格子可以填的数字;
3.填入一个数字后,递归。
随着填上去数字增多,剩余空格上的不确定度也会降低,如果某个格子上的不确定度降到1,那这个格子可以先确定下来,如果降到了0,哦,非常遗憾,在前面的填数中一定是填错了,你不得不回退。
四、唯一解的问题
这里有一问题,我们需要的是我们生成的数独是否具有唯一解?
是的,按上面数独生成的过程是不能保证的。
为了保证数独有唯一解,应该从哪儿考虑呢?
我的思路是:
从完整数独中挖格子的过程中去分析。
根据数独破解的方法,在破解过程中每次要寻找的最小不确定度的那个格子,如果每次找到的这个格子可填的数字都仅为1个(最小不确定度为1)时,那么得到的解一定唯一。
这样就给我们启发,我们在挖格子时,每挖一个格子,也去检测最小不确定度的格子的不确定度。
如果这个不确定度大于1,则就要重新这次挖格子。
另外也有可能挖遍所有的格子(程序中我设的上限是81次)也没有合适解时,那么要中止这次操作,这时就要从重新生成一个数独。
五、游戏的难易程序
这个问题我是这么考虑的,只要生成的数独中的空格数(blank)越多,那么就越难。
所以在些程序中我设置三个级别:
1 容易:
blank=33~35;
2 中等:
blank=36~38;
3 困难:
blank=39~41;
六、源程序
#ifndefSUDOKU_RICK_0701_
#defineSUDOKU_RICK_0701_
classCSudoku
{
intmap[9][9];
intblanks;
intsmod;
intsolves;
intcheck(int,int,int*);
voiddfs();
public:
enum{ANY=0,ALL=1};
CSudoku(int);
CSudoku:
:
CSudoku(int*data);
voidSudokuGenerator(int); //随机生成数独,n越大越难
voidSudokuGenerator(int*data); //人工指定数独
//virtual~CSudoku();
voiddisplay(); //显示数独
intresolve(intmod=ALL); //解数独
voidanalyze();
};
#endif
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#include"iostream"
#include"iomanip" //要用到格式控制符
usingnamespacestd;
CSudoku:
:
CSudoku(intn)
{
intj;
j=rand()%3;
blanks=n+j;
SudokuGenerator(blanks);
cout< "< //cout<<(空格子数为"< display(); cout<<"pressentertocontinue! "< getchar(); getchar(); while (1) { cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"< cout<<" %% 请选择您的操作: %%"< cout<<" %%============================%%"< cout<<" %% %%"< cout<<" %% 1.显示当前数独 %%"< cout<<" %% 2.分析求解 %%"< cout<<" %% 3.查看结果 %%"< cout<<" %% 4.返 回 %%"< cout<<" %% %%"< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"< intselect; cin>>select; switch(select) { case1: { cout< "< display(); cout<<"pressentertocontinue! "< getchar(); getchar(); break; } case2: { analyze(); break; } case3: { cout< "< resolve(); cout<<"pressentertocontinue! "< getchar(); getchar(); break; } case4: return; default: { cout<<"输入错误,请重新输入."< break; } } } } CSudoku: : CSudoku(int*data) { SudokuGenerator(data); cout< "< display(); cout<<"pressentertocontinue! "< getchar(); getchar(); analyze(); } voidCSudoku: : SudokuGenerator(intn) { inti,j; intmark[10]; srand(time(0)); //每一行i产生一个随机位置(列j)并置为当前行值i+1,0= do { for(i=0;i<9;++i) { for(j=0;j<9;++j) map[i][j]=0; j=rand()%9; map[i][j]=i+1; } //display(); } while(! resolve(ANY)); //生成完整的随机Sudoku表格 //挖窟窿 for(intk=0;k { inttmp,flag=0,sum=1; do { // cout<<"sum="< if(sum++>81) { SudokuGenerator(n); return; } if(flag==1) map[i][j]=tmp; do { i=rand()%81; j=i%9; i=i/9; } while(map[i][j]==0); tmp=map[i][j]; map[i][j]=0; flag=1; } while(check(i,j,mark)>1); } } voidCSudoku: : SudokuGenerator(int*data) { int*pm=(int*)map; for(inti=0;i<81;++i) pm[i]=data[i]; } voidCSudoku: : display() { printf("┏━┯━┯━┳━┯━┯━┳━┯━┯━┓\n"); for(inti=0;i<9;++i) { for(intj=0;j<9;++j) { if(map[i][j]>0) { if(j%3==0) printf("┃%d",map[i][j]); else printf("│%d",map[i][j]); } else { if(j%3==0) printf("┃ "); else printf("│ "); } } printf("┃\n"); if(i! =8) { if((i+1)%3==0) printf("┣━┿━┿━╋━┿━┿━╋━┿━┿━┫\n"); else printf("┠─┼─┼─╂─┼─┼─╂─┼─┼─┨\n"); } } printf("┗━┷━┷━┻━┷━┷━┻━┷━┷━┛\n"); } intCSudoku: : resolve(intmod) { smod=mod; if(mod==ALL) { solves=0; dfs(); returnsolves; } elseif(mod==ANY) { try { dfs(); return0; } catch(int) { return1; } } return0; } intCSudoku: : check(inty,intx,int*mark) { inti,j,is,js,count=0; for(i=1;i<=9;++i) mark[i]=0; for(i=0;i<9;++i) mark[map[y][i]]=1; for(i=0;i<9;++i) mark[map[i][x]]=1; is=y/3*3; js=x/3*3; for(i=0;i<3;++i) { for(j=0;j<3;++j) mark[map[is+i][js+j]]=1; } for(i=1;i<=9;++i) if(mark[i]==0) count++; returncount; } voidCSudoku: : dfs() { inti,j,im=-1,jm,min=10; intmark[10]; // display(); //求自由度最小的格map[im][jm] for(i=0;i<9;++i) { for(j=0;j<9;++j) { if(map[i][j]) //如果此格已填入数则看一下格。 continue; intc=check(i,j,mark); //如果此格空,则求其自由度。 if(c==0) //已到结尾,没有空格了。 return; if(c { im=i; jm=j; min=c; } } } if(im==-1) //若im=-1,则格子都填满。 { if(smod==ALL) //smod==ALL是求解过程。 { //printf("No.%d: \n",++solves); display(); return; } elseif(smod==ANY) //smod==ANY是初始化过程。 { throw (1); } } check(im,jm,mark); for(i=1;i<=9;++i) { if(mark[i]==0) { map[im][jm]=i; //从小到大让第一个可填的数填入自由度最小的格。 dfs(); } } map[im][jm]=0; return; } voidCSudoku: : analyze() { while (1) { cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"< cout<<" %% 请问你想做什么? %%"< cout<<" %%============================%%"< cout<<" %% %%"< cout<<" %% 1.查找最小不确定度的格子%%"< cout<<" %% 2.指定格子的可填数 %%"< cout<<" %% 3.给指定格子填数 %%"< cout<<" %% 4.显示当前数独 %%"< cout<<" %% 5.查看结果 %%"< cout<<" %% 6.返 回 %%"< cout<<" %% %%"< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"< intselect; cin>>select; switch(select) { case1: //求不确定度最小的空格map[im][jm] { inti,j,im=-1,jm,min=10; intmark[10]; for(i=0;i<9;++i) { for(j=0;j<9;++j) { if(map[i][j]) //如果此格已填入数则看一下格。 continue; intc=check(i,j,mark); //如果此格空,则求其不确定度。 if(c==0) { cout<<"不能得到结果或已无空格子! 自动返回! "< return; } if(c { im=i; jm=j; min=c; } } } cout< ["< "< cout<<"pressentertocontinue! "< getchar(); getchar(); break; } case2: { intx,y; intmark[10]; cout< 24,中间用空格.): [x,y]="; cin>>x>>y; getchar(); while(map[x][y]! =0) { cout< 此格已经有数! 请重新输入."< cout<<"请重新输入格子位置(如[2,4],则输入: 24,中间用空格.): [x,y]="; cin>>x>>y; getchar(); } inti,j,is,js,count=0; for(i=1;i<=9;++i) mark[i]=0; for(i=0;i<9;++i) mark[map[x][i]]=1; for(i=0;i<9;++i) mark[map[i][y]]=1; is=x/3*3; js=y/3*3; for(i=0;i<3;++i) { for(j=0;j<3;++j) mark[map[is+i][js+j]]=1; } cout< "; for(i=1;i<=9;++i) if(mark[i]==0) { count++; cout< } cout< cout<<"pressentertocontinue! "< getchar(); break; } case3: { intx,y; cout< 24,中间用空格.): [x,y]="; cin>>x>>y; cout<<"请输入要填入的数: "; cin>>map[x][y]; cout<<"您填入的格为: map["< cout<<"pressentertocontinue! "< getchar(); getchar(); break; } case4: { cout< "< display(); cout<<"pressentertocontinue! "< getchar(); getchar(); break; } case5: { cout< "< resolve(); //没有输入参数,则默认为smod==ALL,见程序开始函数声明。 cout<<"pressentertocontinue! "< getchar(); getchar(); break; } case6: return; default: { cout<<"输入错误,请重新输入."< break; } } } } voidmain() { intblanks; while (1) { boolexit_f=true; cout< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%"< cout<<" %% SUDOKU游戏 %%"< cout<<" %% 任二艳制作 %%"< cout<<" %%=====================%%"< cout<<" %% 1.新游戏 %%"< cout<<" %% 2.退 出 %%"< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%"< intselect; cin>>select; switch(select) { case1: //开始新游戏 { while(exit_f) { cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%"< cout<<" %% 请选择游戏难度 %%"< cout<<" %%=====================%%"< cout<<" %% %%"< cout<<" %% 1.简 单 %%"< cout<<" %% 2.中 等 %%"< cout<<" %% 3.困 难 %%"< cout<<" %% 4.返 回 %%"< cout<<" %% %%"< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%"< /* cout< "< cout<<"======================="< cout<<"1.简 单"< cout<<"2.中 等"< cout<<"3.困 难"< cout<<"4.解一个已知数独"< cout<<"5.退 出"<<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- sudoku 生成 破解