柯春梅
(廈門海洋職業(yè)技術學院基礎部,福建廈門 361101)
數(shù)獨就是在一個包含一定單元格的區(qū)域內,根據(jù)題目類型給定的規(guī)則,通過已知數(shù)字推理出剩余未知數(shù)字的一類數(shù)字謎題.數(shù)獨按照條件、規(guī)則,可分為標準數(shù)獨和變形數(shù)獨.連體數(shù)獨是一款變形數(shù)獨,它是指兩個或者多個具有若干共同格子的數(shù)獨連成一體,構成的另外一種數(shù)獨,其解題規(guī)則是:在不相交部分,求解要求與單個數(shù)獨的要求完全一樣,在相交部分,其數(shù)字既是第一個數(shù)獨的,也是第二個數(shù)獨的[1].連體數(shù)獨不是由可以單獨解開的數(shù)獨合并到一起的,合格的連體數(shù)獨是以整體出現(xiàn)時可以求解,而拆分開來是無法單獨求解的.連體數(shù)獨連的方式多種多樣,常見的有二連體數(shù)獨、三連體數(shù)獨、四連體數(shù)獨(僧侶數(shù)獨)、五連體數(shù)(武士數(shù)獨、花型數(shù)獨、異形五連體數(shù)獨)、六連體數(shù)獨、九連體數(shù)獨、十一連體數(shù)獨等[2-3].數(shù)獨問題可以看作優(yōu)化問題,通過建立數(shù)學模型,并利用LINGO軟件進行求解,目前這種研究不多,胡英武[4]給出九階數(shù)獨的模型與求解程序,馬麗娜[5]給出對角線數(shù)獨的模型與求解程序,柯春梅[6-7]給出了標準數(shù)獨、對角線數(shù)獨、窗口數(shù)獨、額外區(qū)域數(shù)獨、奇偶數(shù)獨及殺手數(shù)獨的求解程序,對于連體數(shù)獨的建模與求解問題,目前尚未看到相關研究.這里基于數(shù)學建模研究五連體數(shù)獨的求解問題,這些思路與方法可以推廣到其他連體數(shù)獨的求解問題.
圖1所示的五連體數(shù)獨稱為武士數(shù)獨,是由五個數(shù)獨組成的,其中中間數(shù)獨和其他四個數(shù)獨都有一個共同的小九宮.我們按照符號假設、模型建立與模型求解等數(shù)學建模基本步驟來建立武士數(shù)獨的數(shù)學模型,編制相應的LINGO程序,并以圖1為例求解.然后將模型推廣,建立花型數(shù)獨的數(shù)學模型,編制相應的LINGO程序,并舉例求解.
圖1 武士數(shù)獨
圖2 武士數(shù)獨的解
Bmt={(i,j)|3int[(i-1)/3]+int[(j-1)/3]+1=mt},t=1,2,3,4,5;Bmt表示第t個數(shù)獨的第m個小九宮.
連體數(shù)獨的求解問題可以轉化為數(shù)學規(guī)劃問題,數(shù)學規(guī)劃問題的三要素是決策變量、目標函數(shù)和約束條件.
決策變量:由于格子(i,j)處要么填入數(shù)字k,要么不填入數(shù)字k(k=1,2,…,9),有且只有兩種狀態(tài),因而引入三元0-1變量:
目標函數(shù):由于數(shù)獨的可行解是唯一的,連體數(shù)獨的可行解也是唯一的,該可行解就是目標函數(shù),所以連體數(shù)獨的目標函數(shù)為min=1.
約束條件:根據(jù)數(shù)獨的填數(shù)規(guī)則和連體數(shù)獨的概念,武士數(shù)獨的約束條件為:
(7)公共部分的數(shù)字滿足相交的兩個數(shù)獨的條件:
根據(jù)上述分析可知,武士數(shù)獨的數(shù)學模型為:
LINGO是求解優(yōu)化問題的專業(yè)軟件包,它內置建模語言,提供幾十個內部函數(shù),從而能以較少的語句,較直觀的方式描述大規(guī)模的優(yōu)化模型,而且它的運算速度快,計算結果可靠[8].利用LINGO編程語言,對上述模型編制程序如下:
model:
sets:
number/1..9/;
line/1..9/;
col/1..9/;
gong/1..9/;
shudu(line,col):b1,b2,b3,b4,b5,a1,a2,a3,a4,a5;
link(line,col,number):x1,x2,x3,x4,x5;
endsets
data:
!鍵盤輸入;
a1=?;
a2=?;
a3=?;
a4=?;
a5=?;
enddata
@for(line(i):@for(col(j):b1(i,j)=@sum(number(k):k*x1(i,j,k))));
@for(line(i):@for(col(j):@sum(number(k):x1(i,j,k))=1));
@for(line(i):@for(number(k):@sum(col(j):x1(i,j,k))=1));
@for(col(j):@for(number(k):@sum(line(i):x1(i,j,k))=1));
@for(link(i,j,k):@bin(x1(i,j,k)));
@for(line(i):@for(col(j):b2(i,j)=@sum(number(k):k*x2(i,j,k))));
@for(line(i):@for(col(j):@sum(number(k):x2(i,j,k))=1));
@for(line(i):@for(number(k):@sum(col(j):x2(i,j,k))=1));
@for(col(j):@for(number(k):@sum(line(i):x2(i,j,k))=1));
@for(link(i,j,k):@bin(x2(i,j,k)));
@for(line(i):@for(col(j):b3(i,j)=@sum(number(k):k*x3(i,j,k))));
@for(line(i):@for(col(j):@sum(number(k):x3(i,j,k))=1));
@for(line(i):@for(number(k):@sum(col(j):x3(i,j,k))=1));
@for(col(j):@for(number(k):@sum(line(i):x3(i,j,k))=1));
@for(link(i,j,k):@bin(x3(i,j,k)));
@for(line(i):@for(col(j):b4(i,j)=@sum(number(k):k*x4(i,j,k))));
@for(line(i):@for(col(j):@sum(number(k):x4(i,j,k))=1));
@for(line(i):@for(number(k):@sum(col(j):x4(i,j,k))=1));
@for(col(j):@for(number(k):@sum(line(i):x4(i,j,k))=1));
@for(link(i,j,k):@bin(x4(i,j,k)));
@for(line(i):@for(col(j):b5(i,j)=@sum(number(k):k*x5(i,j,k))));
@for(line(i):@for(col(j):@sum(number(k):x5(i,j,k))=1));
@for(line(i):@for(number(k):@sum(col(j):x5(i,j,k))=1));
@for(col(j):@for(number(k):@sum(line(i):x5(i,j,k))=1));
@for(link(i,j,k):@bin(x5(i,j,k)));
End
鍵盤輸入
a1=0 1 6 0 7 0 0 9 0
8 0 2 5 0 9 6 0 1
0 0 0 0 0 4 0 0 0
0 5 0 0 0 0 0 0 0
2 0 0 4 0 3 0 0 7
0 0 0 0 0 0 0 2 0
0 0 0 1 0 0 0 0 0
5 0 9 2 0 7 1 0 3
0 8 0 0 9 0 5 4 0; a2=0 7 0 2 0 1 0 3 0
0 0 9 0 8 0 0 0 0
0 0 3 0 0 0 6 0 0
0 4 0 9 0 8 1 6 0
7 0 0 0 0 0 0 0 4
0 6 5 4 0 7 0 9 0
0 0 7 0 0 0 0 1 6
0 0 0 0 9 0 8 0 2
0 8 0 1 0 6 0 0 0; a3=0 0 4 0 0 0 9 0 7
3 6 0 0 0 0 0 1 5
8 0 0 7 0 5 0 0 0
0 4 0 0 8 0 0 5 0
5 0 0 0 0 0 0 0 6
0 1 0 0 7 0 0 8 0
0 9 0 3 0 8 0 0 1
6 0 1 0 0 0 0 9 8
0 0 0 0 0 0 5 0 0;
a4=5 0 0 8 0 0 0 0 0
0 7 0 4 0 3 5 0 9
0 0 0 0 6 0 0 8 0
0 4 0 0 0 0 0 3 0
0 3 8 7 0 4 6 5 0
0 9 0 0 0 0 0 7 0
0 0 3 0 8 0 0 0 0
0 8 0 1 0 7 0 9 0
9 0 0 0 0 5 0 0 2; a5=0 0 0 0 0 0 8 2 3
1 0 3 9 0 7 4 0 0
5 4 0 0 0 0 0 7 0
0 0 0 0 8 3 0 0 0
4 0 6 0 0 0 5 0 9
0 0 0 5 4 0 0 0 0
0 2 0 0 0 0 0 0 0
0 0 5 4 0 8 3 0 0
8 9 1 0 0 0 0 4 5;
運算后可得到武士數(shù)獨的解如圖2所示.
武士數(shù)獨的數(shù)學模型和求解程序具有普遍適用性.對于不同的武士數(shù)獨,我們只要輸入相應的數(shù)據(jù)a1,a2,a3,a4,a5就可以得到它的解.利用百度搜索可以搜到很多武士數(shù)獨,這里選取文獻[9]中10個武士數(shù)獨進行驗證,可以得出正確的解,而且求解速度在1秒以內.
圖3所示的五連體數(shù)獨稱為花型數(shù)獨[3],它是由圖5所示的5個數(shù)獨組成,從左到右的數(shù)獨分別是第1數(shù)獨、第2數(shù)獨、第3數(shù)獨、第4數(shù)獨、第5數(shù)獨.
圖3 花型數(shù)獨
圖4 花型數(shù)獨的解
圖5 組成花型數(shù)獨的5個數(shù)獨
按照前面的符號假設,將武士數(shù)獨模型的最后4行修改為:
相應地,將武士數(shù)獨求解程序的最后4行修改為:
鍵盤輸入
a1=1 9 4 0 0 0 0 0 0
0 0 0 3 1 5 0 0 0
0 0 0 0 0 0 2 8 1
0 0 0 0 0 0 0 0 0
0 0 1 4 0 0 0 0 0
0 0 0 0 7 6 0 1 0
0 0 8 0 0 0 0 9 0
0 0 5 0 0 0 1 0 0
0 1 0 0 0 0 7 0 0; a2=0 0 3 0 0 0 0 0 0
0 0 7 0 0 1 4 0 0
0 0 2 0 0 0 0 7 6
0 5 0 0 0 8 0 0 0
0 2 0 0 0 5 0 0 0
0 3 0 0 1 0 0 0 0
3 0 0 0 5 0 9 6 0
2 0 0 0 0 0 0 0 7
4 0 0 0 0 0 0 0 0; a3=0 0 0 0 0 0 0 0 0
0 0 1 4 0 0 0 0 0
0 0 0 0 7 6 0 1 0
0 0 8 0 0 0 0 9 0
0 0 5 0 0 0 1 0 0
0 1 0 0 0 0 7 0 0
0 5 0 9 6 0 0 0 0
0 0 0 0 0 7 2 0 0
0 0 0 0 0 0 0 0 0;
a4=0 0 0 0 0 0 0 0 2
4 0 0 0 0 0 0 0 8
0 7 6 0 1 0 0 0 9
0 0 0 0 9 0 0 2 0
0 0 0 1 0 0 0 5 0
0 0 0 7 0 0 0 9 0
9 6 0 0 0 0 2 0 0
0 0 7 2 0 0 9 0 0
0 0 0 0 0 0 3 0 0; a5=0 0 8 0 0 0 0 9 0
0 0 5 0 0 0 1 0 0
0 1 0 0 0 0 7 0 0
0 5 0 9 6 0 0 0 0
0 0 0 0 0 7 2 0 0
0 0 0 0 0 0 0 0 0
9 4 6 0 0 0 0 0 0
0 0 0 4 3 9 0 0 0
0 0 0 0 0 0 9 1 4;
運行后可得到該花型數(shù)獨的解如圖4所示.用文獻[3]中的練習題進行驗證,同樣可以在1秒內得到正確答案.
構成連體數(shù)獨的單個數(shù)獨可以是九階的,也可以是非九階的,還可以是變形數(shù)獨.連體數(shù)獨,可以兩個數(shù)獨有共同格子的連體,也可以是多個數(shù)獨有共同格子的連體,而且連體的方法多種多樣,但它們的解題規(guī)則是一樣的.上述建模和求解的思路與方法可以推廣到各種連體數(shù)獨的情形.
數(shù)獨是一款益智數(shù)字游戲,它全面考驗做題者的觀察能力和推理能力,雖然玩法簡單,但數(shù)字排列方式卻千變萬化,是訓練頭腦的絕佳方式,引起許多民眾特別是青年學生的興趣,每年的中國數(shù)獨錦標賽都吸引眾多學生的參加.數(shù)獨的求解問題可以轉化為數(shù)學規(guī)劃問題,先建立數(shù)學模型,建模過程包括符號假設、模型建立、模型求解、模型推廣等,再用LINGO軟件編程求解.用數(shù)學建模的方法求解連體數(shù)獨具有可推廣性,數(shù)學模型和求解程序簡潔,運算時間短,結果準確.將基于數(shù)學建模的數(shù)獨求解問題用于數(shù)學建模的培訓,能引起學生的興趣,可以訓練建模的基本步驟,還能訓練LINGO軟件的應用,對提高培訓效果起到積極的作用.
[1]嚴德人.競技數(shù)獨[M].北京:中國言實出版社,2007.
[2]余俊雄,尤國峻.數(shù)獨揭秘[M].武漢:湖北少年兒童出版社,2011.
[3]蘆向明,藍天.非常數(shù)獨:一本書玩夠76種花式數(shù)獨[M].北京:化學工業(yè)出版社,2011.
[4]胡英武.數(shù)獨問題的整數(shù)規(guī)劃模型[J].金華職業(yè)技術學院學報,2011(6):86-88.
[5]馬麗娜.對角線數(shù)獨的LINGO求解模型[J].電腦知識與技術,2015(4):91-93.
[6]柯春梅.數(shù)獨的數(shù)學模型與LINGO求解程序[J].長春師范大學學報,2016(12):8-13.
[7]柯春梅.殺手數(shù)獨的數(shù)學模型與LINGO求解程序[J].呼倫貝爾學院學報:漢文版,2016(6):85-88,91.
[8]袁新生,邵大宏,郁時爍.LINGO和Excel在數(shù)學建模中的應用[M].北京:科學出版社,2007.
[9]百度貼吧.一組武士數(shù)獨(數(shù)獨吧)[EB/OL].(2015-11-12)[2017-05-29].http://tieba.baidu.com/p/4173732197.