对角线数独的LINGO求解模型

摘要：对角线数独是一个变形数独，该文根据对角线数独的求解规则，建立了与对角线数独的解等价的0-1整数线性规划模型。并用专门求解0-1整数线性规划模型的LINGO软件实现求解，最后用中级对角线数独谜题表明该方法的有效性。

关键词：对角线数独；线性规划； 等价性

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）12-0091-03

LINGO Model for Diagonal Sudoku Problem

MA Li-na

（Department of Information， Xingzhi College of Xi'an University of Finance and Economics， Xian 710038， China）

Abstract： Diagonal Sudoku is a variation of the classical Sudoku problem. In this paper， an integer program model based on the rules for Diagonal Sudoku is proposed. Moreover， the LINGO model for solving the integer program is given. Lastly， an example is used to demonstrate the effectiveness of the proposed model.

Key words： diagonal sudoku； linear program； equivalent

数独是逻辑性很强的数字智力拼图游戏[1-2]，它于1979年首次在美国的一家数学逻辑游戏杂志—Dell Pencil Puzzles & Word Games上出现，当时称之为“NumberPlace” 游戏。数独在上世纪八十年代传入日本，并且正式命名为Sudoku，意为“数字必须是唯一的”。数独的规则很容易理解，即在9行9列的九宫格里填入合适的数字，使得每行，每列以及每个九宫格内所填数字从1到9且互不相等。通常在设计谜题时要求每个数独有唯一解。数独解的性质有删除候选数性质、唯一确定性质（显式唯一法和隐式唯一法）、矛盾性质以及枚举不变性（单元格的枚举和区的枚举）。

许多著名的学者分析数独的结构，对数独谜题的生成算法和求解技巧有大量的研究，并取得了一些结论。数独的生成算法有用进化算法来解决数独并对其进行难度分级从而生成不同难度的数独，和基于最小候选数生成数独的算法。数独的求解算法有回溯法[3]、不动点法[4]、枚举算法[5]、遗传算法[6]等等。

经过发展和创新，涌现出越来越多的变形数独，不断充实着数独家族。变形数独题目大行其道，其趣味性和益智性都有着不同程度的提高，变形数独受到来自世界各地数独爱好者的追捧。所谓“变形数独”，是在标准数独（9*9的数独）的基础上，加入额外的限制条件和规则而得到各种形形色色的新数独谜题。例如，对角线数独、老板数独[7]、蜂巢数独、金字塔数独、彩虹数独、杀手数独、超级数独等等。

对角线数独（如图1）不仅要求每行、每列、每个九宫格内所填数字从1～9不重复，还要求两条对角线内所填数字从1～9不重复，它是在标准数独谜题的基础上添加了两个限制条件。

1 0-1整数线性规划模型

为了方便起见，数独中的每个格子用一个二元组 来表示。 这里 和 分别表示行号和列号（从左上角开始表示）。建立决策变量：

目标函数为：

根据对角线数独的求解规则，建立如下约束条件：

1）每个格子只能填1-9中的一个数字：

2）每行1-9中每个数字只能填一次：

3）每列1-9中每个数字只能填一次：

4）每个九宫格内1-9中每个数字只能填一次：

其中， 表示九个 的小九宫格。

5）主对角线（从左上到右下）上1-9中每个数字只能填一次：

6）次对角线（从左下到右上）上1-9中每个数字只能填一次：

7）要求每个决策变量为0-1变量：

则求解对角线数独的0-1整数线性规划模型为：

初始条件可根据原始数独初盘中某些格子中已填的数字给出。例如，在图1所示的对角线数独中，格子（1，1）已填数字为9，则 。

2 对角线数独的LINGO求解

LINGO是一种专门用于求解数学规划问题的软件包。由于LINGO执行速度快，易于方便地输入、求解和分析数学规划问题，因此在教学、科研和工业界有着广泛应用。LINGO主要用于求解线性规划、非线性规划、二次规划和整数规划等问题，也可以求解一些线性和非线性方程组及代数方程求根等问题。

求解图1的中级对角线数独谜题，该谜题的解与建立的0-1整数线性规模模型的解等价。求解整数线性规划模型的解的Lingo程序如下：

model：

