對角線數(shù)獨(dú)的LINGO求解模型

摘要：對角線數(shù)獨(dú)是一個(gè)變形數(shù)獨(dú)，該文根據(jù)對角線數(shù)獨(dú)的求解規(guī)則，建立了與對角線數(shù)獨(dú)的解等價(jià)的0-1整數(shù)線性規(guī)劃模型。并用專門求解0-1整數(shù)線性規(guī)劃模型的LINGO軟件實(shí)現(xiàn)求解，最后用中級對角線數(shù)獨(dú)謎題表明該方法的有效性。

關(guān)鍵詞：對角線數(shù)獨(dú)；線性規(guī)劃； 等價(jià)性

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

數(shù)獨(dú)是邏輯性很強(qiáng)的數(shù)字智力拼圖游戲[1-2]，它于1979年首次在美國的一家數(shù)學(xué)邏輯游戲雜志—Dell Pencil Puzzles & Word Games上出現(xiàn)，當(dāng)時(shí)稱之為“NumberPlace” 游戲。數(shù)獨(dú)在上世紀(jì)八十年代傳入日本，并且正式命名為Sudoku，意為“數(shù)字必須是唯一的”。數(shù)獨(dú)的規(guī)則很容易理解，即在9行9列的九宮格里填入合適的數(shù)字，使得每行，每列以及每個(gè)九宮格內(nèi)所填數(shù)字從1到9且互不相等。通常在設(shè)計(jì)謎題時(shí)要求每個(gè)數(shù)獨(dú)有唯一解。數(shù)獨(dú)解的性質(zhì)有刪除候選數(shù)性質(zhì)、唯一確定性質(zhì)（顯式唯一法和隱式唯一法）、矛盾性質(zhì)以及枚舉不變性（單元格的枚舉和區(qū)的枚舉）。

許多著名的學(xué)者分析數(shù)獨(dú)的結(jié)構(gòu)，對數(shù)獨(dú)謎題的生成算法和求解技巧有大量的研究，并取得了一些結(jié)論。數(shù)獨(dú)的生成算法有用進(jìn)化算法來解決數(shù)獨(dú)并對其進(jìn)行難度分級從而生成不同難度的數(shù)獨(dú)，和基于最小候選數(shù)生成數(shù)獨(dú)的算法。數(shù)獨(dú)的求解算法有回溯法[3]、不動(dòng)點(diǎn)法[4]、枚舉算法[5]、遺傳算法[6]等等。

經(jīng)過發(fā)展和創(chuàng)新，涌現(xiàn)出越來越多的變形數(shù)獨(dú)，不斷充實(shí)著數(shù)獨(dú)家族。變形數(shù)獨(dú)題目大行其道，其趣味性和益智性都有著不同程度的提高，變形數(shù)獨(dú)受到來自世界各地?cái)?shù)獨(dú)愛好者的追捧。所謂“變形數(shù)獨(dú)”，是在標(biāo)準(zhǔn)數(shù)獨(dú)（9*9的數(shù)獨(dú)）的基礎(chǔ)上，加入額外的限制條件和規(guī)則而得到各種形形色色的新數(shù)獨(dú)謎題。例如，對角線數(shù)獨(dú)、老板數(shù)獨(dú)[7]、蜂巢數(shù)獨(dú)、金字塔數(shù)獨(dú)、彩虹數(shù)獨(dú)、殺手?jǐn)?shù)獨(dú)、超級數(shù)獨(dú)等等。

對角線數(shù)獨(dú)（如圖1）不僅要求每行、每列、每個(gè)九宮格內(nèi)所填數(shù)字從1～9不重復(fù)，還要求兩條對角線內(nèi)所填數(shù)字從1～9不重復(fù)，它是在標(biāo)準(zhǔn)數(shù)獨(dú)謎題的基礎(chǔ)上添加了兩個(gè)限制條件。

1 0-1整數(shù)線性規(guī)劃模型

為了方便起見，數(shù)獨(dú)中的每個(gè)格子用一個(gè)二元組 來表示。 這里 和 分別表示行號(hào)和列號(hào)（從左上角開始表示）。建立決策變量：

目標(biāo)函數(shù)為：

