数独(sudoku)的生成与破解最近在网上比较流行的智力游戏。笔者本人也玩过，可以下个模拟游戏试试，简单的还可以，太难就无从下手了。虽然偶脑子不好使，但偶是计算机科班出身，怕你不成，老规矩，编程破解。 首先，偶是第一次做数独的程序，可能程序不强，以后有时间再改进改进。望高手评析。 还是把数独游戏的规则说一说吧，或许你是刚刚听说这个名字的朋友。数独(sudoku)，起源于瑞士，于1970 年代由美国的一家数学逻辑游戏杂志首先发表，当时名为Number Place。及后在日本大力推广下得以发扬光大，于1984 年取名“数独”，即“独立的数字”的省略，在一个9x9的方格中，有81个小方格组成，然后又分9个大块，每块由3x3的方格组成，就是中国的九宫图，大九宫里面再套9个小九宫，共九九八十一个小格子，游戏开始前会有一些格子上写好了数，你需要在剩下的格子里填数，真到把所有格子填满，并且要求，任何一行或一列或者一个小九宫中没有相同的数字，当然你只能用1-9之间的9个数字。如下图就是一个数独。希望我解释清楚了，如果你还不清楚，用google搜索一下相关资料，点这里http://www.google.com/search?q=sudoku%20%E6%95%B0%E7%8B%AC&hl=zh-CN&lr=&nxpt=10.1471893728569764719035 好啦，言归正传。简单来说，我的破解法非常简单，就是超级无敌强硬大搜索，呵呵，别拿你想数独的那套来让计算机想，它比你可笨得多了，它只会照程序做事，做得快而已，快就是它的本事，其它的一概不会。 核心算法：深度优先搜索（其它形式的搜索也可以） 数据结构：如果用递归的形式写深搜，定义在函数dfs里的所有变量都可以看成是这里的数据结构，因为它们自动地被系统压入栈内，所以，省了，你唯一要做的就是一个二维数组，存放当前数独的状态。 当然有了这些，偶还不敢动手做，如果你做过马遍历的程序，大概会有点怕，那才8x8，这里是9x9，不来点‘启发式’谁敢动手写程序，有可能一个数独来几千几万个解，一个解要搜80层上下（估计），懂得树这个数据结构的人就会明白，80层是什么概念，1-9有9个数字，就是9叉树，至少是9^80量级的代价，什么？计算机反正算得快？也不行，再快的计算机遇到指数复杂度的程序也得变回傻子！谢天谢地，棋局尺寸是固定不变的，我们需要做的就是，剪枝。 偶的启发式思想来源于偶想数独的思路，数独之所以难是因为可行情况太多，把这种不确定性降低就会使它变得简单。某个格子上可以填的数字的个数就称为它的不确定度吧，首先，如果一开始空格比较少，那空格上的不确定度就小，数独也就相对容易，同时，随着填上去数字增多，剩余空格上的不确定度也会降低，如果某个格子上的不确定度降到1，那这个格子可以先确定下来，如果降到了0，哦，非常遗憾，在前面的填数中一定是填错了，剪枝也发生在这里，你不得不回退。 详细地说，如果把每个空格做为分枝，那要优先选择哪个分枝进行搜索呢？对每个空格计算它的权值，也就是它的不确定度，然后从中选出最小的一个进行搜索，同时放弃其它空格在这一层上的搜索！也就是说对剩余的空格交给子层处理。这样在某一个结点上的处理就包括两步：1，选择最佳空格，2，遍历这个空格的所有可行值，填入空格，递归。 OK，看程序： #ifndef SUDOKU_RICK_0701_#define SUDOKU_RICK_0701_class CSudoku{ int map[9][9]; int solves; int check(int,int,int*); void dfs();public: CSudoku(int n=40);// 随机生成数独,n越大越难 CSudoku(int *data);// 人工指定数独 virtual ~CSudoku(); void display();// 输出数独 void resolve();// 解数独};#endif #include "sudoku.h"#include "stdio.h"#include "stdlib.h"#include "time.h" CSudoku::CSudoku(int n){ int i,j,k,m,mark[10],temp,blanks=0; srand(time(0)); for(i=0;i<9;++i) {  for(j=0;j<9;++j)   map[i][j]=j+1;  for(j=0;j<9;++j)  {   int a=rand()%9;   int b=rand()%9;   temp=map[i][a];   map[i][a]=map[i][b];   map[i][b]=temp;  } } for(i=0;i<9;++i) {  for(j=1;j<=9;++j)   mark[j]=0;  for(j=0;j<9;++j)  {   if(mark[map[j][i]])   {    for(k=8;k>=0;--k)    {     if(mark[map[j][k]]==0)     {      temp=map[j][i];      map[j][i]=map[j][k];      map[j][k]=temp;      break;     }    }   }   else   {    mark[map[j][i]]=1;   }  } } for(i=0;i<9;++i) {  for(j=1;j<=9;++j)   mark[j]=0;  for(j=8;j>=0;--j)  {   if(mark[map[j][i]])   {    map[j][i]=0;    blanks++;   }   else    mark[map[j][i]]=1;  } } for(i=0;i<9;i+=3) {  for(j=0;j<9;j+=3)  {   for(k=1;k<=9;++k)    mark[k]=0;   for(k=0;k<3;++k)   {    for(m=0;m<3;++m)    {     if(map[i+k][j+m]==0)      continue;     if(mark[map[i+k][j+m]])     {      map[i+k][j+m]=0;      blanks++;     }     else      mark[map[i+k][j+m]]=1;    }   }  } } while(n>blanks) {  m=rand()%81;  i=m/9;  j=m%9;  if(map[i][j]>0)  {   map[i][j]=0;   blanks++;  } } printf("(randomized sudoku created with %d blanks.)\n",blanks);}CSudoku::CSudoku(int *data){ int *pm=(int*)map; for(int i=0;i<81;++i)  pm[i]=data[i];}CSudoku::~CSudoku(){ return;}void CSudoku::display(){ for(int i=0;i<9;++i) {  for(int j=0;j<9;++j)  {   if(map[i][j]>0)    printf("< %d >  ",map[i][j]);   else    printf("[   ]  ");  }  printf("\n"); }}void CSudoku::resolve(){ solves=0; dfs(); if(solves==0)  printf("(sorry,this sudoku is a bad one.)\n");}int CSudoku::check(int y,int x,int *mark){ int i,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++; return count;}void CSudoku::dfs(){ int i,j,im=-1,jm,min=10; int mark[10]; for(i=0;i<9;++i) {  for(j=0;j<9;++j)  {   if(map[i][j])    continue;   int c=check(i,j,mark);   if(c==0)    return;   if(c<min)   {    im=i;    jm=j;    min=c;   }  } } if(im==-1) {  printf("No. %d:\n",++solves);  display();  return; } check(im,jm,mark); for(i=1;i<=9;++i) {  if(mark[i]==0)  {   map[im][jm]=i;   dfs();  } } map[im][jm]=0;} #include <iostream>#include "sudoku.h"using namespace std;int main(){ int data1[]= {4,9,0,0,0,6,0,2,7,  5,0,0,0,1,0,0,0,4,  6,0,0,0,0,8,0,0,3,  1,0,4,0,0,0,0,0,0,  0,6,0,0,0,0,0,5,0,  0,0,0,0,0,0,2,0,8,  7,0,0,2,0,0,0,0,5,  8,0,0,0,9,0,0,0,1,  3,4,0,5,0,0,0,6,2 }; int data2[]= {7,4,0,0,8,0,0,1,6,  9,0,0,0,3,5,0,0,4,  0,0,0,7,0,0,0,0,0,  0,7,0,0,0,9,5,0,0,  6,1,0,0,5,0,0,8,7,  0,0,2,6,0,0,0,4,0,  0,0,0,0,0,4,0,0,0,  3,0,0,5,6,0,0,0,2,  5,6,0,0,1,0,0,3,9 }; CSudoku s1(data1); s1.display(); s1.resolve(); CSudoku s2(data2); s2.display(); s2.resolve(); return 0;} 代码里有很大部分实际上是在‘生成数独’，然后结果并不是我所料的那样，我用随机填充的方法，生成的大都是没有解的数独，如果空格太多，解是有，也太多。所以数独的生成似乎成了个难题。 数独的生成，最好的情况是，先得到一个完整的数独，然后根据难度需要，随机地挖一些空格出来，过程是相反的，所以可以保证有解。所以关键就是如何得到完整的数独，也要有一定的随机化。用上面的程序可以试验出来，如果我挖的空格越大，就越容易出解（相对于无解的情况），那偶就可以从一些有很多空格的数独出发，用解数独的程序，先解一个数独，那不就得到了完整的数独！也就是先只设定少数一些位置上的数字，然后用解数独程序得到完整数独，然后再挖一些空格出来，这样就得到一个绝对有解的数独，that's right! 偶的生成方法采用很简单的方法，因为可以通过上面的程序验证，当有72个空格时，可以很快得到一个数独解，偶就在一开始在每一行的随机位置上填上1-9的数字，这些初始数字就叫他们种子吧，不同的种子可以得到不同的数独，9行，每行9个位置，那有9的9次方，大概3亿多个不同情况，那我至少可以得到3亿多个不同的完整数独，再随机去掉不同数目的空格，那就可以生成相当数量的数独了！ 改进了的数独生成程序及完整的数独代码：（比原来更短了） #ifndef SUDOKU_RICK_0701_#define SUDOKU_RICK_0701_class CSudoku{ int map[9][9]; int smod; int solves; int check(int,int,int*); void dfs();public: enum{ANY=0,ALL=1}; CSudoku(int n=40);// 随机生成数独,n越大越难 CSudoku(int *data);// 人工指定数独 virtual ~CSudoku(); void display();// 显示数独 int resolve(int mod=ALL);// 解数独};#endif #include "sudoku.h"#include "stdio.h"#include "stdlib.h"#include "time.h" CSudoku::CSudoku(int n){ int i,j; srand(time(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;  } } while(!resolve(ANY));  // 挖窟窿 for(int k=0;k<n;) {  i=rand()%81;  j=i%9;  i=i/9;  if(map[i][j]>0)  {   map[i][j]=0;   ++k;  }  } //printf("(randomized sudoku created with %d blanks.)\n",blanks);}CSudoku::CSudoku(int *data){ int *pm=(int*)map; for(int i=0;i<81;++i)  pm[i]=data[i];}CSudoku::~CSudoku(){ return;}void CSudoku::display(){ for(int i=0;i<9;++i) {  for(int j=0;j<9;++j)  {   if(map[i][j]>0)    printf("< %d >  ",map[i][j]);   else    printf("[   ]  ");  }  printf("\n"); }}int CSudoku::resolve(int mod){ smod=mod; if(mod==ALL) {  solves=0;  dfs();  return solves; } else if(mod==ANY) {  try  {   dfs();   return 0;  }  catch(int)  {   return 1;  } } return 0;}int CSudoku::check(int y,int x,int *mark){ int i,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++; return count;}void CSudoku::dfs(){ int i,j,im=-1,jm,min=10; int mark[10]; for(i=0;i<9;++i) {  for(j=0;j<9;++j)  {   if(map[i][j])    continue;   int c=check(i,j,mark);   if(c==0)    return;   if(c<min)   {    im=i;    jm=j;    min=c;   }  } } if(im==-1) {  if(smod==ALL)  {   printf("No. %d:\n",++solves);   display();   return;  }  else if(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;} #include <iostream>#include "sudoku.h"using namespace std;int main(){ int data1[]= {4,9,0,0,0,6,0,2,7,  5,0,0,0,1,0,0,0,4,  6,0,0,0,0,8,0,0,3,  1,0,4,0,0,0,0,0,0,  0,6,0,0,0,0,0,5,0,  0,0,0,0,0,0,2,0,8,  7,0,0,2,0,0,0,0,5,  8,0,0,0,9,0,0,0,1,  3,4,0,5,0,0,0,6,2 }; int data2[]= {7,4,0,0,8,0,0,1,6,  9,0,0,0,3,5,0,0,4,  0,0,0,7,0,0,0,0,0,  0,7,0,0,0,9,5,0,0,  6,1,0,0,5,0,0,8,7,  0,0,2,6,0,0,0,4,0,  0,0,0,0,0,4,0,0,0,  3,0,0,5,6,0,0,0,2,  5,6,0,0,1,0,0,3,9 }; int blanks; cout<<"随机生成一个数独,输入空格数"; cin>>blanks; CSudoku s(blanks); s.display(); cout<<"开始解数独:"<<endl; s.resolve(); return 0;} 测试运行结果： 随机生成一个数独,输入空格数40[   ]  < 7 >  < 8 >  [   ]  [   ]  [   ]  [   ]  [   ]  < 6 >< 6 >  < 3 >  [   ]  < 7 >  [   ]  < 2 >  < 8 >  [   ]  < 5 >< 2 >  [   ]  [   ]  < 8 >  [   ]  [   ]  [   ]  [   ]  < 9 >< 3 >  < 9 >  [   ]  < 1 >  [   ]  [   ]  < 2 >  < 5 >  [   ][   ]  [   ]  [   ]  < 2 >  < 5 >  < 4 >  < 6 >  [   ]  < 3 >< 4 >  [   ]  [   ]  [   ]  [   ]  [   ]  < 7 >  < 1 >  [   ][   ]  [   ]  [   ]  < 4 >  < 7 >  [   ]  [   ]  < 3 >  < 1 >< 9 >  < 4 >  [   ]  < 6 >  < 2 >  < 1 >  < 5 >  < 8 >  [   ][   ]  [   ]  < 7 >  < 9 >  < 3 >  [   ]  [   ]  < 6 >  < 2 >开始解数独:No. 1:< 1 >  < 7 >  < 8 >  < 5 >  < 4 >  < 9 >  < 3 >  < 2 >  < 6 >< 6 >  < 3 >  < 9 >  < 7 >  < 1 >  < 2 >  < 8 >  < 4 >  < 5 >< 2 >  < 5 >  < 4 >  < 8 >  < 6 >  < 3 >  < 1 >  < 7 >  < 9 >< 3 >  < 9 >  < 6 >  < 1 >  < 8 >  < 7 >  < 2 >  < 5 >  < 4 >< 7 >  < 8 >  < 1 >  < 2 >  < 5 >  < 4 >  < 6 >  < 9 >  < 3 >< 4 >  < 2 >  < 5 >  < 3 >  < 9 >  < 6 >  < 7 >  < 1 >  < 8 >< 5 >  < 6 >  < 2 >  < 4 >  < 7 >  < 8 >  < 9 >  < 3 >  < 1 >< 9 >  < 4 >  < 3 >  < 6 >  < 2 >  < 1 >  < 5 >  < 8 >  < 7 >< 8 >  < 1 >  < 7 >  < 9 >  < 3 >  < 5 >  < 4 >  < 6 >  < 2 >No. 2:< 1 >  < 7 >  < 8 >  < 5 >  < 4 >  < 9 >  < 3 >  < 2 >  < 6 >< 6 >  < 3 >  < 9 >  < 7 >  < 1 >  < 2 >  < 8 >  < 4 >  < 5 >< 2 >  < 5 >  < 4 >  < 8 >  < 6 >  < 3 >  < 1 >  < 7 >  < 9 >< 3 >  < 9 >  < 6 >  < 1 >  < 8 >  < 7 >  < 2 >  < 5 >  < 4 >< 7 >  < 8 >  < 1 >  < 2 >  < 5 >  < 4 >  < 6 >  < 9 >  < 3 >< 4 >  < 2 >  < 5 >  < 3 >  < 9 >  < 6 >  < 7 >  < 1 >  < 8 >< 8 >  < 6 >  < 2 >  < 4 >  < 7 >  < 5 >  < 9 >  < 3 >  < 1 >< 9 >  < 4 >  < 3 >  < 6 >  < 2 >  < 1 >  < 5 >  < 8 >  < 7 >< 5 >  < 1 >  < 7 >  < 9 >  < 3 >  < 8 >  < 4 >  < 6 >  < 2 >Press any key to continue rickone 2007/01/25

评论