sets：

number/1..9/；

line/1..9/；

col/1..9/；

link（line，col，number）：x；

endsets

data：

！只输出大于0的值；

@text（）=@writefor（link（i，j，k）|x（i，j，k）#GT#0：'x（'，i，'，'，j，'，'，k，'）='，x（i，j，k），' '）；

enddata

max=@sum（link（i，j，k）：x（i，j，k））； ！建立目标函数；

！每个空格只填一个数；

@for（line（i）：@for（col（j）：@sum（number（k）：x（i，j，k））=1））；

！每行每个数字只填一次；

@for（line（i）：@for（number（k）：@sum（col（j）：x（i，j，k））=1））；

！每列每个数字只填一次；

@for（col（j）：@for（number（k）：@sum（line（i）：x（i，j，k））=1））；

！每个九宫格每个数字只填一次；

@for（number（k）：@sum（line（i）|i#GE#1#and#i#LE#3：@sum（col（j）|j#GE#1#and#j#LE#3：x（i，j，k）））=1）；

@for（number（k）：@sum（line（i）|i#GE#1#and#i#LE#3：@sum（col（j）|j#GE#4#and#j#LE#6：x（i，j，k）））=1）；

@for（number（k）：@sum（line（i）|i#GE#1#and#i#LE#3：@sum（col（j）|j#GE#7#and#j#LE#9：x（i，j，k）））=1）；

@for（number（k）：@sum（line（i）|i#GE#4#and#i#LE#6：@sum（col（j）|j#GE#1#and#j#LE#3：x（i，j，k）））=1）；

@for（number（k）：@sum（line（i）|i#GE#4#and#i#LE#6：@sum（col（j）|j#GE#4#and#j#LE#6：x（i，j，k）））=1）；

@for（number（k）：@sum（line（i）|i#GE#4#and#i#LE#6：@sum（col（j）|j#GE#7#and#j#LE#9：x（i，j，k）））=1）；

@for（number（k）：@sum（line（i）|i#GE#7#and#i#LE#9：@sum（col（j）|j#GE#1#and#j#LE#3：x（i，j，k）））=1）；

@for（number（k）：@sum（line（i）|i#GE#7#and#i#LE#9：@sum（col（j）|j#GE#4#and#j#LE#6：x（i，j，k）））=1）；

@for（number（k）：@sum（line（i）|i#GE#7#and#i#LE#9：@sum（col（j）|j#GE#7#and#j#LE#9：x（i，j，k）））=1）；

！主对角线每个数字只填一次；

@for（number（k）：@sum（line（i）：x（i，i，k））=1））；

！次对角线每个数字只填一次；

@for（number（k）：@sum（line（i）：x（i，9-i+1，k））=1））；

！0-1变量约束；

@for（link（i，j，k）：@bin（x（i，j，k）））；

End

计算时间在毫秒级。求解结果如图2：

3 结论

本文针对对角线数独谜题建立了与之等价的0-1整数线性规划模型，并用LINGO实现了求。数值实例证明，算法的计算时间在毫秒级。但是对于空格比较多的数独难题，LINGO不能实现求解或者计算时间比较长。这时需要考虑改进算法，这也是本文下一步研究的问题。

参考文献：

[1] 晓木. 数独的历史[J]. 青年科学， 2009 （10）： 55-55.

[2] 李盘荣. “数独” 游戏的算法研究与实现[J]. 电脑知识与技术， 2008， 46（3）： 1715-1717.

[3] 胥剑. 回溯法解数独问题[J]. 电脑编程技巧与维护，2009（5）： 17-41.

[4] 顾雏军. 顾氏不动点解法——数独题通用解法[J]. 北华航天工业学院学报， 2008， 18（1）： 47-49.

[5] 肖华勇， 田铮， 马雷. 数独基于规则的逐步枚举算法设计[J]. 计算机工程与设计， 2010 （5）： 1035-1037.

[6] 刘延风， 刘三阳. 基于遗传算法求解数独难题[J]. 计算机科学， 2010 （3）： 445-446.

[7] 肖华勇， 马丽娜， 程海礁. 老板数独的方程求解算法研究[J]. 计算机工程与应用， 2014， 50（9）： 41-44.