程海礁

?

窗口數(shù)獨(dú)求解的線性規(guī)劃模型

程海礁

（湖南科技學(xué)院 理學(xué)院，湖南 永州 425199）

窗口數(shù)獨(dú)是在標(biāo)準(zhǔn)的數(shù)獨(dú)上多增加四個宮格，相對于標(biāo)準(zhǔn)數(shù)獨(dú)來說求解難度比較大，文章從窗口數(shù)獨(dú)的求解要求出發(fā)建立了線性規(guī)劃模型，該線性方程組的解與原窗口數(shù)獨(dú)的解完全相同。最后利用Matlab軟件實(shí)現(xiàn)算法，并應(yīng)用該算法去驗(yàn)證窗口數(shù)獨(dú)難題。

窗口數(shù)獨(dú); 唯一解; 線性規(guī)劃

1　引　言

當(dāng)大家還在鉆研數(shù)獨(dú)究竟填寫1至9這幾個數(shù)字的竅門時，另一個相類的游戲于最近迅速火爆，這就是窗口數(shù)獨(dú)。窗口數(shù)獨(dú)在英美等地人氣急升，窗口數(shù)獨(dú)相比九宮數(shù)獨(dú)更難玩。窗口數(shù)獨(dú)（如圖1）的規(guī)則十分簡單，首先就是在原有的標(biāo)準(zhǔn)的九宮格里面填數(shù)字，每個方格中填入合適的數(shù)字以使得每行每列以及每個九宮格都要包含從的數(shù)字且互不相同，新增加的四個宮格中也要包含1-9的數(shù)字且不能重復(fù)。窗口數(shù)獨(dú)與標(biāo)準(zhǔn)的九宮數(shù)獨(dú)玩法相近但趣味更豐富、挑戰(zhàn)性更大?，F(xiàn)有很多數(shù)獨(dú)網(wǎng)站，它里面詳細(xì)的說明了數(shù)獨(dú)的游戲規(guī)則和解數(shù)獨(dú)常用的技巧，還有在線數(shù)獨(dú)練習(xí)、數(shù)獨(dú)論壇，并且可以從該網(wǎng)站上下載數(shù)獨(dú)游戲軟件。還有很多利用人工智能求解數(shù)獨(dú)的方法，例如，枚舉算法[1]，遺傳算法[2]，粒子群算法[3]等。

圖1.窗口數(shù)獨(dú)題目

2　建立線性規(guī)劃模型

對于一般的窗口數(shù)獨(dú)問題，我們建立線性規(guī)劃模型[4]。

建立如下約束：

（1）每個空格恰好填一個數(shù)字：

（2）每行每個數(shù)字恰好填一次：

（3）每列每個數(shù)字恰好填一次：

（4）每個九宮格每個數(shù)字恰好填一次：

（5）新增加的四個九宮每個數(shù)字恰好填一次：

（6）要求每個變量為0-1變量，則：

則根據(jù)窗口數(shù)獨(dú)的求解規(guī)則便得到了一個線性方程組：

3　應(yīng)用實(shí)例的算法實(shí)現(xiàn)

對于圖1中的數(shù)獨(dú)題目，應(yīng)用上述思想，Matlab算法流程如下:

（1）建立候選數(shù)矩陣H與結(jié)果矩陣S，候選數(shù)矩陣H維度為H:81*9，每個空格初始包含9個候選數(shù)，結(jié)果矩陣維度為S:9*9.

（2）每個空格恰好填一個數(shù)字，根據(jù)已知解過濾未知空格的解空間

for i=1:size(S,1), j=1:size(S,2)

if S(i,j)~=0

k=i*10+j;

for m=1:9

H(k,m)=0;

end

H(k,j)=S(i,j);

end

end %初始化候選數(shù)矩陣

（3）每行每個數(shù)字恰好填一次，根據(jù)已知數(shù)按行排除候選數(shù)

for i=1:size(S,1), j=1:size(S,2)

if S(i,j)~=0

for j1=1:9

k1=S(i,j);

if j1~=j

H(i*10+j1,k1)=0

end

end

end

end

（4）每列每個數(shù)字恰好填一次，根據(jù)已知數(shù)按列排除候選數(shù)

for i=1:size(S,1), j=1,size(S,2)

if S(i,j)~=0

k3=S(i,j);

for i1=1:9

if i1~=i

H(i1*10+j,k3)=0;

end

end

end

end

（5）每個九宮格恰好填一次，根據(jù)已知解按原九宮格排除候選數(shù)

for i=size(S,1),j=1:size(S,2)

if S(i,j)~=0

if i<=3; j<=3

k3=S(i,j);

for k4=1:3, k5=1:3

if k4~=i,k5~=j

H(k4*10+k5,k3)=0;

end

end

end

... %同其他九宮格

end

end

（6）新增的九宮格恰好填一次，根據(jù)已知解按新九宮格排除候選數(shù)

for i=size(S,1),j=1:size(S,2)

if S(i,j)~=0

K3=S(i,j);

if 2=

for k6=2:4, k7=2:4

If k5~=i,k6~=j

H(K5*10+k6,k3)=0;

end

end

end

...%同其他新增九宮格

end

end

（7）循環(huán)遍歷，排除不符合規(guī)則候選數(shù)，直到候選數(shù)矩陣每列只有一個非零值。求解結(jié)果如圖2：

圖2.窗口數(shù)獨(dú)答案

4　結(jié)　論

文章提出了由窗口數(shù)獨(dú)出發(fā)建立了一個線性方程組的問題，把窗口數(shù)獨(dú)的求解轉(zhuǎn)化為完全等價于求解該線性方程組。當(dāng)窗口數(shù)獨(dú)有唯一解時，此方程組也有唯一解。用此算法可以求解大量的窗口數(shù)獨(dú)難題。可以將此算法推廣到求解其他變形數(shù)獨(dú)，同時可以考慮改進(jìn)的算法使得求解速度變快，即是我們下一步需要研究的問題。

[1]肖華勇,田錚,馬雷.數(shù)獨(dú)基于規(guī)則的逐步枚舉算法設(shè)計[J].計算機(jī)工程與設(shè)計,2010,(5):1035-1037.

[2]劉延風(fēng),劉三陽.基于遺傳算法求解數(shù)獨(dú)難題[J].計算機(jī)科學(xué),2010,(3):225-226.

[3]任小波,楊忠秀.粒子群優(yōu)化算法的改進(jìn)[J].計算機(jī)工程, 2010,(7): 205-207.

[4]肖華勇,程海礁,王月興.九宮數(shù)獨(dú)的方程求解算法研究[J].計算機(jī)應(yīng)用,2012,(10):387-401.

[5]劉曉寶.數(shù)獨(dú)游戲的解題算法[J].電腦編程技巧與維護(hù), 2007,(5):64-67.

[6]雷蕾,沈?？?關(guān)于數(shù)獨(dú)問題的算法的設(shè)計與實(shí)現(xiàn)[J].電腦知識與技術(shù),2007,(2):481-482．

(責(zé)任編校：何俊華)

2016－03－11

湖南科技學(xué)院校級科研課題（項(xiàng)目編號16XKY066）。

程海礁（1987－），女，遼寧本溪人，助教，碩士，研究方向?yàn)楦怕式y(tǒng)計。

O21

A

1673-2219（2016）10-0001-02