殺手?jǐn)?shù)獨(dú)的數(shù)學(xué)模型與LINGO求解程序

柯春梅

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

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

圖1 殺手?jǐn)?shù)獨(dú)

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

1.殺手?jǐn)?shù)獨(dú)的數(shù)學(xué)規(guī)劃模型的建立過程

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

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

引入三元0-1變量

目標(biāo)函數(shù)：

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

約束條件：

與決策變量的關(guān)系；

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

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

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

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

（6）xijk是0-1變量；

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

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

因此圖1所示殺手?jǐn)?shù)獨(dú)的數(shù)學(xué)模型為：

2.殺手?jǐn)?shù)獨(dú)的Lingo求解程序設(shè)計(jì)

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

即得到圖1所示殺手?jǐn)?shù)獨(dú)的解如圖2.

圖2 殺手?jǐn)?shù)獨(dú)的解

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

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

圖3 模擬試題1殺手?jǐn)?shù)獨(dú)及其解

圖4 模擬試題2殺手?jǐn)?shù)獨(dú)及其解

圖5 模擬試題3殺手?jǐn)?shù)獨(dú)及其解

4.結(jié)語

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