基于區(qū)域序列枚舉法的蜂巢數(shù)獨求解算法研究

肖華勇，楊菲菲，黃奔茹

西北工業(yè)大學(xué) 理學(xué)院 數(shù)學(xué)系，西安 710129

基于區(qū)域序列枚舉法的蜂巢數(shù)獨求解算法研究

肖華勇，楊菲菲，黃奔茹

西北工業(yè)大學(xué) 理學(xué)院 數(shù)學(xué)系，西安 710129

1 引言

數(shù)獨（Sudoku）是一種基于邏輯推理的數(shù)學(xué)謎題，是18世紀(jì)末由瑞士數(shù)學(xué)家歐拉發(fā)明的，后在美國發(fā)展，并在日本得以發(fā)揚光大。數(shù)獨的玩法邏輯上非常簡單，但數(shù)字排列方式千變?nèi)f化。謎題中會預(yù)先填入若干數(shù)字，其他宮格為空白，玩家需要根據(jù)謎題中的數(shù)字分布狀況，邏輯推敲出剩余的空格所需數(shù)字。隨著對數(shù)獨研究的深入，出現(xiàn)了越來越多的變形，數(shù)獨形狀變化（蜂巢數(shù)獨、環(huán)狀數(shù)獨等）和引入和式計算（Killer數(shù)獨、Kakuro數(shù)獨等）等[1]。

蜂巢數(shù)獨是標(biāo)準(zhǔn)數(shù)獨形狀發(fā)生變化的數(shù)獨，其外形類似蜂巢，所以稱為蜂巢數(shù)獨。如圖1所示，蜂巢數(shù)獨有行，沒有列和九宮格，但有正斜線、反斜線。它要求每行、正斜線、反斜線所填數(shù)字不能重復(fù)，且每行、正斜線、反斜線所填數(shù)字序列是連續(xù)數(shù)列（例如 1～6，3～8，4～9，…）。除了中間的行、正斜線、反斜線所填數(shù)字是1～9，其他行、正斜線、反斜線所填數(shù)字不一定是從1開始，也就是說其他行、正斜線、反斜線所填數(shù)字不一定包括1～9這9個數(shù)字。由于蜂巢數(shù)獨并沒有九宮，最特殊的是蜂巢連線（行、正斜線、反斜線）數(shù)字序并不固定，所以不能完全沿用傳統(tǒng)數(shù)獨解題技法。

國內(nèi)外學(xué)者針對數(shù)獨求解方面展開了大量研究，他們把數(shù)獨問題轉(zhuǎn)化成不同的數(shù)學(xué)模型。A.C.Bartlett等[2-3]針對對角線數(shù)獨、金字塔數(shù)獨等特殊形式的數(shù)獨建立了0-1整數(shù)規(guī)劃模型，并運用Matlab中的優(yōu)化函數(shù)求得模型的解。肖華勇等[4]提出了用數(shù)獨規(guī)則的逐步枚舉算法求解標(biāo)準(zhǔn)數(shù)獨，該方法比回溯法具有更快的速度。Christian Posthoff等[5]用建立邏輯方程的形式求解數(shù)獨謎題，但是這種算法的效率比較低。劉延風(fēng)等[6]用遺傳算法求解標(biāo)準(zhǔn)數(shù)獨。Sheehan Khan等[7]用概率圖解方法求解數(shù)獨，但是其算法的適應(yīng)性、通用性不高。J. Goldberger[8]對信息傳遞算法進行了改進，使之適用于一般的數(shù)獨問題。Lynce等[9]用兩種SAT推理方法解決了數(shù)獨謎題。J.A.Bondy等[10]將數(shù)獨問題轉(zhuǎn)化為著色問題。肖華勇等[11]研究了標(biāo)準(zhǔn)數(shù)獨的方程求解算法問題。R.Lewis[12]提出利用現(xiàn)代優(yōu)化算法求解標(biāo)準(zhǔn)數(shù)獨問題，并提出了一種基于模擬退火的求解方法。但是以上文獻多針對標(biāo)準(zhǔn)數(shù)獨展開研究，而對于蜂巢數(shù)獨等變形數(shù)獨的研究較少。

圖1 初級蜂巢數(shù)獨謎題

