黃祖賢

(中南大學信息科學與工程學院，長沙410012)

數(shù)獨游戲的問題生成及求解算法優(yōu)化

黃祖賢

(中南大學信息科學與工程學院，長沙410012)

將“數(shù)獨”問題分解為建立終盤、生成有唯一解初盤和求解初盤等子問題。運用拉斯維加斯隨機算法思想結(jié)合回溯法建立終盤，采用“挖洞”思想隱去部分數(shù)字并結(jié)合反序回溯法生成具有唯一解的初盤,依據(jù)初盤中空格數(shù)的多少對問題的難度進行劃分，創(chuàng)建不同等級難度的“數(shù)獨”游戲，并對求解數(shù)獨問題的候選數(shù)搜索算法進行優(yōu)化改進。實例分析結(jié)果表明，優(yōu)化后的候選數(shù)搜索算法性能提高了50%以上，驗證了所提出算法模型的有效性。

數(shù)獨；回溯法；唯一解；候選數(shù)；搜索算法

數(shù)獨是1種利用簡單邏輯推理就能解決的數(shù)字謎題，其雛形源于1979年美國的數(shù)學邏輯游戲雜志—Dell Pencil Puzzles&Word Games發(fā)表的稱之為“NumberPlace”的游戲[1-2]。目前，數(shù)獨作為1種智力游戲已經(jīng)風靡世界，其游戲規(guī)則為：在由9個小宮格組成的大九宮格(9格×9格)里，根據(jù)已知數(shù)字，利用邏輯和推理，填出剩余空格的數(shù)字1～9，且每個數(shù)字在其所在的行、列和小九宮格中出現(xiàn)且只出現(xiàn)1次[3]。初始數(shù)字的多寡與位置，一定程度上決定著題目的難易程度以及解是否能夠唯一[4]。有學者認為通過對數(shù)獨游戲的思考能夠降低老年癡呆和帕金森綜合癥的患病率[5]，因此數(shù)獨游戲吸引著無數(shù)“獨迷”參與。

目前，許多學者對數(shù)獨的求解與生成算法進行了深入研究，如，胥劍[6]使用回溯法快速求解數(shù)獨問題，薛源海等[7]提出基于“挖洞”思想運用反證法判斷解的唯一性，并對其進行剪枝優(yōu)化，達到了較好的性能。候選數(shù)搜索法在求解數(shù)獨問題上也有廣泛的應用，常見的方法有唯一候選數(shù)法、隱形唯一候選數(shù)法和區(qū)塊刪減法等[8]。文中根據(jù)數(shù)獨求解規(guī)則，對在終盤的基礎上生成的數(shù)獨初盤可能出現(xiàn)的不同解進行分析，采用反序回溯法檢驗初盤解的唯一性，并對傳統(tǒng)的候選數(shù)搜索算法進行優(yōu)化改進。

1 數(shù)獨求解規(guī)則

數(shù)獨必須遵循邏輯性、可推導性等原則，在求解數(shù)獨時，必須讓每一步有規(guī)可循，每一步推導有根有據(jù)[5]。數(shù)獨展開邏輯推理需確保：數(shù)字1～9在每一行中各出現(xiàn)且只出現(xiàn)1次；數(shù)字1～9在每一列中各出現(xiàn)且只出現(xiàn)1次；數(shù)字1～9在每一個小九宮中，各出現(xiàn)1次且不重復。數(shù)獨求解規(guī)則的實現(xiàn)步驟如下：

1)當前格子不為空，則返回FALSE；

2)將所選數(shù)字與該格同行同列的數(shù)字進行橫向和縱向比較，若存在某數(shù)與所給參數(shù)數(shù)字相等，則返回FALSE；

3)將所選數(shù)字與該格所在宮格的數(shù)字進行比較，若存在某數(shù)與所給參數(shù)數(shù)字相等，則返回FALSE；

4)返回TRUE。

2 生成算法

2.1 終盤生成

2.1.1 基于小數(shù)的回溯法

