数独电脑自动计算,数独电脑系统自带

数独的解谜技巧，可大分为直观法及候选数法两种。

直观法的特性：

1. 不需任何辅助工具就可应用。所以要玩报章杂志上的数独谜题时，只要有一枝笔就可以开始了。

2. 从接到数独谜题的那一刻起就可以立即开始解题。

3. 初学者或没有计算机辅助时的首要解题方法。

4. 相对而言，能解出的谜题较简单。

5. 主要的技巧：唯一解法、基础摒除法、区块摒除法、唯余解法、矩形摒除法、单元摒除法。

候选数法的特性：

1. 需先建立候选数列表，所以要玩报章杂志上的数独谜题时，因篇幅的影响通常格子不会太大，且候选数列表 的建立十分繁琐，所以常需计算机辅助，或使用候选数法的辅助解题用纸。

2. 需先建立候选数列表，所以从接到数独谜题的那一刻起，需经过一段相当的时间才会出现第 1 个解。

3. 需使用高阶直观法技巧或有计算机辅助时的首要解题方法。

4. 相对而言，能解出的谜题较复杂。

5. 主要的技巧：唯一候选数法(Singles Candidature)、隐性唯一候选数法(Hidden Singles Candidature)、 区块删减法(Locked Candidates)、数对删减法(Naked Pairs)、隐性数对删减法(Hidden Pairs)、 三链数删减法(Naked Triples)、隐性三链数删减法(Hidden Triples)、矩形顶点删减法(X-Wing)、 三链列删减法(Swordfish)、关键数删减法(Colors, Colouring)、关连数删减法(Forcing chains)。

数独的解谜技巧，刚开始发展时，以人性的直观式解法为主，对于初入门的玩家来说，这也是 较容易理解、接受的方法；其实就算是资深的玩家，当手边没有计算机协助更新候选数列表时，大多数仍会选择 采用本法，因为候选数列表的建立及更新若采用手动方式操作，一来十分繁琐，二来十分容易出错，而候选数法 对于候选数列表的正确性要求是不容有一点误差的。一般报章杂志上的数独谜题为了迎合大众程度，大抵均属 简易级或中级，如果能灵活运用直观法，通常已游刃有余。但若是网站上的数独谜题，则常是需用到候选数法 才能解出的。

下面介绍其中一种方法：

基础摒除法

前言

对第一次接触数独游戏，接受了 1 ～ 9 的数字在每一行、每一列、每一个九宫格都只能出现一次的规则后， 开始要解题的玩家来说，基础摒除法绝对是他第一个想到及使用的方法，十分的自然、也十分的简易。

如果能够细心、系统化的运用基础摒除法，一般报章杂志或较大众化的数独网站上的数独谜题几乎全部可解出来。 只不过大部分的玩家都不知如何系统化的运用基础摒除法罢了！

基础摒除法虽然简单，但在寻找解的过程中，仍然要分成三个部分：寻找九宫格摒除解、寻找列摒除解、 寻找行摒除解。不要说是初入门者，即使是很多未接受过本讯息者，也常常会遗漏了行、列摒除解的寻找。 对一些粗心的玩家来说，即使是九宫格摒除解也常被跳着做，所以解起题来就会感到不是十分顺手。

九宫格摒除解的寻找

九宫格摒除解的系统寻找是由数字 1 开始一直到数字 9 ，周而复始， 直到解完全题或无解时为止；每个数字又需从上左九宫格起，直到下右九宫格，周而复始， 同样要不断重复到解完全题或无解时为止。

<图 1>

以< 图 1 >的解题为例：先从数字 1 开始，并由上左九宫格起寻找九宫格摒除解，会影响上左九宫格的数字， 一定存在第 1 列～第 3 列以及第 1 行～第 3 行如< 图 2 >的绿色区域。

<图 2>

本区域已存在的数字 1 共有两个，它们分别存在 (2, 9) 及 (5, 1)；其中 (2, 9)的 1 将摒除第 2 列其它 宫格再填入数字 1 的可能，因为依照规则每一列只能有一个数字 1，如果再在本列填入数字 1，那么本列 就会有两个 1 了。同理，(5, 1)的 1 则将摒除第 1 行其它宫格再填入数字 1 的可能，其示意图如<图 3>。

<图 3>

