|
摘 要 以2006年首届世界数独大赛决赛题目为例，说明用C语言模拟数独的人工解题思路。介绍了唯一法、排除法及尝试法三种解题方法。用C语言模拟数独的人工解题思路，有利于学习C语言及相应的编程技巧，尝试着把人的思维方式转化成相应的计算机程序，便于人工智能方面的研究。试验验证了程序的正确性。
关键词 数独; C语言; 人工解题; 候选数
一、引言
数独是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。数独的玩法逻辑简单，数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。数独游戏成功的原因除了它的趣味性和挑战性之外，更重要的原因其实是因为它很容易上手。玩这个游戏只需要认识1～9这九个数字，然后再需要一定的逻辑推理加上必要的耐心就可以了。
数独游戏的规则是：在一个9x9的大正方形中，每一行和每一列都必须填入1至9 的数字，不能重复也不能少；在每个由粗线隔开的3 x 3小九宫格（也被称为“区”）中，也必须填入1至9的数字，同样不能重复也不能少；每个数独游戏只有一个解答方案。一般而言，一条数独题会给出1/3左右的数字作为初始条件，剩下的2/3空白处由读者完成。简单的数独题目初始时会有更多的数字。
用C语言模拟数独的人工解题思路，有利于学习C语言及相应的编程技巧，不仅可以找寻计算机程序与人思维方式的差异，而且可以尝试着把人的思维方式转化成相应的计算机程序，便于今后人工智能方面的研究。
二、数独解题思路
数独游戏上手简单，但是随着难度的加大将会充满挑战。数独的解题方法多种多样，归纳起来主要有三种方法：唯一法、排除法和尝试法。
唯一法指的是在任何一行、一列或一区中，如果仅有一个数字没有填上，那么这个数字一定是目前在这一行、这一列或是这一区里应该填上的那个数字。排除法指的是假如在某一行中的两个空格拥有相同的两个候选数字，虽然不能确定哪一个数字应该放在哪一个空格中，但至少可以确定，这一行中没有任何其他的空格可以放入这两个数字。这个原则同样适用于列和区。尝试法指的是首先选定一个候选数最少的空格，再选择其中较小的一个候选数字，假定这个候选数字就是最终的答案，然后根据往下判定其它空格，如果最终解决问题当然万事大吉；如果发现在某一相同的行、列或区中一定会出现相同的两个数字，那么可以断定前面的假设是错误的；这个时候，要重新选择另一个候选数字进行尝试，直到解题。
当然唯一法、排除法及尝试法还可以扩展，这些在用C语言实现时将做进一步探讨。从解题的顺序来看，优先使用唯一法。在唯一法无法实现解题的前提下，再使用排除法。一般入门级、中级、高级，甚至某些黄金级(骨灰级)的题目用这两种方法是可以解题的。如果在前两者循环使用后，仍然不能解决问题，再使用尝试法。高级或黄金级(骨灰级)的题目通常要用到尝试法，有些难题甚至要多次尝试，对许多空格都要尝试。如果尝试过多，人工解题就失去了太多的乐趣。通常对某一个空格使用尝试法之后，再结合唯一法、排除法可以顺利解题。
三、C语言程序
1．唯一法
这里以2006年首届世界数独大赛决赛题目为例来说明用C语言模拟数独的人工解题思路。此题用C语言描述如下：
int a[x][x]={
0,0,0,7,5,0,0,0,0,
0,3,0,0,4,8,0,2,0,
1,0,0,0,0,0,0,0,6,
0,4,0,0,0,0,0,0,8,
7,9,0,0,0,0,0,3,1,
2,0,0,0,0,0,0,7,0,
5,0,0,0,0,0,0,0,7,
0,8,0,3,2,0,0,4,0,
0,0,0,0,6,9,0,0,0
};
其中x为9，0代表空格。这是一个二维数组，按C语言来定行列，如第1行的7其行列为[0][3]。人工解题首先考虑的是哪一个空格只有唯一解，由本题可见，a[4][4]只能填8，因为其行、列或区中已经有了除8以外其它1-9的8个数据；写入8之后，接下来可在a[6][4]写入1、a[6][5]写入4、a[6][3]写入8、a[8][3]写入5、a[7][5]写入7。
人可以一眼看出象这样的唯一解，但计算机不行，必须用相应的程序来实现此功能。首先需要对行中的整数0进行计数，记录其相应位置。然后寻找每一行、每一列、每一区中缺少的整数。不提倡用随机数来生成数据，一来没有必要，二来用循环及判断很容易找到缺少的数据。最后找出每个空格可写入的整数(即候选数)与每个空格总共可写入几个整数(即个数)。找候选数及其个数的程序较难，以此为例略加说明：
for (r=0; r<x; r++)
for (h=0; h<rowcnt[r]; h++)
{
n=r/3;
t=wei[r][h];
m=t/3+3*n;
if(b[r][t]==0)
{
for (j=0; j<colcnt[t]; j++)
{
for (i=0; i<rowcnt[r]; i++)
{
if (roww[r][i]>0 && roww[r][i]==colw[t][j])
//寻找相同的整数
//首先是每行缺少的整数与列中的第1个数比较
//然后是列中的每行数据依次被比较
//再是wei的位置进行移动
//最后是换到下一行
{
aflag = 1;
break; //跳出i
}
else
aflag =0;
}//--end for i
if (aflag ==1)
{
for (q=0; q<newcnt[m]; q++)
{
if (neww[m][q]==roww[r][i])
{ xian[r][h][rowk]=roww[r][i];
rowk++;
break;//跳出q
}
}
} //end if (aflag ==1)
aflag=0;
} // end for j
}//end if(b[r][t]==0)
samecnt[r][h] = rowk;
rowk = 0;
} // end for h
|