基于小數(shù)的回溯法采用從左至右、從上至下的搜索方式，從初盤的第一個空格開始，由1到9搜索滿足約束條件的1個解，以該可能解為出發(fā)點，對下一個空格繼續(xù)進行由1到9的試探性搜索，如果在某一次搜索中某一空格的所有可能解都不能滿足約束條件，則返回上一個空格，放棄原有的可能解，使用該空格的下一個可能解。依次類推，直到所有空格的可能解都被找到，則得到了該問題的一個完整解[6]。其算法步驟如下：

1)判斷數(shù)獨最后一行是否已填寫完，如果是，則跳至步驟4)。否則，自左向右、自上而下搜索下一個空格；

2)由1到9遍歷搜索，與該空格所在行、列以及所在宮的其他有效數(shù)字進行比較，若存在1個數(shù)滿足約束條件，則將該數(shù)字填入該空格，跳至步驟1)；

3)若該空格的所有可能解都不能滿足約束條件，返回上一個空格，其值重置為0，搜索并使用該空格的下一個可能解，并將該數(shù)字填入該空格，跳至步驟1)，否則繼續(xù)執(zhí)行該步驟；

4)輸出1個數(shù)獨終盤。

2.1.2 拉斯維加斯算法

采用拉斯維加斯算法隨機生成1個數(shù)獨題的終盤。首先，在1個數(shù)獨“空盤”中隨機選中n個格子，在這些格子內(nèi)隨機填入數(shù)字1～9；然后，調(diào)用上述求解器對已知n格的數(shù)獨題S(n)進行求解。完成上述兩步操作的JAVA代碼段為BOOL Las-vegas(n)：如果S(n)有解，則返回TRUE；否則返回FALSE。拉斯維加斯算法的思想便是不斷重復執(zhí)行Las-vegas(n)，直至其返回TRUE為止，用JAVA編程語言表示如下

根據(jù)拉斯維加斯的算法思想可知，代碼段Las-vegas(n)返回TRUE（即成功生成終盤）的概率p與n有關。已有研究表明[7]，當n=11時，p能達到0.997，且p隨著n的減小而增大，但運行時間延長。故將n設為11。

2.2 有唯一解初盤的生成

基于“挖洞”思想生成有唯一解的初盤?！巴诙础彼枷刖褪恰巴谌ァ睌?shù)獨終盤上的一些格子，使其成為至少有1個解的數(shù)獨問題?！巴诙础钡臋C制多種多樣，國內(nèi)現(xiàn)有的研究中，多將其與數(shù)獨問題的難度等級劃分結(jié)合，生成有解初盤[7]。文中借鑒這一思想，采取1種較為簡單的“挖洞”機制。“挖洞”流程中的關鍵問題如下。

1)“挖洞”數(shù)目

“挖洞”數(shù)目由保留格子的數(shù)目決定。文中簡化了對數(shù)獨問題的難度劃分標準，以初盤上非空格的數(shù)量為依據(jù)、在一定區(qū)間內(nèi)將數(shù)獨問題劃分為5個難度等級，如表1。

2)“挖洞”約束

從已知格的分布入手，對“挖洞”操作加以約束。規(guī)定，數(shù)獨初盤中每行已知格的數(shù)目至少為2個，則已知格的總數(shù)至少為18個，因為[20，24]區(qū)間的整數(shù)均不能被9整除，所以各行不可能均多出1個已知格，只能有些行多1個或2個、有些行不增加，即每行至多有4個已知格。

用1個整型一維數(shù)組already[9]存儲每行中已知格的數(shù)目，定義1個整型二維數(shù)組displayed[9][4]存放每行已知格的位置信息(隨機產(chǎn)生，數(shù)組內(nèi)的無效位置信息置“-1”操作“挖去”格子)，將數(shù)組外其他位置的格子“挖去”。實例如圖1，2。

圖1直觀描述了一維數(shù)組already和二維數(shù)組displayed的對應關系，圖2中灰格為由displayed確定的數(shù)獨初盤上已知格的位置，白格為被“挖去”的格子。

表1 難度等級對應的“挖洞”數(shù)目Tab.1 Difficulty level corresponding to the number of holes

3)基于大數(shù)(反序)的回溯法解唯一性的判斷

