|
程序中rowcnt[r]、colcnt[t]、newcnt[m]分别为每一行、列、区的空格个数，Wei[r][h]表示每一行空格的相应位置，程序初始时把a[x][x]赋值给了b[x][x]。aflag为1表示寻找到当前空格中行、列都缺少的数据，roww[r][i] 、colw[t][j]、neww[m][q]表示每一行、每一列、每一区中缺少的整数。xian[r][h][rowk]为此空格的候选数，samecnt[r][h]为其个数。针对某一空格，如果行、列、区都缺少此数据，那么此数据为当前空格的一个候选数，同时其个数加1。如果samecnt[r][h]为1，那么此空格只有唯一解。
也就是说，人一眼看出缺少的数据，实际上也要由这些过程得来：此空格所处的行、列、区都缺少一些什么数据；该数据是否是三者都缺少；如果是，那么就是此空格的候选数；如果其个数是1，那么直接填入即可。计算机程序无非是把这一过程细化了。
唯一法还可以进行扩展，如此时观察a[5][2]，可以发现，由于前两行都出现了数字8，那么此行此区也要出现，而在a[5][1]这一列中已经出现过数字8，那么a[5][2]必然是数字8。同理可在a[0][0]写入8、a[3][4]写入7。
用C语言来表达在a[5][2]写入8的过程，首先要对每一行中每个区0的个数进行区别对待，即一行中每3列(一个区中)有几个0。这里在a[5][2]处为有两个0的情况。然后判断另外两行(由于1个区由3行3列组成，这里指的是和该区并排的另外两行)是否出现了与某一候选数相同的数据。如果有，再找出另一空格的那一列是否出现了同样的数据，如果仍然成立，那么使此空格的候选个数置1，写入该候选数。
唯一法还可以进一步扩展，如此时观察a[8][0]，虽然前面的方法已经无法再用，但是针对此空格，可以发现，除了它可以写入4之外，这一列中的其余空格都不可能填入该数字，那么该数字就是唯一答案。同理可在a[8][8]写入2、a[0][8]写入3、a[3][0]写入3、a[5][8]写入4。然后可以在a[5][8]写入4。
用C语言来描述在a[8][0]写入4的过程，可以采用如下方法：首先对此列的每一候选数出现的次数都进行累加；然后找候选数有没有只出现过一次的数据，如果有，那么此空格只能填入该数据，其他候选数可以忽略。
2. 排除法
遗憾的是此题未能使用到排除法，或者说使用了也不能使某一空格有惟一解。经常见到某行、某列或某区的两个空格出现候选数相同的情况，那么在该行、该列或该区的其它空格的候选数就可以删除相同的数据，因为不可能再填入该数据。同样某行、某列或某区有三个空格出现候选数相同或大致相同的情况，可以采用这种方式处理。如某行三个空格的候选数为12、13、123或13、123、123或12、23、13就可当作大致相同。而在许多数独题目中，当某些空格删除了这样的候选数后，将只剩下唯一答案。这里不再展开讨论。
3.尝试法
在使用了唯一法后，无法再做下去，这时只好采用尝试法。首先选定一个候选数最少的空格，如a[0][1]只有两个候选数2和6。先选择其中较小的候选数2，把它填入。这一数据填对填错的概率为50%。然后往下判定其他的空格，结果发现最终无法解题，当要填a[2][7]时出现冲突，a[2][1]及a[2][7]都只能填入5；那么可以断定前面的假设是错误的，a[0][1]应该选择候选数6填入，刚才填入的数据要重新再填。这一次，可以顺利解题。
用C语言来描述尝试法，以填入a[0][1]为例，程序如下：
if (aflag==2) //尝试写入数据
{
initial_b(btemp2, b);//把现在b的值暂存起来
initial_rowcolneww_1(0);//给roww_1赋初值
initial_rowcolneww_1(1);//给colw_1赋初值
initial_rowcolneww_1(2);//给neww_1赋初值
initial_samecnt(0);
initial_xian(0);//给xian赋初值
changshi(); //尝试函数
rtnleast=rtnlittle[0]; // rtnlittle[0]=least;
rtnj=rtnlittle[1]; // rtnlittle[1]=r;
rtni=rtnlittle[2]; // rtnlittle[2]=s;
samecnt[rtnj][rtni]=1;
}//end if (aflag==2)
if(aflag==3)
{
initial_b(b, btemp2);//复原原来的数据
initial_rowcolneww(0);//给roww赋初值
initial_rowcolneww(1);//给colw赋初值
initial_rowcolneww(2);//给neww赋初值
initial_samecnt(1);
initial_xian(1);//给xian赋初值
if (ycnt<rtnleast-1)
{
ycnt++;
yiwei(rtnj,rtni,ycnt);
samecnt[rtnj][rtni]=1;
}
else
{
ycnt=0; //清除掉循环完毕标志
aflag=4; //另外处理
}
}
在进行尝试写入前，首先要保存此时的一些关键数据，如b、roww、colw、neww 、samecnt、xian等。然后寻找候选数最少的空格，保存候选数的个数及空格的位置。然后将使此空格的候选个数置1，写入该候选数。如果未能成功解题(出错)，那么需要复原在尝试前的所有数据，选择下一个候选数，再次写入。如果候选数用完仍然不能成功解题，那么需要进行第二次尝试。本例中未用到第二次尝试，最终此题答案如下。
{8, 6, 2, 7, 5, 1, 4, 9, 3},
{9, 3, 7, 6, 4, 8, 1, 2, 5},
{1, 5, 4, 2, 9, 3, 7, 8, 6},
{3, 4, 6, 1, 7, 2, 9, 5, 8},
{7, 9, 5, 4, 8, 6, 2, 3, 1},
{2, 1, 8, 9, 3, 5, 6, 7, 4},
{5, 2, 9, 8, 1, 4, 3, 6, 7},
{6, 8, 1, 3, 2, 7, 5, 4, 9},
{4, 7, 3, 5, 6, 9, 8, 1, 2}
四、结语
经过试验，本程序可以解决许多数独题目。如下面这样的难题，在填a[5][5]时用到了排除法，可以不用尝试法，更接近人工解题的思路。
int a[x][x]=
{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
};
参考文献
[1] 谭浩强. C语言程序设计[M].北京:清华大学出版社,2000.
[2] 数独9981网站. http://www.sd9981.com/.
[3] 于春凡. C语言程序设计[M].天津:南开大学出版社,2000.
[4] 钱能. C++程序设计教程[M].北京:清华大学出版社,2005.
|
