正文

数独(sudoku)的生成与破解2007-01-25 21:06:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/22806.html

分享到:

数独(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

阅读(42879) | 评论(25)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册