借助數(shù)獨問題求解算法—回溯法提出1個新的策略來檢驗“挖洞”后的數(shù)獨初盤是否具有唯一解。數(shù)獨終盤中，對某幾行或某幾列的2個數(shù)(或多個數(shù))的位置同時進行兩兩替換，得到的仍然是1個滿足約束條件的數(shù)獨終盤?？梢酝茢啵瑢τ凇巴诙础焙蟮臄?shù)獨初盤，若存在多個解，則一定存在某些數(shù)字相對原終盤出現(xiàn)兩兩替換的現(xiàn)象。文中提出基于大數(shù)的回溯法對“挖洞”后的初盤進行求解用以檢測上述情況中的多個解，其算法步驟為：

(1)判斷數(shù)獨最后一行是否已填寫完，如果是，則跳至步驟(4)。否則，自左向右、自上而下搜索下一個空格；

(2)由9到1遍歷搜索，與該空格所在行、列以及所在宮的其他有效數(shù)字進行比較，若存在滿足約束條件的數(shù)，則將該數(shù)字填入該空格，跳至步驟(1)；

(3)若該空格的所有可能解都不能滿足約束條件，返回到上一個空格，其值重置為0，搜索并使用該空格的下一個可能解，并將該數(shù)字填入該空格，跳至步驟(1)；

(4)輸出數(shù)獨終盤，若該次求解輸出的終盤與原終盤有異，則重復進行新的“挖洞”約束。即一旦出現(xiàn)其他解，就放棄現(xiàn)有初盤，這在一定程度上降低了算法的復雜程度。

采用該算法與基于小數(shù)的回溯法對“挖洞”后的初盤進行求解，結(jié)果如圖3。比較圖3(a)，(b)可以發(fā)現(xiàn)，2種算法求解出的結(jié)果不同，在基于小數(shù)的回溯數(shù)獨生成算法下，基于大數(shù)的回溯算法能夠有效檢測出某一“挖洞”初盤的多個解。

采用基于大數(shù)的回溯算法生成具有唯一解的初盤過程如圖4。第三次“挖洞”后得到唯一解初盤如圖4(c)，圖4(a)是對第一次進行“挖洞”得到的初盤進行唯一解判斷的結(jié)果。比較圖4(a)，(c)中圈出部分可知，與原初盤有異，該初盤不可用。同理，由圖4(b)知，第二次進行“挖洞”得到的初盤仍不可用。圖4(c)顯示了第三次進行“挖洞”后具有唯一解的初盤，表明該判斷結(jié)果有效可信。

3 候選數(shù)優(yōu)化

國內(nèi)已有研究將基于人工智能的候選數(shù)法與回溯法相結(jié)合求解數(shù)獨問題，其候選數(shù)優(yōu)化算法相較于回溯法，縮短的時間至少為1/3[9]。文中采用相似的策略進行數(shù)據(jù)結(jié)構(gòu)的設計，從候選數(shù)最少的空格出發(fā)，對候選數(shù)法進行優(yōu)化以進一步提高求解速度。候選數(shù)優(yōu)化過程的關鍵步驟。

1)求出候選數(shù)集 以候選數(shù)法求解數(shù)獨問題時，必須明確數(shù)獨初盤中每一個空格的候選數(shù)集合。產(chǎn)生候選數(shù)集合的方法是從1到9搜索，將滿足約束條件的數(shù)存入候選數(shù)集合中。用一維整型數(shù)組c存放候選數(shù)集合，一維整型數(shù)組d存儲該宮格的位置信息，d數(shù)組的長度比c數(shù)組的長度多2，其中d[0]和d[1]用來存儲該空格的行、列值，隨后存儲該宮格的候選數(shù)集合。

2)找出候選數(shù)最少的集合信息 利用JAVA編程語言中Vector向量的特性，將數(shù)獨布局中從上至下、從左至右每一個空格的d數(shù)組存入Vector＜int[]＞testVector容器中，對該容器中各候選數(shù)字集合進行排序，找到候選數(shù)字最少的集合及其在容器中的位置，并返回容器中該位置的數(shù)組。

3)候選數(shù)字回溯 在步驟2)中獲取的候選數(shù)字最少的空格內(nèi)將該數(shù)字格的候選數(shù)從小到大依次代入，每次代入后根據(jù)新的數(shù)獨布局更新候選數(shù)集合并重新找出新布局下候選數(shù)最少的集合信息，若該集合長度為2(即只含有空格的行、列值信息)，則產(chǎn)生矛盾，進行回溯。這樣，有效降低了回溯中枚舉的次數(shù)。優(yōu)化前，候選數(shù)法和回溯法的結(jié)合是簡單的，沒有為候選數(shù)集合進行排序選擇的過程。