根據(jù)對角線數(shù)獨(dú)的求解規(guī)則，建立如下約束條件：

1）每個(gè)格子只能填1-9中的一個(gè)數(shù)字：

2）每行1-9中每個(gè)數(shù)字只能填一次：

3）每列1-9中每個(gè)數(shù)字只能填一次：

4）每個(gè)九宮格內(nèi)1-9中每個(gè)數(shù)字只能填一次：

其中， 表示九個(gè) 的小九宮格。

5）主對角線（從左上到右下）上1-9中每個(gè)數(shù)字只能填一次：

6）次對角線（從左下到右上）上1-9中每個(gè)數(shù)字只能填一次：

7）要求每個(gè)決策變量為0-1變量：

則求解對角線數(shù)獨(dú)的0-1整數(shù)線性規(guī)劃模型為：

初始條件可根據(jù)原始數(shù)獨(dú)初盤中某些格子中已填的數(shù)字給出。例如，在圖1所示的對角線數(shù)獨(dú)中，格子（1，1）已填數(shù)字為9，則 。

2 對角線數(shù)獨(dú)的LINGO求解

LINGO是一種專門用于求解數(shù)學(xué)規(guī)劃問題的軟件包。由于LINGO執(zhí)行速度快，易于方便地輸入、求解和分析數(shù)學(xué)規(guī)劃問題，因此在教學(xué)、科研和工業(yè)界有著廣泛應(yīng)用。LINGO主要用于求解線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃和整數(shù)規(guī)劃等問題，也可以求解一些線性和非線性方程組及代數(shù)方程求根等問題。

求解圖1的中級對角線數(shù)獨(dú)謎題，該謎題的解與建立的0-1整數(shù)線性規(guī)模模型的解等價(jià)。求解整數(shù)線性規(guī)劃模型的解的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））； ！建立目標(biāo)函數(shù)；

！每個(gè)空格只填一個(gè)數(shù)；

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

！每行每個(gè)數(shù)字只填一次；

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

！每列每個(gè)數(shù)字只填一次；

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

！每個(gè)九宮格每個(gè)數(shù)字只填一次；

@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）；

！主對角線每個(gè)數(shù)字只填一次；

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

！次對角線每個(gè)數(shù)字只填一次；

@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

計(jì)算時(shí)間在毫秒級。求解結(jié)果如圖2：

3 結(jié)論

本文針對對角線數(shù)獨(dú)謎題建立了與之等價(jià)的0-1整數(shù)線性規(guī)劃模型，并用LINGO實(shí)現(xiàn)了求。數(shù)值實(shí)例證明，算法的計(jì)算時(shí)間在毫秒級。但是對于空格比較多的數(shù)獨(dú)難題，LINGO不能實(shí)現(xiàn)求解或者計(jì)算時(shí)間比較長。這時(shí)需要考慮改進(jìn)算法，這也是本文下一步研究的問題。

參考文獻(xiàn)：

[1] 曉木. 數(shù)獨(dú)的歷史[J]. 青年科學(xué)， 2009 （10）： 55-55.

[2] 李盤榮. “數(shù)獨(dú)” 游戲的算法研究與實(shí)現(xiàn)[J]. 電腦知識(shí)與技術(shù)， 2008， 46（3）： 1715-1717.

[3] 胥劍. 回溯法解數(shù)獨(dú)問題[J]. 電腦編程技巧與維護(hù)，2009（5）： 17-41.

[4] 顧雛軍. 顧氏不動(dòng)點(diǎn)解法——數(shù)獨(dú)題通用解法[J]. 北華航天工業(yè)學(xué)院學(xué)報(bào)， 2008， 18（1）： 47-49.

[5] 肖華勇， 田錚， 馬雷. 數(shù)獨(dú)基于規(guī)則的逐步枚舉算法設(shè)計(jì)[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2010 （5）： 1035-1037.

[6] 劉延風(fēng)， 劉三陽. 基于遺傳算法求解數(shù)獨(dú)難題[J]. 計(jì)算機(jī)科學(xué)， 2010 （3）： 445-446.

[7] 肖華勇， 馬麗娜， 程海礁. 老板數(shù)獨(dú)的方程求解算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2014， 50（9）： 41-44.