目前國內(nèi)外學(xué)者對于蜂巢數(shù)獨的研究多局限于行列唯一法、基本摒除法、三角形摒除法、余數(shù)法、數(shù)偶法、砂漏法等直觀法求解[13]，與標(biāo)準(zhǔn)數(shù)獨的直觀法求解[14]有很大的不同。但是對計算機求解蜂巢數(shù)獨的算法的研究尚屬起步階段。

蜂巢數(shù)獨同標(biāo)準(zhǔn)數(shù)獨最大的區(qū)別在于形狀類似蜂巢，完全拋棄了九宮格，對序列有連續(xù)性的要求。因此在求解算法上，兩者相似但有很大的不同。本文利用線性規(guī)劃方程組建立數(shù)學(xué)模型，研究其解的性質(zhì)，然后提出算法，并用實例說明求解的有效性。

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

2.1 單元格的表示

蜂巢數(shù)獨的行對應(yīng)標(biāo)準(zhǔn)數(shù)獨的行，正斜線表示數(shù)獨從左到右從右上到左下的9條斜線，反斜線表示數(shù)獨從左到右從左上到右下的9條斜線。

每個單元格用坐標(biāo)(i，j)表示。i代表行號，從上到下 i=1，2，…，9 ；j代表列號，從左到右為 1，2，3，… 。其中第1行 j=1，2，…，5，第2行 j=1，2，…，6，依次類推，第9行 j=1，2，…，5。

用 Ai(i=1，2，…，9)表示每行存放的單元格的集合 。其 中 A1={(1，1)，(1，2)，(1，3)，(1，4)，(1，5)}，A2={(2，1)，(2，2)，(2，3)，(2，4)，(2，5)，(2，6)}，以此類推 A9={(9，1)，(9，2)，(9，3)，(9，4)，(9，5)}。

用Bi(i=1，2，…，9)表示每條正斜線存放的單元格的集合，每條正斜線上的單元格按從上到下排列。

其 中 B1={(1，1)，(2，1)，(3，1)，(4，1)，(5，1)}，B2={(1，2)，(2，2)，(3，2)，(4，2)，(5，2)，(6，1)} 以此類推 B9={(5，9)，(6，8)，(7，7)，(8，6)，(9，5)}。

用Ci(i=1，2，…，9)表示每條反斜線存放的單元格的集合，每條反斜線上的單元格按從上到下排列。

其 中 C1={(5，1)，(6，1)，(7，1)，(8，1)，(9，1)}，C2={(4，1)，(5，2)，(6，2)，(7，2)，(8，2)，(9，2)}，以此類推 C9={(1，5)，(2，6)，(3，7)，(4，8)，(5，9)}。

每個單元格有其所在的行號，正斜線號和反斜線號。每個單元格用一個三維向量(u，v，w)表示。如單元格 (1，1)的三維向量為 (1，1，5)，它表示單元格 (1，1)是第1行，第1條正斜線和第5條反斜線相交的單元格。

2.2 區(qū)候選數(shù)的確定

由于除了中間的行、正斜線、反斜線所填數(shù)字是1～9，其他行、正斜線、反斜線所填數(shù)字不一定包括1～9這9個數(shù)字。所以它不能像標(biāo)準(zhǔn)數(shù)獨那樣讓空單元格的初始候選數(shù)取1～9這9個數(shù)字，它要按各行所含有的單元格數(shù)和已填數(shù)字來確定初始候選數(shù)。

為方便起見，把某行、某正斜線、某反斜線都稱為一個區(qū)。設(shè)某區(qū)有L個格子，則該區(qū)只允許L個連續(xù)數(shù)字。若該區(qū)所填數(shù)字單元格大于1個時，取所填數(shù)字中最小數(shù)字為a，最大數(shù)字為b；若該區(qū)所填數(shù)字單元格只有一個時，a取該單元格的值，且b=a；則該區(qū)候選數(shù)范圍為 [m，M]，其中 m=max{1，b-L+1}，M=min{9，a+L-1}。當(dāng)該區(qū)一個數(shù)字也沒有填，取m=1，M=9。由于該區(qū)所填數(shù)字是L個連續(xù)數(shù)字，這連續(xù)數(shù)字序列可能為 [m，m+L-1]，或 [m+1，m+L]，…，或 [M-L+1，M]，則該區(qū)必然出現(xiàn)的候選數(shù)為這些連續(xù)數(shù)字序列的交集[M+(1-L)，m+(1-L)]。各區(qū)必然出現(xiàn)的候選數(shù)用L(At)，L(Bt)，L(Ct)表示，其中 t=1，2，…，9 。