世界上迄今難度最大的數(shù)獨游戲問題如圖5[10]，在操作系統(tǒng)Windows 8.1和CPU為Intel Core i5(1.70 GHz)的環(huán)境下，采用優(yōu)化前、后的候選數(shù)法分別對圖5所示問題進行5次求解實驗，結(jié)果見表2。

表2 對圖5數(shù)獨問題優(yōu)化前后求解性能的比較Tab.2 Acomparison of algorithm performance before and after the optimization of sudoku puzzle

從表2可看出，對于圖5所示的數(shù)獨問題，優(yōu)化后的計算時間比優(yōu)化前節(jié)省了1/2以上，表明提出的問題求解優(yōu)化算法較簡單候選數(shù)算法高效。

4 結(jié) 論

采用回溯算法建立終盤并基于“挖洞”思想生成有解初盤，提出的“基于大數(shù)的回溯算法”可以檢測和判斷數(shù)獨初盤是否存在唯一解，該算法應用于對數(shù)獨初盤產(chǎn)生多解的情況，具備較好的性能?；谇蠼鈹?shù)獨問題的候選數(shù)搜索算法，提出1個候選數(shù)優(yōu)化算法，實例分析表明，采用該算法進行數(shù)獨問題求解明顯節(jié)約了計算時間。

[1]Garns H.Number place[J].Dell Pencil Puzzles&Word Games,1979,16(5):6.

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

[3]易珺,朱靜文,曹東.數(shù)獨求解算法的設計與實現(xiàn)[J].科學技術與工程,2010,10(27):6772-6774.

[4]黃皓.數(shù)獨問題的一種簡單解法[J].電腦知識與技術，2014,10(22):5340-5344.

[5]王瓊，鄒晟.數(shù)獨問題的求解、評價與生成算法的研究[J].南京師范大學學報：工程技術版,2010,10(1):76-79.

[6]胥劍.回溯法解數(shù)獨問題[J].電腦編程技巧與維護,2009(5):17-21.

[7]薛源海，蔣彪彬，李永卓.基于“挖洞”思想的數(shù)獨游戲生成算法[J].數(shù)學的實踐與認識,2009,39(21):1-7.

[8]Flykinger.數(shù)獨的候選數(shù)法解題技巧(上）[EB/OL].（2009-07-03[2015-02-06]http://blog.sina.com.cn/s/blog_62003b8d 0100mnx4.html）.

[9]程曦，肖華勇，吳林波.數(shù)獨求解的候選數(shù)優(yōu)化算法設計[J].科學技術與工程,2011,11(26):6409-6412.

[10]姜華林.數(shù)獨問題高效算法的研究與實現(xiàn)[J].計算機光盤軟件與應用,2013,16(219):82-83.

責任編輯：何莉

AStudy of Problem Generation andAlgorithm Optimization of Sudoku Puzzle

HUANG Zuxian
(School of Information Science and Engineering,Central South University,Changsha 410012,China)

Sudoku puzzle includes creating final layout,generating original layout with unique solution,and solving original layout.To create the final layout,an algorithm based on LasVegas and backtrack was proposed,and an original layout with a unique solution was obtained by adopting the idea of digging holes through covering some numbers and combining backtrack algorithm with inverted sequence.In accordance with the division of the original layout into different difficulty groups based on the number of blank blocks there,sudoku puzzle games with different difficulty degrees were created.Furthermore,optimization was also performed in candidates searching algorithm for sudoku puzzle solution.Analysis results of examples show that performance efficiency of the optimized candidate searching algorithm is improved by over 50%,verifying the effectiveness of the proposed algorithm.

sudoku;backtrack;unique solution;candidates;search algorithm

TP312

A

10.3969/j.issn.1671-7872.2015.02.018

2015-03-09

黃祖賢(1993-)，女，安徽馬鞍山人，主要研究方向為計算機科學與技術。

1671-7872(2015)-02-0187-05