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

柯春梅

(廈門海洋職業技術學院基礎部，福建廈門 361101)

數獨就是在一個包含一定單元格的區域內，根據題目類型給定的規則，通過已知數字推理出剩余未知數字的一類數字謎題.數獨按照條件、規則，可分為標準數獨和變形數獨.連體數獨是一款變形數獨，它是指兩個或者多個具有若干共同格子的數獨連成一體，構成的另外一種數獨，其解題規則是：在不相交部分，求解要求與單個數獨的要求完全一樣，在相交部分，其數字既是第一個數獨的，也是第二個數獨的[1].連體數獨不是由可以單獨解開的數獨合并到一起的，合格的連體數獨是以整體出現時可以求解，而拆分開來是無法單獨求解的.連體數獨連的方式多種多樣，常見的有二連體數獨、三連體數獨、四連體數獨(僧侶數獨)、五連體數(武士數獨、花型數獨、異形五連體數獨)、六連體數獨、九連體數獨、十一連體數獨等[2-3].數獨問題可以看作優化問題，通過建立數學模型，并利用LINGO軟件進行求解，目前這種研究不多，胡英武[4]給出九階數獨的模型與求解程序，馬麗娜[5]給出對角線數獨的模型與求解程序，柯春梅[6-7]給出了標準數獨、對角線數獨、窗口數獨、額外區域數獨、奇偶數獨及殺手數獨的求解程序，對于連體數獨的建模與求解問題，目前尚未看到相關研究.這里基于數學建模研究五連體數獨的求解問題，這些思路與方法可以推廣到其他連體數獨的求解問題.

1 提出問題

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

2 符號假設

圖1 武士數獨

圖2 武士數獨的解

Bmt={(i,j)|3int[(i-1)/3]+int[(j-1)/3]+1=mt}，t=1,2,3,4,5；Bmt表示第t個數獨的第m個小九宮.

3 建立模型

連體數獨的求解問題可以轉化為數學規劃問題，數學規劃問題的三要素是決策變量、目標函數和約束條件.

決策變量：由于格子(i,j)處要么填入數字k，要么不填入數字k(k=1,2,…,9)，有且只有兩種狀態，因而引入三元0-1變量：

目標函數：由于數獨的可行解是唯一的，連體數獨的可行解也是唯一的，該可行解就是目標函數，所以連體數獨的目標函數為min=1.

約束條件：根據數獨的填數規則和連體數獨的概念，武士數獨的約束條件為：

(7)公共部分的數字滿足相交的兩個數獨的條件：

根據上述分析可知，武士數獨的數學模型為：

4 模型的求解

LINGO是求解優化問題的專業軟件包，它內置建模語言，提供幾十個內部函數，從而能以較少的語句，較直觀的方式描述大規模的優化模型，而且它的運算速度快，計算結果可靠[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;

運算后可得到武士數獨的解如圖2所示.

5 模型檢驗

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

6 模型的推廣

圖3所示的五連體數獨稱為花型數獨[3]，它是由圖5所示的5個數獨組成，從左到右的數獨分別是第1數獨、第2數獨、第3數獨、第4數獨、第5數獨.

圖3 花型數獨

圖4 花型數獨的解

圖5 組成花型數獨的5個數獨

按照前面的符號假設，將武士數獨模型的最后4行修改為：

相應地，將武士數獨求解程序的最后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;

運行后可得到該花型數獨的解如圖4所示.用文獻[3]中的練習題進行驗證，同樣可以在1秒內得到正確答案.

構成連體數獨的單個數獨可以是九階的，也可以是非九階的，還可以是變形數獨.連體數獨，可以兩個數獨有共同格子的連體，也可以是多個數獨有共同格子的連體，而且連體的方法多種多樣，但它們的解題規則是一樣的.上述建模和求解的思路與方法可以推廣到各種連體數獨的情形.

7 結語

數獨是一款益智數字游戲，它全面考驗做題者的觀察能力和推理能力，雖然玩法簡單，但數字排列方式卻千變萬化，是訓練頭腦的絕佳方式，引起許多民眾特別是青年學生的興趣，每年的中國數獨錦標賽都吸引眾多學生的參加.數獨的求解問題可以轉化為數學規劃問題，先建立數學模型，建模過程包括符號假設、模型建立、模型求解、模型推廣等，再用LINGO軟件編程求解.用數學建模的方法求解連體數獨具有可推廣性，數學模型和求解程序簡潔，運算時間短，結果準確.將基于數學建模的數獨求解問題用于數學建模的培訓，能引起學生的興趣，可以訓練建模的基本步驟，還能訓練LINGO軟件的應用，對提高培訓效果起到積極的作用.

[1]嚴德人.競技數獨[M].北京:中國言實出版社,2007.

[2]余俊雄,尤國峻.數獨揭秘[M].武漢:湖北少年兒童出版社,2011.

[3]蘆向明,藍天.非常數獨:一本書玩夠76種花式數獨[M].北京:化學工業出版社,2011.

[4]胡英武.數獨問題的整數規劃模型[J].金華職業技術學院學報,2011(6):86-88.

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

[6]柯春梅.數獨的數學模型與LINGO求解程序[J].長春師范大學學報,2016(12):8-13.

[7]柯春梅.殺手數獨的數學模型與LINGO求解程序[J].呼倫貝爾學院學報:漢文版,2016(6):85-88,91.

[8]袁新生,邵大宏,郁時爍.LINGO和Excel在數學建模中的應用[M].北京:科學出版社,2007.

[9]百度貼吧.一組武士數獨(數獨吧)[EB/OL].(2015-11-12)[2017-05-29].http://tieba.baidu.com/p/4173732197.