数独设计理念和完整解决方案
运行时，如果有错误，反复运行，运行成功后会出现一个正确的9*9数独矩阵。
如果你想玩一个预先填充了一些数字的游戏，你只需要修改初始矩阵。
算法:为每个位置定义一个可选的元素集合，每次更新都是从集合中删除已经出现在它的行、列和3×3方阵中的元素。填充时，从最小候选集(立即)中选择一个填充，更新候选集，然后填充，直到所有位置都被填充，游戏结束。
/* * * * * * 9×9数独游戏的计算机程序* * * * * *
/* * * * * *作者:小慈* * * * * * * * * * * *
/* * * * * *时间:2006年6月23日* * * * * * * * * *
/* * * * * *版本:V1.0 * * * * * * * * * * * * * * *
* * * * * * * *算法思想* * * * * * * * * * * * * * * * * *
/* * * * *对于每个位置的元素，考虑可以选择的数量。
设置，并一次用最少数量的候选元素填充该位置。
从最小候选集合中随机选择一个元素进行填充，然后重复。
这个过程，直到所有的元素都被填入* * * * * * * * * */
/* * * *适合填充所有空的数独方块和填充一些现有的数独方块* * * */
/* * * *对初始化的候选集的第一次更新是解决第二个数独游戏* * *
/* * * *如果已经填写了一些元素，可以直接修改矩阵* * * *
/* * * *数独有多个结果* * * * * */
# include & ltiostream & gt
# include & ltctime & gt
# include & ltvector & gt
使用命名空间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；
/* * * * * * *每个元素的初始候选集* * * * * *
向量& lt向量& ltint & gt& gtIVEC(81)；
/* * * * * * * * * *函数原型* * * * * * * * * * * * * *
/* * * * * *获取元素的初始数量* * * * * *
int get _ initial count()；
/* * * * * * *初始化候选集* * * * * * * * * *
void initial _ candidate()；
/* * * * * * * * *从vector中删除指定的元素* * * * * *
void delete_value(向量& ltint & gt& ampivec，int值)；
/* * * * * * * *更新候选集* * * * * * * * * *
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 _ INITIAL COUNT()；
/* * * * * *初始化候选集* * * * */
initial _ candidate()；
/* * * * * * * *先更新候选集(应对部分号码已被填充的情况)* * * */
refresh_candidate()。
int I；
int MinSeq
int选择值；
min seq = min _ seq()；
choose value = choose _ seq(MinSeq)；
while(is_finish(MinSeq，ChooseValue)！=1)
{
refresh_candidate()。
min seq = min _ seq()；
choose value = choose _ seq(MinSeq)；
}
/* * * * * * * *输出完成的数独游戏结果* * * * * * * *
for(I = 0；我& lt9;++i)
{
for(int j = 0；j & lt9;++j)
{
cout & lt& ltMATRIX[I][j]& lt；& lt\ t '；
}
cout & lt& ltendl
}
返回0；
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
/* * * * * *获取元素的初始数量* * * * * *
int get_initialcount()
{
int count = 0；
for(int I = 0；我& lt9;++i)
{
for(int j = 0；j & lt9;++j)
{
if(MATRIX[i][j]！=0)
{
count++；
}
}
}
返回计数；
}
/* * * * * * *初始化候选集* * * * * * * * * *
void initial_candidate()
{
for(int I = 0；我& lt81;++i)
{
for(int j = 1；j & lt10;++j)
{
IVEC[我]。push _ back(j)；
}
}
}
/* * * * * * * * *从vector中删除指定的元素* * * * * *
void delete_value(向量& ltint & gt& ampivec，int值)
{
/* * * * * * *如果ivec为空，直接退出* * * * * */
if (ivec.size()==0)
{
返回；
}
向量& ltint & gt*迭代器ITER = ivec . begin()；
while(ITER & lt；ivec . end()& amp；& amp(*iter)！=值)
{
iter++；
}
if(ITER & lt；Ivec.end())//找到vector中填充的元素并删除。
{
ivec . erase(ITER)；
}
}
/* * * * * * * *更新候选集* * * * * * * * * *
void refresh_candidate()
{
int I；
int rownum，colnum
int row，col
/* * * * * *更新81矢量*******/ * * *
for(I = 0；我& lt81;++i)
{
row = I/9；
col = I % 9；
if(矩阵[行][列]！=0)//位置已填充。
{
如果(IVEC[我]。size()！=0)//向量不为空。
{
/* * * * * *删除整个候选集* * * * * * * *
IVEC[我]。抹去(IVEC[我]。开始()，IVEC[我]。end())；
}
}
其他
{
/* * * *删除同一行中的元素* * */
for(colnum = 0；colnum & lt9;++列)
{
delete_value(IVEC[i]，矩阵[行][列数])；
}
/* * * *删除同一列中的元素* * */
for(rownum = 0；rownum & lt9;++rownum)
{
delete_value(IVEC[i]，矩阵[rownum][col])；
}
/* * * * * *删除3×3正方形中的元素* * * * */
/* * * * *在块1中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 0 & amp；& ampcol/3==0)
{
for(int r = 0；r & lt3;++r)
{
for(int c = 0；c & lt3;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
/* * * * * *在块2中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 0 & amp；& ampcol/3==1)
{
for(int r = 0；r & lt3;++r)
{
for(int c = 3；c & lt6;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
/* * * * * *在第三个块中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 0 & amp；& ampcol/3==2)
{
for(int r = 0；r & lt3;++r)
{
for(int c = 6；c & lt9;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
/* * * * * *在块4中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 1 & amp；& ampcol/3==0)
{
for(int r = 3；r & lt6;++r)
{
for(int c = 0；c & lt3;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
/* * * * * *在块5中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 1 & amp；& ampcol/3==1)
{
for(int r = 3；r & lt6;++r)
{
for(int c = 3；c & lt6;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
/* * * * * *在第6块中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 1 & amp；& ampcol/3==2)
{
for(int r = 3；r & lt6;++r)
{
for(int c = 6；c & lt9;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
/* * * * * *在第7块中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 2 & amp；& ampcol/3==0)
{
for(int r = 6；r & lt9;++r)
{
for(int c = 0；c & lt3;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
/* * * * * *在第8块中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 2 & amp；& ampcol/3==1)
{
for(int r = 6；r & lt9;++r)
{
for(int c = 3；c & lt6;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
/* * * * * *在第9块中，删除3×3的正方形矩阵元素* * * */
if(row/3 = = 2 & amp；& ampcol/3==2)
{
for(int r = 6；r & lt9;++r)
{
for(int c = 6；c & lt9;++c)
{
delete_value(IVEC[i]，矩阵[r][c])；
}
}
}
}
}
}
/* * * * * * * *返回元素数最少的9×9候选集的序列号* * * * * *
int min_seq()
{
int count[81]；
int I；
for(I = 0；我& lt81;++i)
{
IVEC伯爵。size()；
}
int value = 10；
int min _ seq
for(I = 0；我& lt81;++i)
{
if(count[i]==0)
{
继续；
}
if(count[I]& lt；值)
{
value = count[I]；
min _ seq = I；
}
}
返回min _ seq
}
/* * * * * *随机生成一个位置序号，并获取该序号对应的元素值* * * * */
整数选择序列(整数最小序列)
{
/* * * *根据当前时间设置种子* * * * */
srand((无符号)时间(空))；
int random _ seq = rand()%(IVEC[最小序列])。size())；
返回IVEC[最小序列][随机序列]；
}
/* * * * * * *填写该元素，判断是否完成* * * * * */
int is_finish(int min_seq，int choose_value)
{
int row，column
row = min _ seq/9；
column = min _ seq % 9；
矩阵[行][列]= choose _ value；
FINISH _ count++；/* * * *填充元素的数量加上1*****/
/* * * * * *填写后判断* * * * * *
if(完成计数= = 81-初始计数)
{
返回1；
}
其他
{
返回0；
}
}
/Cui feng hui/blog/item/f 771396 DD 111 bbfb 421694 ee . html
希望对你有帮助！！