如圖1，第一行 a=6，b=7，L=5，則第一行候選數(shù)范圍為 [3，9]，5 個連續(xù)數(shù)字序列可能為 [3，7]，或 [4，8]，或[5，9]，第一行必然出現(xiàn)的候選數(shù)為{5，6，7}，即 L(A1)= {5，6，7}。

2.3 單元格候選數(shù)的確定

若某個單元格所在行、正斜線、反斜線得到的候選數(shù)范圍為 [m1，M1]，[m2，M2]，[m3，M3]，則該單元格的初始候選數(shù)為[d，u]，其中 d=max{m1，m2，m3}，u=min{M1，M2，M3}。

如圖1，單元格 (1，1)的三維向量為 (1，1，5)，它所在第一行中 a=6，b=7，L=5，則第一行候選數(shù)范圍為[3，9]；它所在第一條正斜線中 a=3，b=6，L=5，則第一條正斜線候選數(shù)范圍為[2，7]；它所在第五條反斜線中a=2，b=8，L=9，則第五條反斜線候選數(shù)范圍為 [1，9]；那么單元格 (1，1)的初始候選數(shù)為3，4，5，6，7。

2.4 建立決策變量

為表達方便，設(shè)所有解未確定的變量都取xijk=-1，表示數(shù)字k為格子(i，j)的候選數(shù)。

3 線性規(guī)劃方程組的性質(zhì)

3.1 候選數(shù)刪除性質(zhì)

性質(zhì)3.1.1若 xijk=1，則 xijl=0，l≠k 。當(dāng)格子 (i，j)的數(shù)字確定時，利用該性質(zhì)可刪除該格子上的其余候選數(shù)。

性質(zhì) 3.1.2若 xijk=1，則 xilk=0，(i，j)∈ At，(i，l)∈ At，l≠j，t=1，2，…，9 。當(dāng)格子 (i，j)的數(shù)字確定為 k 時，利用該性質(zhì)可刪除該格子所在第t行區(qū)其他格子上的候選數(shù)k。

性質(zhì) 3.1.3若 xijk=1，則 xmnk=0，(i，j)∈ Bt，(m，n)∈Bt，(i，j)≠(m，n)，t=1，2，…，9 。當(dāng)格子 (i，j)的數(shù)字確定為k時，利用該性質(zhì)可刪除該格子所在第t正斜線區(qū)其他格子上的候選數(shù)k。

性質(zhì) 3.1.4若 xijk=1，則 xmnk=0，(i，j)∈ Ct，(m，n)∈Ct，(i，j)≠(m，n)，t=1，2，…，9 。當(dāng)格子 (i，j)的數(shù)字確定為k時，利用該性質(zhì)可刪除該格子所在第t反斜線區(qū)其他格子上的候選數(shù)k。

3.2 確定性性質(zhì)

為表示方便，建立函數(shù)：

性質(zhì)3.2.2若 xijk=-1，k∈[M+1-L，m-1+L]對任意的 (m，n)∈ At，(i，j)∈ At，(i，j)≠(m，n)，都有 xmnk≠ -1，則必有xijk=1。該性質(zhì)表示當(dāng)該格子在第t行區(qū)存在必定出現(xiàn)的數(shù)字，并且第t行區(qū)的其他格子未存在時，該格子所填數(shù)字必為候選數(shù)k。

性質(zhì)3.2.3若 xijk=-1，k∈[M+1-L，m-1+L]對任意的 (m，n)∈Bt，(i，j)∈Bt，(i，j)≠(m，n)，都有 xmnk≠-1，則必有xijk=1。該性質(zhì)表示當(dāng)該格子在第t正斜線區(qū)存在必定出現(xiàn)的數(shù)字，并且第t正斜線區(qū)的其他格子未存在時，該格子所填數(shù)字必為候選數(shù)k。

