肖華勇，楊菲菲，黃奔茹

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

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

肖華勇，楊菲菲，黃奔茹

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

1 引言

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

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

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

圖1 初級(jí)蜂巢數(shù)獨(dú)謎題

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

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

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

2.1 單元格的表示

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

每個(gè)單元格用坐標(biāo)(i，j)表示。i代表行號(hào)，從上到下 i=1，2，…，9 ；j代表列號(hào)，從左到右為 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)}。

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

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

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

為方便起見(jiàn)，把某行、某正斜線、某反斜線都稱為一個(gè)區(qū)。設(shè)某區(qū)有L個(gè)格子，則該區(qū)只允許L個(gè)連續(xù)數(shù)字。若該區(qū)所填數(shù)字單元格大于1個(gè)時(shí)，取所填數(shù)字中最小數(shù)字為a，最大數(shù)字為b；若該區(qū)所填數(shù)字單元格只有一個(gè)時(shí)，a取該單元格的值，且b=a；則該區(qū)候選數(shù)范圍為 [m，M]，其中 m=max{1，b-L+1}，M=min{9，a+L-1}。當(dāng)該區(qū)一個(gè)數(shù)字也沒(méi)有填，取m=1，M=9。由于該區(qū)所填數(shù)字是L個(gè)連續(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 個(gè)連續(xù)數(shù)字序列可能為 [3，7]，或 [4，8]，或[5，9]，第一行必然出現(xiàn)的候選數(shù)為{5，6，7}，即 L(A1)= {5，6，7}。

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

若某個(gè)單元格所在行、正斜線、反斜線得到的候選數(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 建立決策變量

為表達(dá)方便，設(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ù)字確定時(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 時(shí)，利用該性質(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時(shí)，利用該性質(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時(shí)，利用該性質(zhì)可刪除該格子所在第t反斜線區(qū)其他格子上的候選數(shù)k。

3.2 確定性性質(zhì)

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

性質(zhì)3.2.2若 xijk=-1，k∈[M+1-L，m-1+L]對(duì)任意的 (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ù)字必為候選數(shù)k。

性質(zhì)3.2.3若 xijk=-1，k∈[M+1-L，m-1+L]對(duì)任意的 (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ù)字必為候選數(shù)k。

性質(zhì)3.2.4若 xijk=-1，k∈[M+1-L，m-1+L]對(duì)任意的 (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ù)字必為候選數(shù)k。

3.3 矛盾性質(zhì)

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

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

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

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

3.4 不變性

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

性質(zhì) 3.4.2對(duì)某 r(r=2，3，4，…)個(gè)固定格子 (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)對(duì)r個(gè)格子的多有候選數(shù)來(lái)說(shuō)，當(dāng)xi1j1k1=-1，…，xirjrkr=-1時(shí)，某個(gè)格子 (i，j)都不能填 r，則xijr=0。

4 算法應(yīng)用及實(shí)例計(jì)算

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

初始化：將數(shù)獨(dú)謎題存放在數(shù)組T[9][9]中，若格子(i，j)為空格，則令 T[i][j]=0 ；若格子 (i，j)已填入數(shù)字k，則令T[i][j]=k。基于蜂巢數(shù)獨(dú)獨(dú)特的形狀，為了保證數(shù)組的完整性，其他未有格子的部分填-1。將數(shù)獨(dú)格子的候選數(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é)的方法確定每個(gè)格子的候選數(shù)，然后根據(jù)3.1節(jié)性質(zhì)進(jìn)行候選數(shù)的刪除。

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

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

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

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

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

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

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

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

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

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

圖4 中級(jí)蜂巢數(shù)獨(dú)謎題

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

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

5 結(jié)論

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

[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ù)獨(dú)基于規(guī)則的逐步枚舉算法設(shè)計(jì)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（5）：1035-1037.

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

[6]劉延風(fēng)，劉三陽(yáng).基于遺傳算法求解數(shù)獨(dú)難題[J].計(jì)算機(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ù)獨(dú)的方程求解算法研究[J].計(jì)算機(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ù)獨(dú)——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ù)獨(dú)的方程求解算法研究[J].計(jì)算機(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ù)獨(dú)是類似蜂巢難度又高的變形數(shù)獨(dú)，它有著重要的研究意義。由蜂巢數(shù)獨(dú)謎題提出與之等價(jià)的線性規(guī)劃方程組；從方程組出發(fā)推導(dǎo)出求解數(shù)獨(dú)算法的性質(zhì)，如候選數(shù)刪除性質(zhì)、矛盾性質(zhì)、唯一確定性質(zhì)、枚舉不變性質(zhì)；基于以上性質(zhì)，提出用區(qū)域序列枚舉方法求解蜂巢數(shù)獨(dú)。結(jié)合實(shí)例計(jì)算，提出的算法對(duì)中度難度級(jí)別的蜂巢數(shù)獨(dú)是有效的。

蜂巢數(shù)獨(dú)；變形數(shù)獨(dú)；方程組；區(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)新項(xiàng)目基金（No.07gz1601）。

肖華勇（1969—），男，博士，副教授，主要研究方向：統(tǒng)計(jì)優(yōu)化；楊菲菲（1988—），女，碩士研究生，主要研究方向：統(tǒng)計(jì)優(yōu)化；黃奔茹（1992—），女，主要研究方向：統(tǒng)計(jì)學(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