对上左九宫格的摒除仅能到此地步，我们可以很容易的发现：本九宫中还有 3 个宫格不在被摒除的区域中， 意即：这 3 个宫格都仍有可能填入数字 1，依不可猜测的原则，本九宫格暂时不予处理。

接下来我们要尝试在上中九宫格寻找是否有九宫格摒除解 1：会影响上中九宫格的数字，一定存在第 1 列 ～第 3 列以及第 4 行～第 6 行。本区域已存在的数字 1 共有 3 个，它们分别存在 (2, 9)、(4, 6) 及 (9, 5)，其摒除的范围示意图如<图 4>。

<图 4>

同样的，我们可以很容易的发现：本九宫中还有 2 个宫格不在被摒除的区域中， 意即：这 2 个宫格都仍有可能填入数字 1，依不可猜测的原则，本九宫格一样暂时不予处理。

接下来的上右、中左、中央九宫格都已有数字 1 了，所以不必再找数字 1 该填入的宫格。

所以现在需要处理的九宫格轮到了中右九宫格，依上法对此九宫格进行的摒除示意图如 <图 5>：

<图 5>

我们可以很容易的发现：本九宫中只剩宫格 (6, 8) 不在被摒除的区域中， 意即：在这个九宫格中只剩这个宫格仍有可能填入数字 1，所以本九宫格的数字 1 就只能填到这里了； 这时我们称：在 (6, 8) 有九宫格摒除解 1。

在一般的解题技巧教导中(也包含尤怪之家先前的作品)，把前面的徒劳寻找都省略不提，直接就告诉玩家： 在 (6, 8) 有九宫格摒除解 1。当然这是为了篇幅考虑，把全部过程都写出来将多出很多篇幅，但也将造成 初学者的挫折感，他们会以为计算机或已入门者的功力实在太高强了，一眼就能看出解在哪里！自己却很笨， 找了老半天才找到一个解；其实速度可能有差，方法及过程则是一样的。

重复前面的方法，我们可以发现数字 1、2 都没法找到九宫格摒除解了。轮到数字 3 时，也要一直到 下左九宫格才能找到 (8, 2) 有九宫格摒除解 3 如 <图 6>、然后在 (9, 9) 有九宫格摒除解 3 如 <图 7>：

<图 6> <图 7>

在这里要提醒初学者注意的是：虽然我们从上左九宫格开始，到现在的下右九宫格，已将所有的九宫格都 找过一遍了！但因为中间曾经在某些宫格填入我们找到的数字解，所以一定要再从头找一遍，否则会让 我们遗漏掉一些可以马上找到的解。例如我们又可找到在 (6, 1) 有九宫格摒除解 3 如 <图 8>； 然后在 (5, 6) 也有九宫格摒除解 3 如 <图 9>：

<图 8> <图 9>

同样的，因为在本循环又曾找到一些解，所以还要再找一次，确定已没法找到九宫格摒除解 3 了，才能 换成数字 4 继续寻找下去。

在以上的过程中，为了标示已存在的数字对九宫格的摒除状况，特别用图示的方式呈现，有些玩家就发出了 这样的疑问：在解报章杂志上的数独题目时，是否要用铅笔在谜题上画线，以找出摒除解呢？其实不必啦！ 玩家们只要稍微练习一下，至多只要空手在谜题上比划比划，就可以看出哪些宫格已被摒除，进而找出摒除解 的。

行、列摒除解的寻找

和九宫格摒除解的寻找一样，列摒除解的系统寻找是由数字 1 开始一直到数字 9 ，周而复始，直到解完全题或 无解时为止；每个数字又需从第 1 列起，直到第 9 列止，周而复始，同样要不断重复到解完全题或无解时为止。 同理，行摒除解的系统寻找也是一样的作法。

大部分的人都会十分习惯应用九宫格摒除解的寻找，而完全忽略了行、列摒除解的寻找；对某些题目而言或许 可行，但对某些题目而言，不运用此二法可是行不通的哦！

大家已有九宫格摒除解的寻找经验了，所以尤怪就不再把无效的找寻过程秀出来，而直接展示成功的例子啦， 不过直接秀出来又太没意思了，就当做是做个小小的测验吧，以下的范例都先展示目前题型，并告诉大家在 某个宫格有何解，请大家找找看，如果找到了，要核对摒除示意图，或者找不到，要参考摒除示意图，请将 鼠标光标移到图块上就可显现啦！

