数独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.退 出"<<