江 赟

(重慶工商大學(xué) 重慶市檢測(cè)控制集成系統(tǒng)工程實(shí)驗(yàn)室，重慶 400067)

基于膜計(jì)算模型的數(shù)獨(dú)游戲基本解法*

江 赟

(重慶工商大學(xué) 重慶市檢測(cè)控制集成系統(tǒng)工程實(shí)驗(yàn)室，重慶 400067)

為了更好地求解數(shù)獨(dú)問題，提出了一種新的求解方法，利用一個(gè)具有抑制催化和膜溶解規(guī)則以及進(jìn)化規(guī)則的優(yōu)先級(jí)的膜系統(tǒng)來進(jìn)行求解；結(jié)果表明，對(duì)于一個(gè)數(shù)獨(dú)問題，只要其所有部分解都至少包含一個(gè)具有唯一解的單元格，方法都是有效的；如果數(shù)獨(dú)問題可以利用此策略求解，則膜系統(tǒng)在計(jì)算的最后一步將問題的解編碼并返回物質(zhì)YES，否則，膜系統(tǒng)可以檢測(cè)出數(shù)獨(dú)問題不符合上述特征，返回物質(zhì)NO，計(jì)算停止；方法求解策略與人類求解數(shù)獨(dú)問題的思考過程非常類似，并且給出的是數(shù)獨(dú)問題的統(tǒng)一解，即與數(shù)獨(dú)問題的維度和提示數(shù)無關(guān)。

膜計(jì)算；數(shù)獨(dú)游戲；細(xì)胞膜系統(tǒng)

數(shù)獨(dú)游戲(Sudoku)是一種非常受歡迎的數(shù)學(xué)智力拼圖游戲，它既不需要豐富的百科知識(shí)，也不需要掌握大量的詞匯，是老少皆宜的游戲。傳統(tǒng)的9×9格子數(shù)獨(dú)游戲(九宮數(shù)獨(dú))的形式如圖1所示，為了方便描述，用數(shù)字1～9來標(biāo)識(shí)行(row)和列(column)，這樣每個(gè)小單元格(cell)就有了坐標(biāo)。這81個(gè)單元格又組成9個(gè)小九宮格(box)，分別標(biāo)記為1～9。數(shù)獨(dú)游戲的規(guī)則很簡(jiǎn)單，在81個(gè)單元格中填入數(shù)字1～9，要求填入的數(shù)字在每行和每列都不能有重復(fù)，同時(shí)在每個(gè)小九宮格中也不能有重復(fù)。游戲開始時(shí)會(huì)將一些位置上的數(shù)字固定下來，這稱為提示數(shù)(或起始數(shù))，根據(jù)提示數(shù)的位置和數(shù)量可以將數(shù)獨(dú)游戲分為不同的難度等級(jí)。

圖1 一個(gè)簡(jiǎn)單的數(shù)獨(dú)例子Fig.1 A simple example of Sudoku

數(shù)獨(dú)游戲不僅具有娛樂性，而且從數(shù)學(xué)的角度看具有重要的性質(zhì)。標(biāo)準(zhǔn)九宮數(shù)獨(dú)一共有6 670 903 752 021 072 936 960=9!×722×27×27 704 267 971種合法的數(shù)獨(dú)終盤，其中最后一個(gè)因子是質(zhì)數(shù)[1]。其次，求解n2×n2個(gè)單元格的數(shù)獨(dú)問題已被證明是一個(gè)NP完全問題[2]。

用計(jì)算機(jī)求解數(shù)獨(dú)問題最原始的方法是暴力破解法，即用窮舉的辦法遍歷整個(gè)解空間，這種方法的遍歷和回溯都是在最大深度上進(jìn)行的，需要大量的時(shí)間和內(nèi)存。目前有多種方法求解數(shù)獨(dú)問題。文獻(xiàn)[3]利用約束規(guī)劃的方法，通過設(shè)置一個(gè)目標(biāo)函數(shù)與約束函數(shù)，采用分支定界法求解。文獻(xiàn)[4]將數(shù)獨(dú)問題轉(zhuǎn)化為組合優(yōu)化問題，然后利用編碼、初始化、交叉、變異及局部搜索具有特點(diǎn)的遺傳算法來進(jìn)行求解。文獻(xiàn)[5]將數(shù)獨(dú)問題轉(zhuǎn)化為一個(gè)1范數(shù)的優(yōu)化問題，然后通過引入松弛變量，轉(zhuǎn)化為一個(gè)線性規(guī)劃問題，再利用算法進(jìn)行快速求解。文獻(xiàn)[6]采用分布式勢(shì)博弈方法進(jìn)行求解，將數(shù)獨(dú)問題轉(zhuǎn)化為勢(shì)博弈模型，然后利用學(xué)習(xí)動(dòng)力進(jìn)行逐步優(yōu)化以達(dá)到勢(shì)博弈的最優(yōu)狀態(tài)——納什均衡點(diǎn)。

