基于數(shù)學建模的連體數(shù)獨的求解問題研究

柯春梅

(廈門海洋職業(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 提出問題

圖1所示的五連體數(shù)獨稱為武士數(shù)獨，是由五個數(shù)獨組成的，其中中間數(shù)獨和其他四個數(shù)獨都有一個共同的小九宮.我們按照符號假設、模型建立與模型求解等數(shù)學建模基本步驟來建立武士數(shù)獨的數(shù)學模型，編制相應的LINGO程序，并以圖1為例求解.然后將模型推廣，建立花型數(shù)獨的數(shù)學模型，編制相應的LINGO程序，并舉例求解.

2 符號假設

圖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個小九宮.

3 建立模型

連體數(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ù)學模型為：

4 模型的求解

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所示.

5 模型檢驗

武士數(shù)獨的數(shù)學模型和求解程序具有普遍適用性.對于不同的武士數(shù)獨，我們只要輸入相應的數(shù)據(jù)a1,a2,a3,a4,a5就可以得到它的解.利用百度搜索可以搜到很多武士數(shù)獨，這里選取文獻[9]中10個武士數(shù)獨進行驗證，可以得出正確的解，而且求解速度在1秒以內.

6 模型的推廣

圖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ù)獨的情形.

7 結語

數(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.