柯春梅

（厦门海洋职业技术学院基础部 福建 厦门 361101 ）

杀手数独是一种数学智力游戏，它结合了数独和数和的玩法。出题者将数独的81个格子用虚线分成若干个区域，每个区域由相邻的若干个格子组成，并在每个区域的左上角给出这个区域的所有格子内数字的总和，规定数独参与者不仅要遵守数独的要求，并且还要满足各区域数字之和的要求来完成数独题，就是在空格内填上1～9的数字，使每个数字在每一行、每一列、每个标有粗线的宫内只能出现一次，虚线框出的区域内所有数字之和等于虚线框左上角标注的数字，并且同一虚线框内的数字不能重复，这就是杀手数独，也称分组数字和数独[1],[2]，图1就是一题杀手数独[2]。

图1 杀手数独

LINGO是求解优化问题的专业软件包，它内置建模语言，提供几十个内部函数，从而能以较少的语句，较直观的方式描述大规模的优化模型，而且它的运算速度快，计算结果可靠[3],[4]。国内许多学者对利用计算机进行快速求解数独的算法进行深入研究与探索，这些算法多数以回溯法为基础，结合各种预处理提高算法的执行速度[5]-[9]，根据数独的求解规则建立数学模型，并给予求解的研究不多[10],[11]，对于杀手数独的建模与求解问题，目前尚未看到相关研究。

1.杀手数独的数学规划模型的建立过程

杀手数独初盘没有给定数，只给出虚线框内数字和，而虚线框所框出的区域变化无常，建立数学模型必须根据具体题目来建立，下面根据图1所示杀手数独分析数学模型的建立过程。

为了方便起见，（i,j）（i,j=1，2，……，9）表示数独盘面中处于第i行第j列的格子，(m=1,2,……,9)表示第 m宫，其中 int表示向下取整。aij表示数独初盘格子(i,j)处所填的数，其中0表示该格子未填数，杀手数独初盘没有给定的数，所以初盘中81个格子都填0，yij(i,j=1,2,……,9)表示数独完成后格子(i,j)处所填的数。

引入三元0-1变量

目标函数：

数独完成后，数独盘上每个格子都填上 1～9的一个数字，且满足每个数字在每一行、每一列、每个宫内不能重复，因此目标函数为

约束条件：

与决策变量的关系；

（2）每个格子（i,j)处恰好填数字 1～9中的一个数；

（3）每行1～9中的每个数只能填一次；

（4）每列1～9中的每个数只能填一次；

（5）每个宫1～9中的每个数只能填一次；

（6）xijk是0-1变量；

（7）虚线框出的区域数字之和等于虚线框左上角标注的数字，根据具体题目确定；

（8）虚线框内的数字不能重复：如果虚线框区域内的格子在同一行、同一列或者同一宫内，则他们的数字已经满足没有重复，如果虚线框区域内的格子至少有两个不在同一行、同一列或者同一宫内，则应增加虚线框内的数两两只差的乘积的绝对值大于零作为约束条件。

因此图1所示杀手数独的数学模型为：

2.杀手数独的Lingo求解程序设计

根据上述杀手数独的数学模型，利用 LINGO软件的内置函数@for、@sum、@floor及@abs编制求解程序，由于 LINGO软件中“<”表示“小于等于”，“>”表示“大于等于”，因此要表示两个数不相等，要用两个数的差的绝对值大于一个很小的正数来表示。因此图 1所示杀手数独的Lingo求解程序如下：

即得到图1所示杀手数独的解如图2.

图2 杀手数独的解

3.计算实验

杀手数独是一种变形数独，对于每一题杀手数独，目标函数都相同，约束条件中（1）～（6）是相同的，约束条件（7）和（8）则需要根据不同题目来编制。图3、图4、图5所示的杀手数独是数独三段段位考试模拟试题，根据题目所给虚线框及其标注的数字修改LINGO求解程序，进行求解，运行后得到它的解，运算速度不足1秒，运算结果准确。

图3 模拟试题1杀手数独及其解

图4 模拟试题2杀手数独及其解

图5 模拟试题3杀手数独及其解

4.结语

杀手数独作为一种数学智力游戏，既具有逻辑性、可推理性，又具有数字和的运算性，建立数学模型，利用 LINGO软件求解大规模规划模型的功能编制求解程序，可以快速准确地得到答案。本文以一题杀手数独为例，建立对应的数学规划模型，编制LINGO求解程序，快速准确得到答案，然后根据三道数独三段段位考试模拟试题，修改部分约束条件，仍可快速准确得到答案，说明这种程序准确，同时具有可复制性。