吴 涛

(西安航空学院 理学院，陕西 西安710077)

引言

九宫格数独，是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数字谜题[1]。数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9这九个数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。这种游戏全面考验做题者的观察能力和推理能力，虽然玩法简单，但数字排列方式却千变万化[2]，所以不少教育者认为数独是训练头脑的绝佳方式。但是目前使用的数独解算器[3-5]，以试探性的遍历算法进行填充，耗时过长。通过建立排除填充法的数学模型，并在此基础上提出一种新型的填充数独游戏的算法[6]，通过Matlab编程[7]，在计算机上得以实现。

1 建立数学模型

1.1 数独游戏简介

如图1所示，数独盘面是九个宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。

图1 数独

1.2 排除法填充模型

1.2.1 行填充模型

将九宫格数独看做是一个9*9的矩阵，那么就可用aij(1<=i<=9,1<=j<=9)表示数独第i行，第j列格子里的数字。设ai1,ai2,…,aim(1<=m<9)是数独中第i行已经填充好的m个数字。

首先，去掉1-9这九个数中的ai1,ai2,…aim,剩下的数ai(m+1),ai(m+2),…，ai9就是要填充在第i行剩下的9-m个空白格子里的数。假设aik(m+1<=k<=9)填充在第i行第j(1<=j<=9-m)个空白格子里，如果第i行第j个空白格子所处的列位置以及它所对应的宫位置中，任何一个格子里的数字与aik都不相同，那么称aik适合填充在第i行第j个空白格子里，否则，称aik不适合填充在第i行第j个空白格子里。

行模型是这样一种填充原则：如果第i行有且仅有一个空白格子适合填aik(m+1<=k<=9)，那么aik一定填充在该位置，否则，aik不填充。

1.2.2 列填充模型

将九宫格数独看做是一个9*9的矩阵，那么就可用aij(1<=i<=9,1<=j<=9)表示数独第i行，第j列格子里的数字。设a1j,a2j,…,amj(1<=m<9)是数独中第j列已经填充好的m个数字。

首先，去掉1-9这九个数中的a1j，a2j，…，amj，剩下的数a(m+1)j，a(m+2)j，…，a9j就是要填充在第j列剩下的9-m个空白格子里的数。……