性質(zhì)3.2.4若 xijk=-1，k∈[M+1-L，m-1+L]對任意的 (m，n)∈ Ct，(i，j)∈ Ct，(i，j)≠(m，n)，都有 xmnk≠ -1，則必有xijk=1。該性質(zhì)表示當(dāng)該格子在第t反斜線區(qū)存在必定出現(xiàn)的數(shù)字，并且第t反斜線區(qū)的其他格子未存在時，該格子所填數(shù)字必為候選數(shù)k。

3.3 矛盾性質(zhì)

性質(zhì)3.3.1若對某固定格子(i，j)，對任意數(shù)字k，都有 xijk=0或1。若則導(dǎo)致該數(shù)獨矛盾。該性質(zhì)表明任何一個格子所填的數(shù)只能有1個。

性質(zhì)3.3.2若對某固定區(qū)t及數(shù)字k，對任意格子(i，j)∈At都有xijk=0 或 1。若2，…，9)，則導(dǎo)致該數(shù)獨矛盾。該性質(zhì)表明任何一個數(shù)在任何一個行區(qū)只能填1次。

性質(zhì)3.3.3若對某固定區(qū)t及數(shù)字k，對任意格子(i，j)∈Bt，都有xijk=0 或 1。若2，…，9)，則導(dǎo)致該數(shù)獨矛盾。該性質(zhì)表明任何一個數(shù)在任何一個正斜線區(qū)只能填1次。

性質(zhì)3.3.4若對某固定區(qū)t及數(shù)字k，對任意格子(i，j)∈Ct，都有xijk=0 或 1。若2，…，9)，則導(dǎo)致該數(shù)獨矛盾。該性質(zhì)表明任何一個數(shù)在任何一個反斜線區(qū)只能填1次。

3.4 不變性

性質(zhì) 3.4.1對某固定格子 (i，j)，若 xijk=-1，k∈{m，m+1，…，M}，即格子 (i，j)候選數(shù)為 m，m+1，…，M 。對所有候選數(shù)k，當(dāng) xijk=1時，某個格子(p，q)都不能填r，則xpqr=0。對某個候選數(shù)k，當(dāng)xijk=1時導(dǎo)致數(shù)獨矛盾，則必有xijk=0。

性質(zhì) 3.4.2對某 r(r=2，3，4，…)個固定格子 (i1，j1)，(i2，j2)，…，(ir，jr)，若 xi1j1k1=-1，k1∈{m1，m1+1，…，M1}，…，xirjrkr=-1，kr∈{mr，mr+1，…，Mr} 。即格子 (i1，j1)的候選 數(shù)為 m1，m1+1，…，M1，格子 (ir，jr) 的候選數(shù)為 mr，mr+1，…，Mr。當(dāng)對r個格子的多有候選數(shù)來說，當(dāng)xi1j1k1=-1，…，xirjrkr=-1時，某個格子 (i，j)都不能填 r，則xijr=0。

4 算法應(yīng)用及實例計算

綜合前面由線性規(guī)劃方程組得到的四類性質(zhì)，本文提出求解該方程組的算法。

初始化：將數(shù)獨謎題存放在數(shù)組T[9][9]中，若格子(i，j)為空格，則令 T[i][j]=0 ；若格子 (i，j)已填入數(shù)字k，則令T[i][j]=k?；诜涑矓?shù)獨獨特的形狀，為了保證數(shù)組的完整性，其他未有格子的部分填-1。將數(shù)獨格子的候選數(shù)存放在數(shù)組x[9][9][9]中，同樣地，若格子(i，j)為空格，則令 x[i][j][k]=-1，k=1，2，…，9 ；若格子(i，j)已填入數(shù)字 k，則令 x[i][j][k]=1，x[i][j][l]=0(l≠k)。

步驟1根據(jù)2.3節(jié)的方法確定每個格子的候選數(shù)，然后根據(jù)3.1節(jié)性質(zhì)進行候選數(shù)的刪除。

步驟2根據(jù)3.2節(jié)性質(zhì)確定性對數(shù)獨進行填寫，若完整則程序結(jié)束，否則進入下一步。

步驟3對格子進行單區(qū)枚舉，刪除每個區(qū)中各格子的候選數(shù)。對任意一個區(qū)進行滿足連續(xù)序列的枚舉。將引起矛盾的候選數(shù)組合刪除，記錄沒有引起矛盾的候選數(shù)組合及由前面推理得到的新的候選數(shù)表，將得到的所有候選數(shù)表求并，從而得到各空格新的候選數(shù)集。實現(xiàn)刪除候選數(shù)的目標(biāo)。