提出一種新的求解思路，使用膜計(jì)算求解數(shù)獨(dú)問題。對(duì)于一個(gè)n維的數(shù)獨(dú)，只要其所有部分解都至少包含一個(gè)具有唯一解的單元格，就可以構(gòu)造一族膜系統(tǒng)來進(jìn)行求解。這一族膜系統(tǒng)中每一個(gè)膜系統(tǒng)∏(n)是一個(gè)具有輸入的膜系統(tǒng)，數(shù)獨(dú)問題編碼為一個(gè)多重集作為輸入。求解的基本思想是利用膜計(jì)算中的抑制催化、膜溶解及規(guī)則間的優(yōu)先級(jí)等操作來尋找只有一個(gè)候選數(shù)的單元格。如果數(shù)獨(dú)問題可以利用此策略求解，則膜系統(tǒng)在計(jì)算的最后一步將問題的解編碼并返回物質(zhì)YES，否則，膜系統(tǒng)可以檢測(cè)出數(shù)獨(dú)問題不符合上述特征，返回物質(zhì)NO，計(jì)算停止。這種求解策略非常類似人類求解數(shù)獨(dú)問題的思考過程[7]。

1 模 型

膜計(jì)算是自然計(jì)算的一個(gè)分支，由歐洲科學(xué)院院士、羅馬尼亞科學(xué)院院士Gheorghe Paun于1998年在芬蘭圖爾庫計(jì)算機(jī)科學(xué)中心提出[8]。膜計(jì)算是當(dāng)前計(jì)算機(jī)科學(xué)、數(shù)學(xué)、生物學(xué)等多學(xué)科交叉的研究熱點(diǎn)，旨在從活細(xì)胞的結(jié)構(gòu)和功能中以及從組織和器官等細(xì)胞群的協(xié)作中抽象出計(jì)算模型，即膜計(jì)算模型(或稱為膜系統(tǒng))。膜計(jì)算模型具有良好的分布式結(jié)構(gòu)和并行處理信息能力。截至目前，主要有3種類型的膜計(jì)算模型：細(xì)胞膜系統(tǒng)[8]、組織膜系統(tǒng)[9]和神經(jīng)膜系統(tǒng)[10]。關(guān)于膜計(jì)算的詳細(xì)內(nèi)容，可以參考膜計(jì)算網(wǎng)站及相關(guān)專著[11-12]。所采用的是細(xì)胞膜系統(tǒng)，計(jì)算模型是模仿細(xì)胞的結(jié)構(gòu)和功能，其基本組成要素包括膜結(jié)構(gòu)、對(duì)象和規(guī)則。

所采用的膜系統(tǒng)使用了以下類型的規(guī)則：

(2) 膜溶解規(guī)則：[u]e→o，多重集u導(dǎo)致膜e溶解，并且生成物質(zhì)o。

(3) 物質(zhì)輸出規(guī)則：[a]e→[]ea，物質(zhì)a被送出標(biāo)記為e的膜。

此外，在使用規(guī)則時(shí)系統(tǒng)還用到了規(guī)則間的優(yōu)先級(jí)。

具體來說，求解數(shù)獨(dú)問題的一族膜系統(tǒng)的結(jié)構(gòu)如下：

膜系統(tǒng)的字母表為

膜的標(biāo)記集合為H={0,1}

膜結(jié)構(gòu)為μ=[[]1]0

系統(tǒng)處于初始組態(tài)時(shí)膜1和膜0中對(duì)象多重集分別為

當(dāng)膜系統(tǒng)求解一個(gè)具體的數(shù)獨(dú)問題時(shí)，膜1中還應(yīng)包含編碼為zijm的問題的輸入。

i0=1，即輸入膜為膜1。

系統(tǒng)的規(guī)則如下所示:

