數(shù)獨的數(shù)學(xué)模型與LINGO求解程序

柯春梅

(廈門海洋職業(yè)技術(shù)學(xué)院基礎(chǔ)部，福建廈門 361101)

?

數(shù)獨的數(shù)學(xué)模型與LINGO求解程序

柯春梅

(廈門海洋職業(yè)技術(shù)學(xué)院基礎(chǔ)部，福建廈門 361101)

本文首先從標(biāo)準(zhǔn)數(shù)獨的條件與規(guī)則出發(fā)，引入三元0-1變量，建立標(biāo)準(zhǔn)數(shù)獨的0-1整數(shù)規(guī)劃模型，根據(jù)模型設(shè)計LINGO求解程序，用一個數(shù)獨難題進(jìn)行驗證，說明程序計算的準(zhǔn)確性；然后將標(biāo)準(zhǔn)數(shù)獨的LINGO求解程序推廣到窗口數(shù)獨、額外區(qū)域數(shù)獨、奇偶數(shù)獨等三種變形數(shù)獨的求解；最后利用數(shù)獨聯(lián)盟五段段位考試訓(xùn)練題進(jìn)行驗證，運算時間不超過2秒，準(zhǔn)確率達(dá)到100%，說明這些LINGO程序求解數(shù)獨問題，速度快且結(jié)果準(zhǔn)確可靠。

LINGO軟件；標(biāo)準(zhǔn)數(shù)獨；0-1整數(shù)規(guī)劃；變形數(shù)獨

LINGO是求解優(yōu)化問題的專業(yè)軟件包，它內(nèi)置建模語言，提供幾十個內(nèi)部函數(shù)，從而能以較少的語句、較直觀的方式描述大規(guī)模的優(yōu)化模型，它的運算速度快，計算結(jié)果可靠[1]。

所謂標(biāo)準(zhǔn)數(shù)獨，就是用9×9的方陣構(gòu)成81個格子，其中9個用粗線分隔的區(qū)域稱為宮，在其中的一些格子里已經(jīng)填上了1到9之間的數(shù)字，還留下若干空格，要求數(shù)獨參與者將這些格子填滿，結(jié)果滿足每一行、每一列、每個宮的9個數(shù)字都是由1到9組成，沒有重復(fù)數(shù)字[2]。數(shù)獨聯(lián)盟將標(biāo)準(zhǔn)數(shù)獨進(jìn)行變形，推出多種變形數(shù)獨。數(shù)獨游戲全面考驗做題者的觀察能力和推理能力，雖然玩法簡單，但數(shù)字排列方式卻千變?nèi)f化，所以不少教育者認(rèn)為數(shù)獨游戲是訓(xùn)練頭腦的絕佳方式。國內(nèi)許多學(xué)者對數(shù)獨的教學(xué)意義進(jìn)行討論，用計算機進(jìn)行快速求解的算法，這些算法多數(shù)以回溯法為基礎(chǔ)，結(jié)合各種預(yù)處理提高算法的執(zhí)行速度[3-7]，而對通過建立數(shù)學(xué)模型、利用數(shù)學(xué)軟件進(jìn)行求解的算法的研究很少[8-9]。本文將標(biāo)準(zhǔn)數(shù)獨的求解程序推廣到窗口數(shù)獨、額外區(qū)域數(shù)獨和奇偶數(shù)獨的求解程序，快速準(zhǔn)確求解數(shù)獨問題，同時訓(xùn)練LINGO軟件的使用技巧。該研究實現(xiàn)了運用數(shù)學(xué)軟件快速準(zhǔn)確求解變形數(shù)獨。

1 標(biāo)準(zhǔn)數(shù)獨的數(shù)學(xué)模型與LINGO求解程序

宮的行狀為3×3正方形的數(shù)獨稱為標(biāo)準(zhǔn)數(shù)獨，圖1就是一個標(biāo)準(zhǔn)數(shù)獨[3]。

圖1 標(biāo)準(zhǔn)數(shù)獨

圖2 標(biāo)準(zhǔn)數(shù)獨的解