在< 图 10 >中，(5, 5) 有一个摒除解 7，你可以看出来吗？

<图 10>

在< 图 11 >中，(9, 1) 有一个摒除解 3，你可以看出来吗？

<图 11>

在< 图 12 >中，(7, 1) 有一个摒除解 1，你可以看出来吗？

<图 12>

在< 图 13 >中，(6, 4) 有一个摒除解 6，你可以看出来吗？

<图 13>

在< 图 14 >中，(1, 3) 有一个摒除解 7，你可以看出来吗？

<图 14>

结语

直观法的基石就是基础摒除法，而基础摒除法中最常用的又是九宫格摒除解的寻找。

有些人只有在所有数字的九宫格摒除解寻找已触礁时，才做行、列摒除解的寻找；有些人则是在每一个数字的 九宫格摒除解寻找完毕后，先做行、列摒除解的寻找，然后再进行下一个数字的摒除。尤怪个人在解题时是 采用前一种做法，但数独教授则是采用第二种做法，要如何运用全看使用者个人的习惯了，不过系统性寻找 的习惯最好要及早建立。

开始的话：这个程序现在还不稳定，有时出现运行时错误，跟踪是由于vector的size()方法引起的。调试发现中间的min_seq并没有完全按照作者的意图变化。

运行时，如果出现错误，就反复运行，运行成功即可出现一个正确的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=0;i<9;++i)

{

for(int j=0;j<9;++j)

{

cout<<MATRIX[i][j]<<'\t';

}

cout<<endl;

}

return 0;

}

/*******************函数定义***********************/

/*********得到初始给出的元素个数*******/

int get_initialcount()

{

int count=0;

for(int i=0;i<9;++i)

{

for(int j=0;j<9;++j)

{

if(MATRIX[i][j]!=0)

{

count++;

}

}

}

return count;

}

/*******初始化候选集合***************/

void initial_candidate()

{

for(int i=0;i<81;++i)

{

for(int j=1;j<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=0;i<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=0;colnum<9;++colnum)

{

delete_value(IVEC[i],MATRIX[row][colnum]);

}

/*****删除同一列中的元素****/

for(rownum=0;rownum<9;++rownum)

{

delete_value(IVEC[i],MATRIX[rownum][col]);

}

/*****删除在一个3×3方阵中的元素******/

/******在第1块中，删除3×3方阵元素*****/

if(row/3==0 && col/3==0)

{

for(int r=0;r<3;++r)

{

for(int c=0;c<3;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第2块中，删除3×3方阵元素*****/

if(row/3==0 && col/3==1)

{

for(int r=0;r<3;++r)

{

for(int c=3;c<6;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第3块中，删除3×3方阵元素*****/

if(row/3==0 && col/3==2)

{

for(int r=0;r<3;++r)

{

for(int c=6;c<9;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第4块中，删除3×3方阵元素*****/

if(row/3==1 && col/3==0)

{

for(int r=3;r<6;++r)

{

for(int c=0;c<3;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第5块中，删除3×3方阵元素*****/

if(row/3==1 && col/3==1)

{

for(int r=3;r<6;++r)

{

for(int c=3;c<6;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第6块中，删除3×3方阵元素*****/

if(row/3==1 && col/3==2)

{

for(int r=3;r<6;++r)

{

for(int c=6;c<9;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第7块中，删除3×3方阵元素*****/

if(row/3==2 && col/3==0)

{

for(int r=6;r<9;++r)

{

for(int c=0;c<3;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第8块中，删除3×3方阵元素*****/

if(row/3==2 && col/3==1)

{

for(int r=6;r<9;++r)

{

for(int c=3;c<6;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第9块中，删除3×3方阵元素*****/

if(row/3==2 && col/3==2)

{

for(int r=6;r<9;++r)

{

for(int c=6;c<9;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

}

}

}

/*********返回9×9候选集合元素最少的候选集合序号*******/

int min_seq()

{

int count[81];

int i;

for(i=0;i<81;++i)

{

count[i]=IVEC[i].size();

}

int value=10;

int min_seq;

for(i=0;i<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;

}

}

希望对你有帮助！！