R3:[,[其中i,j,x∈{1，2,…，n2}

R4:[d,其中i,j∈{1，2,…，n2}

R6:[，其中i,j,x∈{1，2,…，n2}

R7:[，其中i,j,x,q∈{1，2,…，n2}

利用上述膜系統(tǒng)求解數(shù)獨(dú)問題的總體思想是將求解過程分為兩個(gè)階段：檢查階段和重啟階段。在檢查階段，膜系統(tǒng)查找只有一個(gè)候選數(shù)的單元格。一旦找到了這樣的單元格，則候選數(shù)填入其中。在檢查階段后，系統(tǒng)進(jìn)入重啟階段，所有的輔助對(duì)象在此階段重新計(jì)算，然后系統(tǒng)又開始進(jìn)入檢查階段。當(dāng)所有的單元格都填入了數(shù)字，求解完畢，或者在某個(gè)檢查階段沒有找到只有一個(gè)候選解的單元格時(shí)，這個(gè)檢查-重啟循環(huán)結(jié)束。

2 求 解

用一個(gè)如圖2所示的九宮數(shù)獨(dú)的求解過程來解釋上述膜系統(tǒng)。

圖2 一個(gè)3維的數(shù)獨(dú)問題Fig.2 A Sudoku problem of order 3

如圖2所示，數(shù)獨(dú)問題有27個(gè)提示數(shù)，相應(yīng)地，系統(tǒng)的輸入即數(shù)獨(dú)問題編碼為z133z147z181z241z259z276z346z382z452z473z527z553z578z629z645z671z684z735z756z779z811z822z849z883z924z939z987。

由于系統(tǒng)中不再有物質(zhì)zijx，因此集合R1中的規(guī)則不再適用。此時(shí)，系統(tǒng)處于組態(tài)C1，集合R2中的規(guī)則適用，表1的對(duì)象從膜1中移除，系統(tǒng)進(jìn)化到組態(tài)C2。

表1 系統(tǒng)處于組態(tài)C1時(shí)從膜1中移除的對(duì)象Table 1 Objects removed from membrane 1 at configuration C1

各單元格中的候選解由R6中的規(guī)則來檢測(cè)。當(dāng)系統(tǒng)處于組態(tài)C5時(shí)，如果膜1中同時(shí)存在對(duì)象fix，cjx，bkx和boxijk，這意味著數(shù)字x沒有填入第i行，第j列和第k宮，因此數(shù)字x是單元格(i,j)的一個(gè)候選解。目前系統(tǒng)中不存在對(duì)象mijx，因此相應(yīng)的三元組(i,j,x)都會(huì)觸發(fā)R6中的一條規(guī)則，系統(tǒng)從而達(dá)到組態(tài)C6。使用集合R6中的一條規(guī)則將移除相應(yīng)的對(duì)象rij，并產(chǎn)生對(duì)應(yīng)的對(duì)象aij。由于使用R6中的規(guī)則會(huì)產(chǎn)生對(duì)象mijx，因此每條規(guī)則只能使用一次。

集合R6中的規(guī)則使用完畢之后，對(duì)象aij的數(shù)目意味著單元格(i,j)中候選解的個(gè)數(shù)。此時(shí)由集合R7中的規(guī)則來檢測(cè)數(shù)字x是單元格(i,j)的唯一候選解：如果在使用R6中的規(guī)則后，系統(tǒng)中有唯一一個(gè)aij和n2-1個(gè)rij，并且單元格(i,j)為空，則單元格(i,j)有唯一候選解。除了檢測(cè)唯一候選解的作用之外，集合R7中的規(guī)則將移除對(duì)象fixcjxbkx并引進(jìn)對(duì)象sijx，p和w。其中對(duì)象sijx對(duì)應(yīng)數(shù)獨(dú)問題的解中的一個(gè)數(shù)字和一個(gè)單元格，p意味著一個(gè)新的數(shù)字填入了數(shù)獨(dú)中(當(dāng)p的個(gè)數(shù)達(dá)到n4個(gè)時(shí)，重啟-檢測(cè)循環(huán)結(jié)束)，w表示集合R7中的規(guī)則使用過一次。

在圖2所示的數(shù)獨(dú)中，首次使用R6中的規(guī)則后，單元格(3,7)，(5,4)，(6,1)和(7,8)對(duì)應(yīng)的對(duì)象aij剛好都只有一個(gè)，這意味著這些單元格中的候選解是唯一解。因此集合R7中有4條規(guī)則被觸發(fā)，物質(zhì)s377、s544、s613、s788被引入到系統(tǒng)中，系統(tǒng)從而到達(dá)組態(tài)C7。

此時(shí)數(shù)獨(dú)的部分解如圖3所示。

圖3 系統(tǒng)處于組態(tài)C7時(shí)對(duì)應(yīng)的數(shù)獨(dú)問題部分解Fig.3 Partial solution at configuration C7

使用集合R7中的規(guī)則導(dǎo)致組態(tài)C8中有4個(gè)對(duì)象w。其中一個(gè)w和k0一起生成對(duì)象k2(組態(tài)C8)，而其余的w將在下一步被移除(組態(tài)C9)。此時(shí)膜1中物質(zhì)p的個(gè)數(shù)尚未達(dá)到n4，因此不能使用集合R10中的規(guī)則，接下來使用集合R11中的規(guī)則，物質(zhì)d被移除，同時(shí)k2進(jìn)化為k1，系統(tǒng)達(dá)到組態(tài)C10，檢查階段結(jié)束。

物質(zhì)d是一個(gè)強(qiáng)抑制劑，沒有它的存在，集合R3中的規(guī)則適用，重啟階段再次開始。系統(tǒng)接下來進(jìn)入新的檢測(cè)階段，通過使用集合R7中的4條規(guī)則，系統(tǒng)中出現(xiàn)了s723、s448、s285、s717。這意味著4個(gè)新的數(shù)被填入數(shù)獨(dú)中(系統(tǒng)處于組態(tài)C15時(shí)對(duì)應(yīng)的數(shù)獨(dú)部分解如圖4所示)。

圖4 系統(tǒng)處于組態(tài)C15時(shí)對(duì)應(yīng)的數(shù)獨(dú)問題部分解Fig.4 Partial solution at configuration C15

這個(gè)檢測(cè)—重啟循環(huán)不斷進(jìn)行下去，在組態(tài)C23時(shí)系統(tǒng)中引入了對(duì)象s174、s228、s638、s657、s742、s943、s951、s972；

組態(tài)C31時(shí)引入s237、s293、s497、s666、s692、s764、s791、s836、s867、s875、s894、s918；

組態(tài)C39時(shí)引入s262、s354、s595、s858、s965、s996；

組態(tài)C47時(shí)引入s112、s155、s168、s214、s319、s363；

組態(tài)C55時(shí)引入s126、s199、s325、s331、s398、s415、s434、s532；

組態(tài)C63時(shí)引入s421、s486、s516；

組態(tài)C71時(shí)引入s469、s561、s589。

此時(shí)膜1中的對(duì)象sijx即為數(shù)獨(dú)問題的解的編碼，于是數(shù)獨(dú)問題的解如圖5所示。

圖5 數(shù)獨(dú)問題的解Fig.5 Solution at configuration C71

膜系統(tǒng)繼續(xù)計(jì)算，系統(tǒng)處于組態(tài)C73時(shí)膜1中有81個(gè)物質(zhì)p，因此規(guī)則R10被觸發(fā)，膜1溶解并且其中的所有物質(zhì)進(jìn)入膜0。在下一步，物質(zhì)YES被送出系統(tǒng)，而其余對(duì)象(除sijx外)都被移除，因此當(dāng)系統(tǒng)處于最終組態(tài)時(shí)環(huán)境中有一個(gè)物質(zhì)YES以及包含解的編碼的膜。

如前所述，并不是所有數(shù)獨(dú)問題的所有部分解都至少包含一個(gè)具有唯一解的單元格。在這種情況下，當(dāng)系統(tǒng)計(jì)算到達(dá)檢查階段時(shí)集合R7中沒有規(guī)則可使用，于是沒有物質(zhì)w產(chǎn)生。由于系統(tǒng)中沒有物質(zhì)w，集合R8中的規(guī)則不能使用，根據(jù)規(guī)則的優(yōu)先級(jí)，接下來使用集合R9中的溶解規(guī)則。隨著物質(zhì)NO被送入膜0，重啟-檢查循環(huán)結(jié)束，下一步一個(gè)物質(zhì)NO被送出膜系統(tǒng)進(jìn)入到環(huán)境中，從而計(jì)算停止。

3 結(jié)論與展望

研究了具有抑制催化、膜溶解以及規(guī)則優(yōu)先級(jí)的膜系統(tǒng)的計(jì)算能力。對(duì)于一個(gè)數(shù)獨(dú)問題，只要其所有部分解都至少包含一個(gè)具有唯一解的單元格，就可以設(shè)計(jì)出一個(gè)膜系統(tǒng)來進(jìn)行求解，并且求解策略與人類求解數(shù)獨(dú)問題的思考過程非常類似。設(shè)計(jì)的求解策略可以找到很多數(shù)獨(dú)問題的解，但是并不能解決所有的數(shù)獨(dú)問題。接下來可以考慮研究利用膜計(jì)算模型求解更困難的數(shù)獨(dú)問題，比如因卡拉數(shù)獨(dú)。

[1] FELHENHAUER B,JAVIS F.Enumerating Possible Sudoku Grids[EB/OL].http://www.shef.ac.uk/pmlafj/sudoku/sudoku.pdf

[2] YATO T,SETA T.Complexity and Completeness of Finding Another Solution and Its Application to Puzzles[J].IEICE Transactions on Fundamentals of Electronics Commu-nications and Computer Sciences,2003,E86-A(5):1052-1060

[3] CRAWFORD B,ARANDA M,CASTRO C,et al.Using Constraint Programming to Solve Sudoku Puzzles[C]∥Proceedings of the Third International Conference on Convergence and Hybrid Information Technology,2008:926-931

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

LIU Y F,LIU S Y.Algorithm Based on Genetic Algorithm for Sudoku Puzzles[J].Computer Science,2010,37(3):225-226

[5] 張煜東,王水花,霍元愷,等.一種基于稀疏優(yōu)化的數(shù)獨(dú)求解新方法[J].南京信息工程大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,3(1):23-27

ZHANG Y D,WANG S H,HUO Y K,et al.A Novel Sudoku Solving Method Based on Sparse Optimization[J].Journal of Nanjing University of Information Science and Technology (Natural Science Edition),2011,3(1):23-27

[6] 商文喜,蔚承建,王開,等.數(shù)獨(dú)問題的一個(gè)分布式物理博弈求解[J].計(jì)算機(jī)應(yīng)用與軟件,2014(12):113-115.

SHANG W X,WEI C J,WANG K,et al.A Distributed Solution of Physical Game to Sudoku Problem[J].Computer Application and Software,2014(12):113-115

[7] 陳俊.智能算法在足球機(jī)器人定向運(yùn)動(dòng)中的應(yīng)用[J].重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,30(3):46-49

CHEN J.Application of Intelligence Algorithm to Oriented Movement of Soccer Robot[J].Journal of Chongqing Technology and Business University (Natural Science Edition),2013,30(3):46-49

[8] PAUN G.Computing with Membrane[J].Journal of Computer and System Science,2000,61(1):108-143

[9] MARTIN-VIDE C,PAUN G,PAZOS J,et al.Tissue P System[J].Theoretical Computer Science,2003,296(2):295-326

[10] IONESCU M,PAUN G,YOKOMARI T.Spiking Neural P Systems[J].Fundamenta Informaticae,2006,71(2-3):279-308

[11] PAUN G.Membrane Computing—An Introduction[M].Berlin Heidelberg:Springer-Verlag,2002

[12] CIOBANU G,PAUN G,PEREZ-JIMENEZ M J.Appli-cation of Membrane Computing[M].Berlin Heidelberg:Springer-Verlag,2006

責(zé)任編輯：田 靜

Basic Solution to Sudoku Based on Membrane Computing Model

JIANG Yun

(Chongqing Engineering Laboratory for Detection, Control and Integrated System;Chongqing Technology and Business University, Chongqing 400067, China)

Sudoku problem has been proved to be an NP complete problem. In order to solve the Sudoku more efficiently, a novel approach was proposed.We designed a family of P systems using enzymatic rules, dissolution rules and priorities among sets of rules to solve a large amount of Sudokus. Results show that the strategy is effective as long as Sudokus satisfy the property that in its all partial solutions there exists at least one square with a unique candidate. If the solution can be solved by using this strategy, the P system encodes the solution and returns Yes in the last step of computation. Otherwise, the P system detects that the property is not satisfied and the computation halts by returning No. The solution is searched by using a human-style method based on looking for squares where only one candidate can be placed.Meanwhile, the solution is a uniform solution to Sudoku problem, in other words, it is irrelevant to the order of the problem and the hint numbers.

membrane computing; Sudoku; cell-like P system

2017-02-24；

2017-03-20.

國(guó)家自然科學(xué)基金項(xiàng)目資助(61502063).

江赟(1983-)，女，湖北紅安人，講師，博士，從事生物計(jì)算研究.

10.16055/j.issn.1672-058X.2017.0004.013

TP38

A

1672-058X(2017)04-0070-06