1.1 標(biāo)準(zhǔn)數(shù)獨的數(shù)學(xué)模型

其中，(1)表示yij與決策變量的關(guān)系；(2)表示每個格子(i,j)處只能填1～9中的一個數(shù)；(3)表示每行1～9中的每個數(shù)只能填一次；(4)表示每列1～9中的每個數(shù)只能填一次；(5)表示每個區(qū)1～9中的每個數(shù)只能填一次。

1.2 標(biāo)準(zhǔn)數(shù)獨的LINGO求解程序

利用LINGO編程語言，對標(biāo)準(zhǔn)數(shù)獨建立的0-1整數(shù)規(guī)劃模型進(jìn)行程序設(shè)計，其求解程序如下：

model:

sets:

number/1..9/;line/1..9/;col/1..9/;gong/1..9/;

shudu(line,col):y,a;

link(line,col,number):x;

endsets

data:

! 鍵盤輸入;

a=？;

enddata

min=@sum(link:x);

@for(shudu(i,j) | a(i,j) #ge# 1:x(i,j,a(i,j))=1);

@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(line(i):@for(col(j):y(i,j)=@sum(number(k):k*x(i,j,k))));

@for(gong(m):@for(number(k):@sum(link(i,j,k)| 3*@floor((i-1)/3)+@floor((j-1)/3)+1 #eq# m:x(i,j,k))=1));

@for(link(i,j,k):@bin(x(i,j,k)));

End

1.3 標(biāo)準(zhǔn)數(shù)獨的求解

運用上述程序求解標(biāo)準(zhǔn)數(shù)獨問題時，只需在鍵盤輸入數(shù)獨初盤，其中未填數(shù)的格子填上0，運行后就可得到數(shù)獨的解。

圖1所示標(biāo)準(zhǔn)數(shù)獨是文獻(xiàn)[3]中的失敗案例，在上述程序中，通過鍵盤中輸入數(shù)據(jù)

a=0 4 0 0 0 6 0 0 5 0 0 0 7 0 0 1 0 0 0 0 0 0 0 0 8 0 2 0 0 0 2 0 1 0 0 0 0 9 0 0 0 0 0 3 0 0 0 0 0 0 8 0 0 0 0 0 0 0 4 0 0 7 0 1 0 5 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0;

運行后得到圖1所示數(shù)獨的解，如圖2所示，其中帶圈的數(shù)字是數(shù)獨初盤提供的數(shù)字(下同)。

2 變形數(shù)獨的數(shù)學(xué)模型與LINGO求解程序

所謂變形數(shù)獨，就是增加或改變標(biāo)準(zhǔn)數(shù)獨的一些條件或規(guī)則，形成的新型數(shù)獨題目。常見的變形數(shù)獨有兩類：一類是增加標(biāo)準(zhǔn)數(shù)獨的一些條件或規(guī)則，如對角線數(shù)獨、窗口數(shù)獨、額外區(qū)域數(shù)獨、奇偶數(shù)獨等；另一類是改變標(biāo)準(zhǔn)數(shù)獨的一些條件或規(guī)則，如不規(guī)則數(shù)獨(鋸齒數(shù)獨、分區(qū)數(shù)獨)、殺手?jǐn)?shù)獨(分組數(shù)字和數(shù)獨)等。

2.1 窗口數(shù)獨的數(shù)學(xué)模型與LINGO求解程序

除了標(biāo)準(zhǔn)數(shù)獨的要求之外，再加上4個灰色窗口內(nèi)也必須包含1～9的規(guī)定的數(shù)獨，稱為窗口數(shù)獨，即“每行、每列及每個3×3的九宮格、每個灰色窗口都要包含數(shù)字1～9”的數(shù)獨，圖3就是一個窗口數(shù)獨[10]。

圖3 窗口數(shù)獨

圖4 窗口數(shù)獨的解

在標(biāo)準(zhǔn)數(shù)獨的LINGO求解程序中增加如下4個語句，就可以得到窗口數(shù)獨的LINGO求解程序。

@for(number(k):(x(2,2,k)+x(2,3,k)+x(2,4,k)+x(3,2,k)+x(3,3,k)+x(3,4,k)+x(4,2,k)+x(4,3,k)+x(4,4,k))=1);

@for(number(k):(x(6,2,k)+x(6,3,k)+x(6,4,k)+x(7,2,k)+x(7,3,k)+x(7,4,k)+x(8,2,k)+x(8,3,k)+x(8,4,k))=1);

@for(number(k):(x(2,6,k)+x(2,7,k)+x(2,8,k)+x(3,6,k)+x(3,7,k)+x(3,8,k)+x(4,6,k)+x(4,7,k)+x(4,8,k))=1);

@for(number(k):(x(6,6,k)+x(6,7,k)+x(6,8,k)+x(7,6,k)+x(7,7,k)+x(7,8,k)+x(8,6,k)+x(8,7,k)+x(8,8,k))=1);

在窗口數(shù)獨求解程序中，通過鍵盤輸入數(shù)獨初盤，運行后可以得到窗口數(shù)獨的解。例如通過鍵盤輸入數(shù)據(jù)：

a=0 0 0 3 0 8 0 0 0 0 0 0 1 0 0 0 2 0 0 6 4 0 0 0 0 0 0 3 0 0 0 0 0 0 0 8 4 0 0 0 5 3 0 0 0 9 0 0 0 0 0 0 0 7 0 9 7 0 0 0 0 0 0 0 0 0 5 0 0 0 8 0 0 0 0 2 0 6 0 0 0;

運行后可以得到圖3所示窗口數(shù)獨的解，如圖4所示。

2.2 用LINGO軟件編程求解額外區(qū)域數(shù)獨和奇偶數(shù)獨

在標(biāo)準(zhǔn)數(shù)獨的基礎(chǔ)上添加了兩組額外區(qū)域(每個區(qū)域含有9個格子)，在滿足標(biāo)準(zhǔn)數(shù)獨規(guī)則的基礎(chǔ)上，兩組額外區(qū)域上的數(shù)字一樣必須是1～9，這種數(shù)獨稱為額外區(qū)域數(shù)獨，圖5就是一個額外區(qū)域數(shù)獨[10]；在標(biāo)準(zhǔn)數(shù)獨的基礎(chǔ)上，指定36個灰色格子，在滿足標(biāo)準(zhǔn)數(shù)獨規(guī)則的基礎(chǔ)上，要求灰色格子內(nèi)的數(shù)字為偶數(shù)，白色格子內(nèi)的數(shù)字為奇數(shù)，這種數(shù)獨稱奇偶數(shù)獨，圖6就是一個奇偶數(shù)獨[10]。

圖5 額外區(qū)域數(shù)獨

圖6 奇偶數(shù)獨

額外區(qū)域數(shù)獨的特點是其額外區(qū)域的形狀變化無常，奇偶數(shù)獨的特點是灰色格子變化無常，因此這兩種數(shù)獨的數(shù)學(xué)模型及LINGO求解程序應(yīng)根據(jù)具體題目具體編寫。下面給出圖5所示額外區(qū)域數(shù)獨和圖6所示奇偶數(shù)獨的LINGO求解程序。

圖5示額外區(qū)域數(shù)獨的LINGO求解程序為：

model:

sets:

number/1..9/;line/1..9/;col/1..9/;gong/1..9/;

shudu(line,col):y,a;

link(line,col,number):x;

endsets

data:

a=0 0 0 1 0 3 0 0 0 0 3 0 0 0 0 6 0 0 0 4 0 0 0 0 0 0 0 8 0 0 0 0 0 0 9 0 4 2 0 0 0 8 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 6 0 0 0 5 8 0 0 0 0 0 0 8 0 0 0 3 0 1;

enddata

min=@sum(link:x);

@for(shudu(i,j)|a(i,j) #ge# 1:x(i,j,a(i,j))=1);

@for(line(i):@for(col(j):y(i,j)=@sum(number(k):k*x(i,j,k))));

@for(shudu(i,j)|a(i,j) #ge# 1:x(i,j,a(i,j))=1);

@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(link(i,j,k):@bin(x(i,j,k)));

@for(gong(m):@for(number(k):@sum(link(i,j,k)|3*@floor((i-1)/3)+@floor((j-1)/3)+1#eq#m:x(i,j,k))=1));

@for(number(k):(x(3,3,k)+x(3,7,k)+x(4,2,k)+x(4,4,k)+x(4,5,k)+x(4,6,k)+x(4,8,k)+x(5,3,k)+x(5,7,k))=1);

@for(number(k):(x(6,3,k)+x(6,7,k)+x(7,2,k)+x(7,4,k)+x(7,5,k)+x(7,6,k)+x(7,8,k)+x(8,3,k)+x(8,7,k))=1);

End

運行后得到額外區(qū)域數(shù)獨的解如圖7所示。

圖7 額外區(qū)域數(shù)獨的解

圖8 奇偶數(shù)獨的解

圖6所示奇偶數(shù)獨的LINGO求解程序為：

model:

sets:

number/1..9/;line/1..9/;col/1..9/;gong/1..9/;

shudu(line,col):y,a,t;

link(line,col,number):x;

endsets

data:

a=0 0 6 0 0 0 0 3 0 0 0 1 0 0 0 0 9 0 0 0 0 0 5 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 6 0 5 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 6 0 0 0 0 0 2 0 0 0 0 9 0 0 0 3 0 0 0 0 2 0 0;

enddata

min=@sum(link:x);

@for(shudu(i,j) | a(i,j) #ge# 1:x(i,j,a(i,j))=1);

@for(line(i):@for(col(j):y(i,j)=@sum(number(k):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(gong(m):@for(number(k):@sum(link(i,j,k)| 3*@floor((i-1)/3)+@floor((j-1)/3)+1 #eq# m:x(i,j,k))=1));

y(1,1)=2*t(1,1);y(1,3)=2*t(1,3);y(1,6)=2*t(1,6);y(1,7)=2*t(1,7);y(2,1)=2*t(2,1);y(2,4)=2*t(2,4);

y(2,6)=2*t(2,6);y(2,7)=2*t(2,7);y(3,2)=2*t(3,2);y(3,6)=2*t(3,6);y(3,8)=2*t(3,8);y(3,9)=2*t(3,9);

y(4,2)=2*t(4,2);y(4,3)=2*t(4,3);y(4,4)=2*t(4,4);y(4,8)=2*t(4,8);y(5,2)=2*t(5,2);y(5,4)=2*t(5,4);

y(5,5)=2*t(5,5);y(5,8)=2*t(5,8);y(6,1)=2*t(6,1);y(6,5)=2*t(6,5);y(6,7)=2*t(6,7);y(6,9)=2*t(6,9);

y(7,4)=2*t(7,4);y(7,5)=2*t(7,5);y(7,8)=2*t(7,8);y(7,9)=2*t(7,9);y(8,2)=2*t(8,2);y(8,3)=2*t(8,3);

y(8,5)=2*t(8,5);y(8,9)=2*t(8,9);y(9,1)=2*t(9,1);y(9,3)=2*t(9,3);y(9,6)=2*t(9,6);y(9,7)=2*t(9,7);

@for(link(i,j,k):@bin(x(i,j,k)));@for(shudu(i,j):@gin(t(i,j)));

End

運行后得到奇偶數(shù)獨的解如圖8所示。

3 計算實驗

運用上述程序?qū)ξ墨I(xiàn)[10]中50題標(biāo)準(zhǔn)數(shù)獨、50題窗口數(shù)獨、50題額外區(qū)域數(shù)獨、50題奇偶數(shù)獨以及文獻(xiàn)[2]中10題四級難度標(biāo)準(zhǔn)數(shù)獨和4題五級難度標(biāo)準(zhǔn)數(shù)獨進(jìn)行求解，運算時間不超過1秒鐘，正確率達(dá)到100%，對目前公認(rèn)為世界難題的芬蘭數(shù)獨進(jìn)行求解，不到1秒就能得出正確答案。

4 結(jié)語

本文根據(jù)標(biāo)準(zhǔn)數(shù)獨、窗口數(shù)獨、額外區(qū)域數(shù)獨和奇偶數(shù)獨的填數(shù)規(guī)則，充分利用LINGO軟件在求解大規(guī)模規(guī)劃模型的功能，編寫求解數(shù)獨問題的程序，用數(shù)獨聯(lián)盟五段段位考試訓(xùn)練題及《競技數(shù)獨》中的練習(xí)題進(jìn)行實驗，驗證所編寫的程序運算速度快，結(jié)論準(zhǔn)確可靠。這種方法，一方面能夠快速、準(zhǔn)確地得到數(shù)獨問題的解，另一方面培養(yǎng)了學(xué)生的數(shù)學(xué)建模能力，使他們掌握LINGO軟件的使用技巧。我們認(rèn)為，用LINGO軟件編程還能求解不規(guī)則數(shù)獨、殺手?jǐn)?shù)獨、連體數(shù)獨等變形數(shù)獨問題，這將是下一步研究的問題。

[1]袁新生,邵大宏,郁時爍.LINGO和Excel在數(shù)學(xué)建模中的應(yīng)用[M].北京:科學(xué)出版社,2007.

[2]嚴(yán)德人.競技數(shù)獨[M].北京:中國言實出版社,2007.

[3]張煜東,王水花,霍元愷,等.一種基于稀疏優(yōu)化的數(shù)獨求解新方法[J].南京信息工程大學(xué)學(xué)報:自然科學(xué)版,2011(1): 23-27.

[4]程曦,肖華勇,吳林波.數(shù)獨求解的候選數(shù)優(yōu)化算法設(shè)計[J].科學(xué)技術(shù)與工程,2011(9):6409-6412.

[5]雷蕾,沈富可.關(guān)于數(shù)獨問題的算法的設(shè)計與實現(xiàn)[J].電腦知識與技術(shù),2007(2):481-482.

[6]王瓊,鄒晟.數(shù)獨問題的求解、評價與生成算法的研究[J].南京師范大學(xué)學(xué)報:工程技術(shù)版,2010(1):76-79.

[7]吳濤.基于排除法填充模型的數(shù)獨求解算法[J].西安航空學(xué)院學(xué)報,2014(5):11-80.

[8]胡英武.數(shù)獨問題的整數(shù)規(guī)劃模型[J].金華職業(yè)技術(shù)學(xué)院學(xué)報,2011(6):86-88.

[9]馬麗娜.對角線數(shù)獨的LINGO求解模型[J].電腦知識與技術(shù),2015(4):91-93.

[10]數(shù)獨聯(lián)盟.高手?jǐn)?shù)獨:數(shù)獨聯(lián)盟段位考試訓(xùn)練題集(五段)[M].北京:中國水利水電出版社,2012.

Mathematical Models of Sudoku and LINGO Solution Program

KE Chun-mei

(Xiamen Ocean Vocational College, Xiamen Fujian 361101,China)

Based on the standard Sudoku rules, the ternary 0-1 variables was introduced to build a 0-1 integer programming of standard Sudoku. The LINGO solution program was developed based on the model, and its accuracy was verified by a Sudoku puzzle. Then, the solution method of standard Sudoku was extended to window Sudoku, extra area Sudoku and odd-even Sudoku. The operation time and accuracy of the LINGO programs are validated by Sudoku puzzles in the Grade Five Exam of Sudoku League. The operation time were all less than 2 seconds, and the accuracy rate were 100%, these LINGO programs can be used to solve Sudoku problems with short operation time and highly reliable results.

LINGO software; standard Sudoku; 0-1 integer programming; deformation Sudoku

2016-08-15

柯春梅(1965- )，女，講師，碩士，從事數(shù)學(xué)建模與金融數(shù)學(xué)研究。

O141.4

A

2095-7602(2016)12-0008-06