admin 管理员组文章数量: 1087840
2024年4月28日发(作者：抽象类的用处)
数独(sudoku)的生成与破解
一、 数独游戏的规则
数独(sudoku)，起源于瑞士，于1970 年代由美国的一家数学逻辑游戏杂志首先发表，当时名
为Number Place。及后在日本大力推广下得以发扬光大，于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，
那这个格子可以先确定下来，如果降到了0，哦，非常遗憾，在前面的填数中一定是填错了，你不
得不回退。
四、 唯一解的问题
这里有一问题，我们需要的是我们生成的数独是否具有唯一解？是的，按上面数独生成的过程
是不能保证的。为了保证数独有唯一解，应该从哪儿考虑呢？
我的思路是：从完整数独中挖格子的过程中去分析。
根据数独破解的方法，在破解过程中每次要寻找的最小不确定度的那个格子，如果每次找到的
这个格子可填的数字都仅为１个（最小不确定度为１）时，那么得到的解一定唯一。这样就给我们
启发，我们在挖格子时，每挖一个格子，也去检测最小不确定度的格子的不确定度。如果这个不确
定度大于１，则就要重新这次挖格子。另外也有可能挖遍所有的格子（程序中我设的上限是81次）
也没有合适解时，那么要中止这次操作，这时就要从重新生成一个数独。
五、 游戏的难易程序
这个问题我是这么考虑的，只要生成的数独中的空格数（blank）越多，那么就越难。所以在
些程序中我设置三个级别：
１ 容易： blank=33~35；
２ 中等： blank=36~38；
３ 困难： blank=39~41；
六、 源程序
#ifndef SUDOKU_RICK_0701_
#define SUDOKU_RICK_0701_
class CSudoku
{
int map[9][9];
int blanks;
int smod;
int solves;
int check(int,int,int*);
void dfs();
public:
enum{ANY=0,ALL=1};
CSudoku(int);
CSudoku::CSudoku(int *data);
void SudokuGenerator(int); // 随机生成数独,n越大越难
void SudokuGenerator(int *data); // 人工指定数独
//virtual ~CSudoku();
void display(); // 显示数独
int resolve(int mod=ALL); // 解数独
void analyze();
};
#endif
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "iostream"
#include "iomanip" //要用到格式控制符
using namespace std;
CSudoku::CSudoku(int n)
{
int j;
j=rand()%3;
blanks=n+j;
SudokuGenerator(blanks);
cout< //cout<<(空格子数为"< display(); cout<<"press enter to continue! "< getchar(); getchar(); while(1) { cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% "< cout<<" %% 请选择您的操作: %% "< cout<<" %%============================%% "< cout<<" %% %% "< cout<<" %% 1. 显示当前数独 %% "< cout<<" %% 2. 分析求解 %% "< cout<<" %% 3. 查看结果 %% "< cout<<" %% 4. 返 回 %% "< cout<<" %% %% "< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% "< int select; cin>>select; switch (select) { case 1: { cout< display(); cout<<"press enter to continue! "< getchar(); getchar(); break; } case 2: { analyze(); break; } case 3: { cout< resolve(); cout<<"press enter to continue! "< getchar(); getchar(); break; } case 4: return; default: { cout<<"输入错误,请重新输入."< break; } } } } CSudoku::CSudoku(int *data) { SudokuGenerator(data); cout< display(); cout<<"press enter to continue! "< getchar(); getchar(); analyze(); } void CSudoku::SudokuGenerator(int n) { int i,j; int mark[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(int k=0;k { int tmp,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); } } void CSudoku::SudokuGenerator(int *data) { int *pm=(int*)map; for(int i=0;i<81;++i) pm[i]=data[i]; } void CSudoku::display() { printf("┏━┯━┯━┳━┯━┯━┳━┯━┯━┓n"); for(int i=0;i<9;++i) { for(int j=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"); } 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]; // display(); //求自由度最小的格map[im][jm] 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 { im=i; jm=j; min=c; } } } if(im==-1) //若im=-1，则格子都填满。 { if(smod==ALL) //smod==ALL是求解过程。 { //printf("No. %d:n",++solves); display(); return; } else if(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; } void CSudoku::analyze() { while(1) { cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% "< cout<<" %% 请问你想做什么? %% "< cout<<" %%============================%% "< cout<<" %% %% "< cout<<" %% 1. 查找最小不确定度的格子 %% "< cout<<" %% 2. 指定格子的可填数 %% "< cout<<" %% 3. 给指定格子填数 %% "< cout<<" %% 4. 显示当前数独 %% "< cout<<" %% 5. 查看结果 %% "< cout<<" %% 6. 返 回 %% "< cout<<" %% %% "< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% "< int select; cin>>select; switch(select) { case 1: //求不确定度最小的空格map[im][jm] { 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) { cout<<"不能得到结果或已无空格子!自动返回! "< return; } if(c { im=i; jm=j; min=c; } } } cout< "< cout<<"press enter to continue! "< getchar(); getchar(); break; } case 2: { int x,y; int mark[10]; cout< getchar(); while (map[x][y]!=0) { cout< cout<<"请重新输入格子位置(如[2,4],则输入:2 4, 中间用空格.): [x,y]="; cin>>x>>y; getchar(); } int i,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<<"press enter to continue! "< getchar(); break; } case 3: { int x,y; cout< cout<<"请输入要填入的数: "; cin>>map[x][y]; cout<<"您填入的格为: map["< cout<<"press enter to continue! "< getchar(); getchar(); break; } case 4: { cout< display(); cout<<"press enter to continue! "< getchar(); getchar(); break; } case 5: { cout< resolve(); //没有输入参数，则默认为smod==ALL,见程序开始函数声明。 cout<<"press enter to continue! "< getchar(); getchar(); break; } case 6: return; default: { cout<<"输入错误,请重新输入."< break; } } } } void main() { int blanks; while(1) { bool exit_f=true; cout< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%% "< cout<<" %% SUDOKU游戏 %% "< cout<<" %% 任二艳制作 %% "< cout<<" %%=====================%% "< cout<<" %% 1. 新游戏 %% "< cout<<" %% 2. 退 出 %% "< cout<<" %%%%%%%%%%%%%%%%%%%%%%%%% "< int select; cin>>select; switch (select) { case 1: //开始新游戏 { 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. 退 出 "< cout<<"======================= "< int level; cin>>level; switch(level) { case 1: { blanks=33; CSudoku s(blanks); break; } case 2: { blanks=36; CSudoku s(blanks); break; } case 3: { blanks=39; CSudoku s(blanks); break; } case 4: { exit_f=false; break; } default: { cout<<"输入错误,请重新输入."< break; } } } break; } case 2: return; default: } } } { cout<<"输入有误,请重新选择!"< break; }
版权声明：本文标题：数独(sudoku)的生成与破解 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1714278702a673157.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论