步驟4利用每個區(qū)各格子新的候選數(shù)集，刪除其他相關(guān)格子中的候選數(shù)。

步驟5若數(shù)獨未填寫完整，轉(zhuǎn)入步驟3，若填寫完整，程序結(jié)束，輸出結(jié)果。

步驟6對格子進行兩區(qū)枚舉，刪除兩個區(qū)中各格子的候選數(shù)。對任意兩個區(qū)進行滿足連續(xù)序列的枚舉，然后進行同步驟3相同的處理。

步驟7若數(shù)獨未填寫完整，轉(zhuǎn)入步驟4，若填寫完整，程序結(jié)束，輸出結(jié)果。

對圖1利用候選數(shù)刪除和確定操作之后，空格減少了6個，如圖2所示。再進行一次單區(qū)枚舉后，數(shù)獨已經(jīng)完成，如圖3所示。

圖2 確定性操作結(jié)果

圖3 單區(qū)枚舉結(jié)果

再如，對圖4所示的中級謎題，進行文獻[11，15]中的空格枚舉算法同本文提出的區(qū)域序列枚舉法對比實驗。結(jié)果顯示，空格枚舉算法中，當(dāng)枚舉空格數(shù)增大到4的時候，還是無法求解出此謎題。然而當(dāng)采用本文提出的區(qū)域序列枚舉算法時，謎題結(jié)果如圖5所示。進行確定及空格枚舉操作后，空格數(shù)同樣也并未減少，選取第9行區(qū)進行枚舉，符合的連續(xù)序列有：34567和45678，將這兩組序列進行已知數(shù)4和7的排列組合，符合它的序列有12種，如：37546，37645等等。經(jīng)過單區(qū)序列枚舉得到結(jié)果圖5所示。

圖4 中級蜂巢數(shù)獨謎題

圖5 中級蜂巢區(qū)序列枚舉結(jié)果

經(jīng)過同文獻[11]中提出的算法進行對比實驗，得出少量的初級蜂巢數(shù)獨謎題只需空格枚舉就可以完成，對于中級甚至高級謎題，單空格枚舉和多空格枚舉失效，但是采用序列的區(qū)域枚舉就可以完成。這就體現(xiàn)出了蜂巢數(shù)獨其獨特的規(guī)則，即序列的連續(xù)性。這是它和標(biāo)準(zhǔn)數(shù)獨在算法上面的不同點。

5 結(jié)論

本文提出的對蜂巢數(shù)獨問題的方程組求解算法，利用了數(shù)獨問題對應(yīng)的方程的性質(zhì)進行候選數(shù)的刪除和更新，實現(xiàn)了由空格枚舉[11，15]向序列枚舉的轉(zhuǎn)變。對絕大多數(shù)的數(shù)獨問題，用很少格子的枚舉就能實現(xiàn)求解，而且計算時間都在毫秒級。但是這種空格枚舉的方法只能針對初級及極少數(shù)中級的蜂巢數(shù)獨謎題，當(dāng)空格數(shù)少于8個甚至更少的時候，這種空格枚舉方法的作用就很小了，于是區(qū)序列枚舉算法就起到了至關(guān)重要的作用。但是本文提出的算法即使再使用多區(qū)序列枚舉后，高級蜂巢數(shù)獨謎題的實現(xiàn)效率依然很低，同時當(dāng)蜂巢數(shù)獨需要經(jīng)過同時枚舉幾個區(qū)才能獲得時速度比較慢，可以考慮改進的方法。這將是下一步將要做的工作。

[1]Garns H.Number place[J].Dell Pencil Puzzles&Word Games，1979，16（5）.

[2]Bartlett A，Chartier T P，Langville A N，et al.An integer programming modelforthesudoku problem[EB/OL].（2006-03-10）.http：//www.cofc.edu/langvillea/Sudoku/sudoku2.pdf.

[3]Simons F.Solving a sudoku puzzle with mathematica[J]. Mathematica in Education and Research，2005，10（4）：1-24.

[4]肖華勇，田錚，馬雷.數(shù)獨基于規(guī)則的逐步枚舉算法設(shè)計[J].計算機工程與設(shè)計，2010，31（5）：1035-1037.

