窗口數獨求解的線性規劃模型

程海礁

?

窗口數獨求解的線性規劃模型

程海礁

（湖南科技學院 理學院，湖南 永州 425199）

窗口數獨是在標準的數獨上多增加四個宮格，相對于標準數獨來說求解難度比較大，文章從窗口數獨的求解要求出發建立了線性規劃模型，該線性方程組的解與原窗口數獨的解完全相同。最后利用Matlab軟件實現算法，并應用該算法去驗證窗口數獨難題。

窗口數獨; 唯一解; 線性規劃

1　引　言

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

圖1.窗口數獨題目

2　建立線性規劃模型

對于一般的窗口數獨問題，我們建立線性規劃模型[4]。

建立如下約束：

（1）每個空格恰好填一個數字：

（2）每行每個數字恰好填一次：

（3）每列每個數字恰好填一次：

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

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

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

則根據窗口數獨的求解規則便得到了一個線性方程組：

3　應用實例的算法實現

對于圖1中的數獨題目，應用上述思想，Matlab算法流程如下:

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

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

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 %初始化候選數矩陣

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

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）每列每個數字恰好填一次，根據已知數按列排除候選數

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）每個九宮格恰好填一次，根據已知解按原九宮格排除候選數

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）新增的九宮格恰好填一次，根據已知解按新九宮格排除候選數

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）循環遍歷，排除不符合規則候選數，直到候選數矩陣每列只有一個非零值。求解結果如圖2：

圖2.窗口數獨答案

4　結　論

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

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

[2]劉延風,劉三陽.基于遺傳算法求解數獨難題[J].計算機科學,2010,(3):225-226.

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

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

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

[6]雷蕾,沈福可.關于數獨問題的算法的設計與實現[J].電腦知識與技術,2007,(2):481-482．

(責任編校：何俊華)

2016－03－11

湖南科技學院校級科研課題（項目編號16XKY066）。

程海礁（1987－），女，遼寧本溪人，助教，碩士，研究方向為概率統計。

O21

A

1673-2219（2016）10-0001-02