柯春梅

（廈門海洋職業(yè)技術學院基礎部 福建 廈門 361101 ）

殺手數(shù)獨是一種數(shù)學智力游戲，它結合了數(shù)獨和數(shù)和的玩法。出題者將數(shù)獨的81個格子用虛線分成若干個區(qū)域，每個區(qū)域由相鄰的若干個格子組成，并在每個區(qū)域的左上角給出這個區(qū)域的所有格子內(nèi)數(shù)字的總和，規(guī)定數(shù)獨參與者不僅要遵守數(shù)獨的要求，并且還要滿足各區(qū)域數(shù)字之和的要求來完成數(shù)獨題，就是在空格內(nèi)填上1～9的數(shù)字，使每個數(shù)字在每一行、每一列、每個標有粗線的宮內(nèi)只能出現(xiàn)一次，虛線框出的區(qū)域內(nèi)所有數(shù)字之和等于虛線框左上角標注的數(shù)字，并且同一虛線框內(nèi)的數(shù)字不能重復，這就是殺手數(shù)獨，也稱分組數(shù)字和數(shù)獨[1],[2]，圖1就是一題殺手數(shù)獨[2]。

圖1 殺手數(shù)獨

LINGO是求解優(yōu)化問題的專業(yè)軟件包，它內(nèi)置建模語言，提供幾十個內(nèi)部函數(shù)，從而能以較少的語句，較直觀的方式描述大規(guī)模的優(yōu)化模型，而且它的運算速度快，計算結果可靠[3],[4]。國內(nèi)許多學者對利用計算機進行快速求解數(shù)獨的算法進行深入研究與探索，這些算法多數(shù)以回溯法為基礎，結合各種預處理提高算法的執(zhí)行速度[5]-[9]，根據(jù)數(shù)獨的求解規(guī)則建立數(shù)學模型，并給予求解的研究不多[10],[11]，對于殺手數(shù)獨的建模與求解問題，目前尚未看到相關研究。

1.殺手數(shù)獨的數(shù)學規(guī)劃模型的建立過程

殺手數(shù)獨初盤沒有給定數(shù)，只給出虛線框內(nèi)數(shù)字和，而虛線框所框出的區(qū)域變化無常，建立數(shù)學模型必須根據(jù)具體題目來建立，下面根據(jù)圖1所示殺手數(shù)獨分析數(shù)學模型的建立過程。

為了方便起見，（i,j）（i,j=1，2，……，9）表示數(shù)獨盤面中處于第i行第j列的格子，(m=1,2,……,9)表示第 m宮，其中 int表示向下取整。aij表示數(shù)獨初盤格子(i,j)處所填的數(shù)，其中0表示該格子未填數(shù)，殺手數(shù)獨初盤沒有給定的數(shù)，所以初盤中81個格子都填0，yij(i,j=1,2,……,9)表示數(shù)獨完成后格子(i,j)處所填的數(shù)。

引入三元0-1變量

目標函數(shù)：

數(shù)獨完成后，數(shù)獨盤上每個格子都填上 1～9的一個數(shù)字，且滿足每個數(shù)字在每一行、每一列、每個宮內(nèi)不能重復，因此目標函數(shù)為

約束條件：

與決策變量的關系；

（2）每個格子（i,j)處恰好填數(shù)字 1～9中的一個數(shù)；

（3）每行1～9中的每個數(shù)只能填一次；

（4）每列1～9中的每個數(shù)只能填一次；

（5）每個宮1～9中的每個數(shù)只能填一次；

（6）xijk是0-1變量；

（7）虛線框出的區(qū)域數(shù)字之和等于虛線框左上角標注的數(shù)字，根據(jù)具體題目確定；

（8）虛線框內(nèi)的數(shù)字不能重復：如果虛線框區(qū)域內(nèi)的格子在同一行、同一列或者同一宮內(nèi)，則他們的數(shù)字已經(jīng)滿足沒有重復，如果虛線框區(qū)域內(nèi)的格子至少有兩個不在同一行、同一列或者同一宮內(nèi)，則應增加虛線框內(nèi)的數(shù)兩兩只差的乘積的絕對值大于零作為約束條件。

因此圖1所示殺手數(shù)獨的數(shù)學模型為：

2.殺手數(shù)獨的Lingo求解程序設計

根據(jù)上述殺手數(shù)獨的數(shù)學模型，利用 LINGO軟件的內(nèi)置函數(shù)@for、@sum、@floor及@abs編制求解程序，由于 LINGO軟件中“<”表示“小于等于”，“>”表示“大于等于”，因此要表示兩個數(shù)不相等，要用兩個數(shù)的差的絕對值大于一個很小的正數(shù)來表示。因此圖 1所示殺手數(shù)獨的Lingo求解程序如下：

即得到圖1所示殺手數(shù)獨的解如圖2.

圖2 殺手數(shù)獨的解

3.計算實驗

殺手數(shù)獨是一種變形數(shù)獨，對于每一題殺手數(shù)獨，目標函數(shù)都相同，約束條件中（1）～（6）是相同的，約束條件（7）和（8）則需要根據(jù)不同題目來編制。圖3、圖4、圖5所示的殺手數(shù)獨是數(shù)獨三段段位考試模擬試題，根據(jù)題目所給虛線框及其標注的數(shù)字修改LINGO求解程序，進行求解，運行后得到它的解，運算速度不足1秒，運算結果準確。

圖3 模擬試題1殺手數(shù)獨及其解

圖4 模擬試題2殺手數(shù)獨及其解

圖5 模擬試題3殺手數(shù)獨及其解

4.結語

殺手數(shù)獨作為一種數(shù)學智力游戲，既具有邏輯性、可推理性，又具有數(shù)字和的運算性，建立數(shù)學模型，利用 LINGO軟件求解大規(guī)模規(guī)劃模型的功能編制求解程序，可以快速準確地得到答案。本文以一題殺手數(shù)獨為例，建立對應的數(shù)學規(guī)劃模型，編制LINGO求解程序，快速準確得到答案，然后根據(jù)三道數(shù)獨三段段位考試模擬試題，修改部分約束條件，仍可快速準確得到答案，說明這種程序準確，同時具有可復制性。