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

黃祖賢

(中南大學(xué)信息科學(xué)與工程學(xué)院，長(zhǎng)沙410012)

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

黃祖賢

(中南大學(xué)信息科學(xué)與工程學(xué)院，長(zhǎng)沙410012)

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

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

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

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

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

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

1)當(dāng)前格子不為空，則返回FALSE；

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

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

4)返回TRUE。

2 生成算法

2.1 終盤生成

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

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

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

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

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

4)輸出1個(gè)數(shù)獨(dú)終盤。

2.1.2 拉斯維加斯算法

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

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

2.2 有唯一解初盤的生成

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

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

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

2)“挖洞”約束

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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

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

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

[5]王瓊，鄒晟.數(shù)獨(dú)問(wèn)題的求解、評(píng)價(jià)與生成算法的研究[J].南京師范大學(xué)學(xué)報(bào)：工程技術(shù)版,2010,10(1):76-79.

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

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

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

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

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

責(zé)任編輯：何莉

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-)，女，安徽馬鞍山人，主要研究方向?yàn)橛?jì)算機(jī)科學(xué)與技術(shù)。

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