[5]Posthoff C，Steinbach B.Sudoku solutions using logic equations[Z].2008.

[6]劉延風(fēng)，劉三陽.基于遺傳算法求解數(shù)獨難題[J].計算機科學(xué)，2010（3）：225-226.

[7]Khan S，Jabbar S，Jabbari S，et al.Solving sudoku using probabilistic graphical models[Z].2009.

[8]Goldberger J.Solving sudoku using combined message passing algorithms[Z].[S.l.]：School of Engineering，Bar-llan University，2007.

[9]Lynee I，Ouaknin J.Sudoku as a SAT problem[C]//Proc of the 9th International Symposium on Artificial Intelligence and Mathematics，2006.

[10]Bondy J A，Murty U S R.Graph theory with applications[M].London：Macmilian，1976.

[11]肖華勇，程海礁，王月興.九宮數(shù)獨的方程求解算法研究[J].計算機應(yīng)用，2012，32（10）：2907-2910.

[12]Lewis R.Metaheuristics can solve sudoku puzzles[J].Journal of Heuristics，2007，13：387-401.

[13]直觀法玩數(shù)獨——SUDOKU[EB/OL].[2012-10-20].http：// hi.baidu.com/kiwy07/item/2e00ad1665e41458f0090e0b.

[14]Lei Lei，Shen Fuke.The design and implementation of the algorithm about sudoku[J].Computer Knowledge and Technology，2007，2：481-482.

[15]肖華勇，馬麗娜，程海礁.老板數(shù)獨的方程求解算法研究[J].計算機工程與應(yīng)用，2014，50（9）：41-44.

XIAO Huayong,YANG Feifei,HUANG Benru

Department of Mathematics,School of Science,Northwestern Polytechnical University,Xi’an 710129,China

Honeycomb sudoku is a kind of deformation of sudoku which is similar to the honeycomb and difficult to solve.Section 1 of the full paper presents the linear programming equation set equivalent with the honeycomb sudoku puzzle. Section 2,the properties of the solution algorithm of honeycomb sudoku are derived from the equation set,such as the property of removing the candidate numbers,the contradictoriness,the unique certainty and the invariance of enumeration.Section 3 solves the honeycomb sudoku with a regional sequence enumeration method,and the difference of solving algorithm between the honeycomb sudoku and standard sudoku is compared.The proposed algorithm is proved effective for the honeycomb sudoku of medium level by examples.

honeycomb sudoku;deformation of sudoku;equation set;regional sequence enumeration method

蜂巢數(shù)獨是類似蜂巢難度又高的變形數(shù)獨，它有著重要的研究意義。由蜂巢數(shù)獨謎題提出與之等價的線性規(guī)劃方程組；從方程組出發(fā)推導(dǎo)出求解數(shù)獨算法的性質(zhì)，如候選數(shù)刪除性質(zhì)、矛盾性質(zhì)、唯一確定性質(zhì)、枚舉不變性質(zhì)；基于以上性質(zhì)，提出用區(qū)域序列枚舉方法求解蜂巢數(shù)獨。結(jié)合實例計算，提出的算法對中度難度級別的蜂巢數(shù)獨是有效的。

蜂巢數(shù)獨；變形數(shù)獨；方程組；區(qū)域序列枚舉

A

O157

10.3778/j.issn.1002-8331.1305-0513

XIAO Huayong,YANG Feifei,HUANG Benru.Equation model for honeycomb sudoku based on regional sequence enumeration method.Computer Engineering and Applications,2014,50（23）：36-40.

西北工業(yè)大學(xué)2013大學(xué)生創(chuàng)新項目基金（No.07gz1601）。

肖華勇（1969—），男，博士，副教授，主要研究方向：統(tǒng)計優(yōu)化；楊菲菲（1988—），女，碩士研究生，主要研究方向：統(tǒng)計優(yōu)化；黃奔茹（1992—），女，主要研究方向：統(tǒng)計學(xué)。E-mail：yangfeifei@mail.nwpu.edu.cn

2013-06-04

2013-07-22

1002-8331（2014）23-0036-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-08-15,http://www.cnki.net/kcms/detail/11.2127.TP.20130815.1635.003.html