运行时，如果出现错误，就反复运行，运行成功即可出现一个正确的9*9数独矩阵。
如果要玩预先填充一些数的游戏，只需修改初始矩阵即可。
算法：为每个位置定义一个可选元素集合，每个更新是把它所在的行，列,所在的3×3方阵中已出现的元素从集合中去掉。填充时，从最小候选集合中选一个(可随即)填进去，更新候选集合，再填充，直到所有位置填充完毕，游戏结束。
/*******9×9数独游戏的计算机程序*******/
/*******作者：xiaocui******************/
/*******时间：2006.6.23****************/
/*******版本：v1.0*********************/
/*******算法思想***********************/
/******对每个位置的元素，考虑其可选取的数字
的集合，每次把候选元素个数最小的那个位置填充
从该最小候选集合中随机选取一个元素填充，重复
这个过程，直到所有元素填充完毕************/
/****适用填充全空的数独方格 和 填充已有一些数的数独方格*****/
/****对初始化的候选集的第一次更新正是为了解决第2类数独游戏***/
/****对于已填充一部分元素的，直接修改MATRIX矩阵即可*****/
/****数独游戏的结果不止一种********/
#include <iostream>
#include <ctime>
#include <vector>
using namespace std
/**********初始9×9的矩阵*************/
/******元素为0，说明该位置还未填充***/
int MATRIX[9][9]={ {0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0} }
/*******初始给出的元素个数***********/
int INITIAL_COUNT
/********已填充元素个数，作为填充结束标志**********/
int FINISH_COUNT=0
/********各个元素的初始候选集合*******/
vector<vector<int>>IVEC(81)
/**************函数原型******************/
/*********得到初始给出的元素个数*******/
int get_initialcount()
/*******初始化候选集合***************/
void initial_candidate()
/***********从vector中删除指定元素*******/
void delete_value(vector<int>&ivec,int value)
/********更新候选集合**************/
void refresh_candidate()
/*********返回9×9候选集合元素最少的候选集合序号*******/
int min_seq()
/********随机生成一个位置序号并取得该序号所对应的元素值******/
int choose_seq(int min_seq)
/*******填充该元素并判断是否填充完毕********/
int is_finish(int min_seq, int choose_value)
int main()
{
/******得到初始给出的元素个数*****/
INITIAL_COUNT=get_initialcount()
/******初始化候选集合*******/
initial_candidate()
/********先更新候选集合(为了应付已经填充一部分数的情况)******/
refresh_candidate()
int i
int MinSeq
int ChooseValue
MinSeq=min_seq()
ChooseValue=choose_seq(MinSeq)
while(is_finish(MinSeq,ChooseValue)!=1)
{
refresh_candidate()
MinSeq=min_seq()
ChooseValue=choose_seq(MinSeq)
}
/**********输出填好的数独游戏结果*********/
for( i=0i<9++i)
{
for(int j=0j<9++j)
{
cout<<MATRIX[i][j]<<'\t'
}
cout<<endl
}
return 0
}
/*******************函数定义***********************/
/*********得到初始给出的元素个数*******/
int get_initialcount()
{
int count=0
for(int i=0i<9++i)
{
for(int j=0j<9++j)
{
if(MATRIX[i][j]!=0)
{
count++
}
}
}
return count
}
/*******初始化候选集合***************/
void initial_candidate()
{
for(int i=0i<81++i)
{
for(int j=1j<10++j)
{
IVEC[i].push_back(j)
}
}
}
/***********从vector中删除指定元素*******/
void delete_value(vector<int>&ivec,int value)
{
/*******如果ivec已经为空，直接退出**********/
if (ivec.size()==0)
{
return
}
vector<int>::iterator iter=ivec.begin()
while( iter<ivec.end() &&(*iter)!=value )
{
iter++
}
if(iter<ivec.end())//在vector中找到已填充的元素，把它删除
{
ivec.erase(iter)
}
}
/********更新候选集合**************/
void refresh_candidate()
{
int i
int rownum,colnum
int row,col
/******更新81个vector*******/
for(i=0i<81++i)
{
row=i/9
col=i%9
if(MATRIX[row][col]!=0)//该位置已经填充
{
if(IVEC[i].size()!=0)//该vector不空
{
/********删除整个候选集***********/
IVEC[i].erase(IVEC[i].begin(),IVEC[i].end())
}
}
else
{
/*****删除同一行中的元素****/
for(colnum=0colnum<9++colnum)
{
delete_value(IVEC[i],MATRIX[row][colnum])
}
/*****删除同一列中的元素****/
for(rownum=0rownum<9++rownum)
{
delete_value(IVEC[i],MATRIX[rownum][col])
}
/*****删除在一个3×3方阵中的元素******/
/******在第1块中，删除3×3方阵元素*****/
if(row/3==0 &&col/3==0)
{
for(int r=0r<3++r)
{
for(int c=0c<3++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
/******在第2块中，删除3×3方阵元素*****/
if(row/3==0 &&col/3==1)
{
for(int r=0r<3++r)
{
for(int c=3c<6++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
/******在第3块中，删除3×3方阵元素*****/
if(row/3==0 &&col/3==2)
{
for(int r=0r<3++r)
{
for(int c=6c<9++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
/******在第4块中，删除3×3方阵元素*****/
if(row/3==1 &&col/3==0)
{
for(int r=3r<6++r)
{
for(int c=0c<3++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
/******在第5块中，删除3×3方阵元素*****/
if(row/3==1 &&col/3==1)
{
for(int r=3r<6++r)
{
for(int c=3c<6++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
/******在第6块中，删除3×3方阵元素*****/
if(row/3==1 &&col/3==2)
{
for(int r=3r<6++r)
{
for(int c=6c<9++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
/******在第7块中，删除3×3方阵元素*****/
if(row/3==2 &&col/3==0)
{
for(int r=6r<9++r)
{
for(int c=0c<3++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
/******在第8块中，删除3×3方阵元素*****/
if(row/3==2 &&col/3==1)
{
for(int r=6r<9++r)
{
for(int c=3c<6++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
/******在第9块中，删除3×3方阵元素*****/
if(row/3==2 &&col/3==2)
{
for(int r=6r<9++r)
{
for(int c=6c<9++c)
{
delete_value(IVEC[i],MATRIX[r][c])
}
}
}
}
}
}
/*********返回9×9候选集合元素最少的候选集合序号*******/
int min_seq()
{
int count[81]
int i
for(i=0i<81++i)
{
count[i]=IVEC[i].size()
}
int value=10
int min_seq
for(i=0i<81++i)
{
if(count[i]==0)
{
continue
}
if(count[i]<value)
{
value=count[i]
min_seq=i
}
}
return min_seq
}
/********随机生成一个位置序号并取得该序号所对应的元素值******/
int choose_seq(int min_seq)
{
/*****根据当前时间设置种子******/
srand((unsigned)time( NULL ))
int random_seq=rand()%(IVEC[min_seq].size())
return IVEC[min_seq][random_seq]
}
/*******填充该元素并判断是否填充完毕********/
int is_finish(int min_seq, int choose_value)
{
int row, column
row=min_seq/9
column=min_seq%9
MATRIX[row][column]=choose_value
FINISH_COUNT++/****已填充元素个数加1*****/
/*******填充完毕判断********/
if(FINISH_COUNT==81-INITIAL_COUNT)
{
return 1
}
else
{
return 0
}
}
http://den.idv.tw/den/java/sudo/makeprob.php
http://hi.baidu.com/cuifenghui/blog/item/f771396dd111bbfb421694ee.html
希望对你有帮助！！
数独游戏规则说明每一行都用到1,2,3,4,5,6,7,8,9，位置不限，
每一列都用到1,2,3,4,5,6,7,8,9，位置不限，
每3×3的格子都用到1,2,3,4,5,6,7,8,9，位置不限，
游戏的的过程就是用1,2,3,4,5,6,7,8,9填充空白，并要求满足每行、每列、每个九宫格都用到1,2,3,4,5,6,7,8,9。
标准数独的游戏规则：每行的9个单元格中填入1-9且不重复；每列的9个单元格中填入1-9且不重复；每个3*3单元格组成的宫中填入1-9且不重复。
直观解法大体分为排除法和唯一解法两大类，这两类方法的思路有所区别，原理如下：
1、排除法的原理：由于数独规则要求每行、每列和每宫的数字不重复，所以已出现的数字可以排除掉同行、同列、同宫中其他单元格内再填入该数字的可能性。
2、唯一法的原理：由于数独规则要求每行、每列和每宫中填入1-9且不重复，所以当与一个单元格同行、同列、同宫中出现了8个不同的数字，则这个单元格中只能填入余下的第9个数字。
唯一解法的几种情况：
1、行唯一解，同样可以在列和宫中运用。说明：一行中出现了8个数字，蓝色单元格中填入未出现的第9个数字。
2、行列唯一解。说明：一行与一列交叉且出现了8个不同的数字，交叉点蓝色单元格填入未出现的第9个数字。
3、行列宫唯一解。说明：一行、一列与一宫交叉且出现了8个不同的数字，交叉点蓝色单元格填入未出现的第9个数字。
排除法的几种情况
1、行列排除宫。说明：数字1排除掉7所在的宫中，与1同行列的单元格填入1的可能性，宫中只有蓝色单元格可以填入1。
2、宫排除行列、行列相互排除。说明：数字7排除掉同行中、同宫中其他单元格填入7的可能性，列中只有蓝色单元格可以填入7。
3、区块排除。说明：数字9排除掉中间宫中三个单元格填入9的可能性，则这个宫里只有剩下的两个单元格内可以填入9，这两个格子称作区块，区块中含有9，对下面宫进行排除，推出蓝色单元格填入9。
4、数对占位的排除。说明：数字3、7排除掉宫中与之同行的单元格填入3和7的可能性，该宫中只剩了两个空单元格，那么这两个空单元格中一定填入3和7，现在不能确定3、7的位置，故记做数对。数字9排除掉同宫中一些单元格填入9的可能性，列中又被数对占了位置，只有蓝色单元格可以填入9。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）