1.1概述

数独，如图一所示，源于18世纪数学家欧拉发明的拉丁方阵，后在美国发展、并在日本得以发扬光大的数字谜题。数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只

图一 数独实例

出现一次。然而，尽管数独号称是一种数学问题，却几乎用不上数学运算方法。事实上，它只需要一定的逻辑推理加上必要的耐心就可以了。理论上，我们可以将数字代换成另外九种不同的符号，例如字母、颜色、图像等。数独游戏成功的原因除了它的趣味性和挑战性之外，更重要的原因其实是因为它很容易上手.不过，数独倒是提供给数学家和计算机学家许多挑战性的课题。

1.2国内外研究现状

目前求解数独的方法主要有两种，一种是基于计算机的回溯法或类似的全枚举方法，另一种方法就是基于人的思维，寻找求解的特殊技巧，如数独终结者软件分别总结了直观法和候选数法两大类，其中直观法有：单元唯一法、单元排除法、区块排除法、唯一余数法、组合排除法、矩阵排除法；候选数法有：显式唯一法、隐式唯一法、区块删减法、显式数对法、显式三数集法、显式四数集法、隐式数对法、隐式三数集法、隐式四数集法、矩形对角线法、XY形态匹配法、XYZ形态匹配法、三链数删减法、WXYZ形态匹配法。这些方法过分注重具体的技巧，缺乏一般性。

而同时，国内外很多专家学者都提出了解决数独问题的计算机算法，如文献[1]中提出的基于排除填充模型的填充算法。在文献[1]作者构造了一种排除填充法的数学模型，将填充过程分成三部分:行填充、列填充和宫填充。

将九宫格数独看做是一个9*9 的矩阵，那么就可用a_ij（1lt;＝ilt;＝9，1lt;=jlt;＝9）表示数独第i行，第j列格子里的数字。设a_i1，a_i2，…，a_im（1lt;=mlt;9）是数独中第i行已经填充好的m个数字。首先，去掉1到9 这九个数中的a_ij，a_i2，…a_im，剩下的数a_{i(m 1)}，a_{i(m 2)}，…，a_i9 就是要填充在第i行剩下的9-m 个空白格子里的数。假设aik(m 1lt;=klt;=)填充在第i行第j（1lt;=jlt;=9-m）个空白格子里，如果第i行第j个空白格子所处的列位置以及它所对应的宫位置中，任何一个格子里的数字与a_ik 都不相同，那么称a_ik适合填充在第ｉ行第ｊ个空白格子里，否则，称a_ik不适合填充在第ｉ行第ｊ个空白格子里。行模型是这样一种填充原则：如果第ｉ行有且仅有一个空白格子适合填a_ik（m 1lt;=klt;=9），那么a_jk一定填充在该位置，否则，a_ik不填充。用类似的方法，我们可以完成列模型和宫模型。

通过建立排除法填充数独的数学模型，在此基础上，找到利用计算机实现填充数独游戏的一种算法。该算法的优点是填充效率高，速度快，不足的地方是该算法不能保证所有的数独都能进行填充，这主要是由数独本身的结构造成的。