柯春梅

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

?

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

柯春梅

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

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

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

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

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

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

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

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

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

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

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

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

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

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ù)獨(dú)的求解

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

圖1所示標(biāo)準(zhǔn)數(shù)獨(dú)是文獻(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;

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

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

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

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

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

圖3 窗口數(shù)獨(dú)

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

在標(biāo)準(zhǔn)數(shù)獨(dú)的LINGO求解程序中增加如下4個(gè)語句，就可以得到窗口數(shù)獨(dú)的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ù)獨(dú)求解程序中，通過鍵盤輸入數(shù)獨(dú)初盤，運(yùn)行后可以得到窗口數(shù)獨(dú)的解。例如通過鍵盤輸入數(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;

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

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

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

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

圖6 奇偶數(shù)獨(dú)

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

圖5示額外區(qū)域數(shù)獨(dú)的LINGO求解程序?yàn)椋?/p>

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

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

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

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

圖6所示奇偶數(shù)獨(dú)的LINGO求解程序?yàn)椋?/p>

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

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

3 計(jì)算實(shí)驗(yàn)

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

4 結(jié)語

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

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

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

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

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

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

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

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

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

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

[10]數(shù)獨(dú)聯(lián)盟.高手?jǐn)?shù)獨(dú):數(shù)獨(dú)聯(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