數(shù)獨(dú)謎題難度級別劃分的步數(shù)法研究

程 曦，肖華勇

（西北工業(yè)大學(xué) 理學(xué)院，陜西 西安 710129）

數(shù)獨(dú)謎題游戲中，玩家面前放置了一個(gè)9×9格子的棋盤，這個(gè)棋盤分成了9個(gè)3×3的區(qū)域。這81個(gè)單元格當(dāng)中有些格子一開始就填上了1-9之間的數(shù)字，當(dāng)滿足下面規(guī)則時(shí)，且有唯一的方法填滿剩下的格子：每個(gè)格子包含一個(gè)1-9之間的數(shù)字且每一行、列和和3×3的區(qū)域包含集合{1，2，…，9}中數(shù)字一次。

一個(gè)數(shù)獨(dú)謎題通過給定的一定格子的數(shù)字，通過這些初始數(shù)字確保能產(chǎn)生的唯一填滿數(shù)字的棋盤，把填滿數(shù)字的棋盤稱為解決數(shù)獨(dú)謎題的一種解題方法。數(shù)獨(dú)謎題游戲的目標(biāo)是通過初始給定的格子中數(shù)字，找出唯一的解題方法。

現(xiàn)階段，對數(shù)獨(dú)的研究主要在它的解答算法、生成算法，目前對數(shù)獨(dú)的研究大部分集中在數(shù)獨(dú)的解法上，比如文獻(xiàn)[1]中的使用有限遞歸預(yù)處理求解數(shù)獨(dú)謎題，文獻(xiàn)[2]中的回溯候選數(shù)法求解數(shù)獨(dú)，文獻(xiàn)[3]中的枚舉算法求解數(shù)獨(dú)，文獻(xiàn)[4]中的幾何粒子群算法求解數(shù)獨(dú)；文獻(xiàn)[5]主要是對數(shù)獨(dú)的生成算法進(jìn)行了研究與討論。

而對于數(shù)獨(dú)謎題的難度劃分，目前非常缺乏這方面的研究。我們嘗試通過玩家經(jīng)常使用的數(shù)獨(dú)策略的角度來討論劃分?jǐn)?shù)獨(dú)謎題難度級別的方法，首先介紹常用的數(shù)獨(dú)謎題策略。

1 常用數(shù)獨(dú)謎題策略

把一個(gè)單元格的行號、列號及3×3區(qū)域號組合在一起稱為這個(gè)格子的群組。兩個(gè)以上的單元格若在同一行同一個(gè)3×3區(qū)域或同一列同一個(gè)3×3區(qū)域那么我們稱這兩個(gè)單元格在同一個(gè)群組。對任意一個(gè)未填入數(shù)字的單元格，將所有已經(jīng)填入其所在行、列、3×3區(qū)域的數(shù)字排除，剩下的數(shù)字的集合稱為該單元格的候選數(shù)集合。給定一個(gè)數(shù)獨(dú)棋盤中一個(gè)單元格（i，j），其中 i代表它的行號，j代表它的列號，定義 S（i，j）為它的候選數(shù)集合。標(biāo)號如圖1所示。

圖1 數(shù)獨(dú)謎題的標(biāo)號Fig.1 Sudoku puzzle’s mark

為了解決一個(gè)數(shù)獨(dú)謎題，玩家能夠使用很多策略以及很多邏輯上的刪減法[6]，假定每個(gè)格子的候選數(shù)集合在使用策略前已經(jīng)通過謎題當(dāng)中的給定的初始數(shù)字初始化好了。

策略 1：顯性唯一候選數(shù)法，如果一個(gè)單元格（i，j），它的候選數(shù)集合只有一個(gè)可能的數(shù)字，那么直接將這個(gè)候選數(shù)字填入空格；

策略2：隱性唯一候選數(shù)法，這個(gè)策略在一個(gè)給定的單元格（i，j）中以下條件可以使用：S（i，j）包含值 k 且（i，j）所在的群組中其他的格子的候選數(shù)集合并不包含值k。

策略3：顯性對數(shù)候選數(shù)法，這個(gè)策略能在2個(gè)同群組單元格（i1，j1）、（i2，j2）且這 2 個(gè)單元格的候選數(shù)集 S（i1，j1）、S（i2，j2）有且只有2個(gè)相同的數(shù)字k1、k2中使用，那么就能將這個(gè)群組的其他單元格候選數(shù)集中這2個(gè)數(shù)字k1、k2全部刪減掉。

策略4：隱性對數(shù)候選數(shù)法，這個(gè)策略在兩個(gè)給定的同群組單元格（i1，j1）、（i2，j2）中以下條件可以使用： S（i1，j1）、S（i2，j2）均包含數(shù)字 k1、k2且（i1，j1）、（i2，j2）所在的群組中其他的單元格的候選數(shù)集合并不包含數(shù)字k1、k2，那么可以將除了k1，k2之外的數(shù)字在候選數(shù)集 S（i1，j1）、S（i2，j2）中排除。

策略 5：交叉排除法，若兩個(gè)空格或3個(gè)空格在同一個(gè)群組中（比如同行同3×3區(qū)域或同列同3×3區(qū)域），若在某一個(gè)3×3區(qū)域中，若所有可能的數(shù)字都出現(xiàn)在同一行/列時(shí)，就可以把這個(gè)數(shù)字從該行/列的其他單元格中的候選數(shù)集合中刪除或者在某一行/列中，當(dāng)所有可能的數(shù)字都出現(xiàn)在同一個(gè)3×3區(qū)域中時(shí)，就可以把這個(gè)數(shù)字從該3×3區(qū)域其他單元格候選數(shù)集合中刪除。

策略6：顯性三數(shù)集候選數(shù)法，這個(gè)策略的使用情況如下：在 3 個(gè)單元格（i1，j1）、（i2，j2）、（i3，j3）（在同一個(gè)群組）且這 3個(gè)單元格的候選數(shù)集有且僅有3個(gè)數(shù)字k1、k2、k3，那么就能將這個(gè)群組的其他單元格候選數(shù)集中這3個(gè)數(shù)字k1、k2、k3全部刪減掉。

策略 7：隱性三數(shù)集候選數(shù)法，這個(gè)策略在3個(gè)給定的同群組單元格（i1，j1）、（i2，j2）、（i3，j3）中以下條件可以使用 S（i1，j1）、S（i2，j2）、S（i3，j3）包含數(shù)字 k1、k2、k3且（i1，j1）、（i2，j2）、（i3，j3）所在的群組中其他的單元格的候選數(shù)集合并不包含數(shù)字k1、k2、k3，那么可以將除了 k1、k2、k3之外的數(shù)字在候選數(shù)集 S（i1，j1）、S（i2，j2）、S（i3，j3）中排除。

策略8：二鏈數(shù)刪減法，若一個(gè)值正好出現(xiàn)且只出現(xiàn)在某兩行的相同的兩列上，則這個(gè)數(shù)字就可以從這兩列上其他的單元格的候選數(shù)中刪除。 若一個(gè)值k正好出現(xiàn)且只出現(xiàn)在某兩列的相同的兩行上，則這個(gè)數(shù)字就可以從這兩行上的其他單元格的候選數(shù)中刪除。

策略 9：顯性四數(shù)集候選數(shù)法，這個(gè)策略使用情況如下：在 4 個(gè)同群組單元格（i1，j1）、（i2，j2）、（i3，j3）、（i4，j4）且這 4 個(gè)單元格的候選數(shù)集有且只有4個(gè)數(shù)字k1、k2、k3、k4，那么就能將這個(gè)群組的其他單元格候選數(shù)集中這4個(gè)數(shù)字 k1、k2、k3、k4全部刪減掉。

策略 10：隱性四數(shù)集候選數(shù)法，這個(gè)策略在4個(gè)給定的同群組單元格（i1，j1）、（i2，j2）、（i3，j3）、（i4，j4）中以下條件可以使用 S（i1，j1）、S（i2，j2）、S（i3，j3）、S（i4，j4）包含數(shù)字 k1、k2、k3、k4且（i1，j1）、（i2，j2）、（i3，j3）、（i4，j4） 所在的群組中其他的單元格的候選數(shù)集合并不包含數(shù)字 k1、k2、k3、k4， 那么可以將除了 k1、k2、k3、k4之外的數(shù)字在候選數(shù)集 S（i1，j1）、S（i2，j2）、S（i3，j3）、S（i4，j4）中排除。

策略 11：XY形態(tài)匹配法，若XY和YZ同在一個(gè)3×3區(qū)域但不同行（列）中，而XZ和XY在同一行（列），但在不同3×3區(qū)域中.那么在XY所在區(qū)塊中與XY所在行（列）交集空格中應(yīng)該刪除候選數(shù)Z，并且在XZ所在區(qū)塊與YZ所在行（列）交集的空格中應(yīng)該刪除候選數(shù)Z。（其中XY，YZ，XZ分別是三空格的候選數(shù)，并且這三空格沒有其他候選數(shù)）

策略 12：XYZ形態(tài)匹配法，若某3×3區(qū)域某空格候選數(shù)為XYZ，在該同3×3區(qū)域但不同列（行）的某空格候選數(shù)為YZ，且與XYZ所在空格同列（行）但不同3×3區(qū)域某空格候選數(shù)為XZ，那么XYZ所在3×3區(qū)域與 XZ所在列（行）的交集中的空格候選數(shù)不能為Z。

策略 13：三鏈數(shù)刪減法，如果某個(gè)數(shù)字k在某3列（行）中只出現(xiàn)在相同的3行（列）中，則將從這3行（列）上其他的候選數(shù)中刪除。

策略 14：WXYZ形態(tài)匹配法，若某3×3區(qū)域某空格候選數(shù)為WXYZ，在該同3×3區(qū)域但不同列（行）的某空格候選數(shù)為WZ，且與WXYZ所在空格同列（行）但不同3×3區(qū)域某兩個(gè)空格候選數(shù)為 XZ和YZ，那么 WXYZ所在3×3區(qū)域與XZ、YZ所在列（行）的交集中的空格候選數(shù)不能為Z。

策略 15：四鏈數(shù)刪減法，如果某個(gè)數(shù)字k在某4列（行）中只出現(xiàn)在相同的4行（列）中，則將從這四行（列）上其他的候選數(shù)中刪除。

策略16：試探法，若某個(gè)空格的候選數(shù)只有兩個(gè)時(shí)，進(jìn)行試探填寫其中一個(gè)候選數(shù)，若填寫成功則該試探成功，若導(dǎo)致矛盾則另外一個(gè)候選數(shù)應(yīng)填該空格。

以上介紹了常用的16數(shù)獨(dú)策略，但是這些策略之間的難易程度如何劃分呢，文中通過按照技術(shù)性和觀察候選數(shù)的個(gè)數(shù)，初略的將這16個(gè)策略分為6個(gè)難度級別：

級別1：顯性唯一候選數(shù)法、隱性唯一候選數(shù)法；

級別2：顯性對數(shù)候選數(shù)法、隱性對數(shù)候選數(shù)法、交叉排除法；

級別3：顯性三數(shù)集候選數(shù)法、隱性三數(shù)集候選數(shù)法、二鏈數(shù)刪減法、XY形態(tài)匹配法；

級別4：顯性四數(shù)集候選數(shù)法、隱性四數(shù)集候選數(shù)法、三鏈數(shù)刪減法、XYZ形態(tài)匹配法；

級別5：四鏈數(shù)刪減法、WXYZ形態(tài)匹配法；

級別6：試探法。

2 難度級別的劃分方法

文中研究：給定一個(gè)數(shù)獨(dú)謎題，如何定義以及確定它的難度？

筆者設(shè)計(jì)一個(gè)算法，讓這個(gè)算法根據(jù)一套分級方法能將給定的數(shù)獨(dú)謎題返回一個(gè)確定的“數(shù)值”代表它的抽象難度級別，定義數(shù)獨(dú)謎題的難度級別通過人們解題的平均步數(shù)來劃分。劃分前的假設(shè)：為了衡量數(shù)獨(dú)專家解決數(shù)獨(dú)謎題的步數(shù)，必須模型化解數(shù)獨(dú)謎題的步驟。對解題者有這樣的假設(shè)：策略能按照難度分級，數(shù)獨(dú)專家使用策略的原則是由易到難，文中使用的策略難度由第二部分已經(jīng)給出。這樣得出了數(shù)獨(dú)難度級別的步數(shù)法，這種方法需要考慮完成一個(gè)數(shù)獨(dú)謎題總共需要的步數(shù)，包括使用各個(gè)求解規(guī)則的步數(shù)。

劃分問題的轉(zhuǎn)化：當(dāng)使用某個(gè)規(guī)則求解數(shù)獨(dú)謎題時(shí)，滿足條件的嘗試會(huì)有很多次，但僅僅只有某些嘗試才會(huì)成功，而通常多數(shù)情況下的嘗試都會(huì)失敗。每次嘗試都會(huì)耗費(fèi)時(shí)間，因此每次嘗試都應(yīng)該考慮時(shí)間。把每次嘗試（不管其是否成功）都記作一步進(jìn)行累加，最后統(tǒng)計(jì)完成題目時(shí)總共經(jīng)歷的步數(shù)。一個(gè)數(shù)獨(dú)題目的難易程度就根據(jù)完成時(shí)所使用的總步數(shù)來確定。

人在使用某種策略求解數(shù)獨(dú)謎題時(shí)，其選擇符合條件的嘗試是隨機(jī)的，其是否成功也具有隨機(jī)性。這樣不同人使用該策略經(jīng)過的步數(shù)會(huì)不同，那么以什么作為參考呢？通常最好的辦法是使用不同人的平均值，在數(shù)學(xué)上就采用數(shù)學(xué)期望作為度量依據(jù)。

該問題可描述為：當(dāng)面對某一數(shù)獨(dú)題目，某策略可嘗試的總情形為s種，其中可成功求解的情形有r種。假定每種情形都等可能出現(xiàn)，求平均經(jīng)歷多少次可首次成功。

因此，始終有：

這樣，當(dāng)通過計(jì)算機(jī)搜索得使用某種層次策略的總次數(shù)r，可成功的次數(shù)s，就可以通過（6）式計(jì)算得到首次成功平均經(jīng)歷的次數(shù)。

接下來考慮另一種情形：面對一個(gè)數(shù)獨(dú)題目，采用某種層次策略，嘗試了所有s種情形都沒有成功，則記總步數(shù)T=s。

因此采用某個(gè)層次策略求解經(jīng)歷的總步數(shù)采用下式計(jì)算：

對任何一個(gè)級別的策略，計(jì)算使用該級別策略的總步數(shù)都采用（7）式計(jì)算。

設(shè)求解一個(gè)數(shù)獨(dú)總共使用了L個(gè)級別的策略，則求解該數(shù)獨(dú)的總步數(shù)為：

難度級別的劃分，可根據(jù)求解總步數(shù)（8）來確定。

難度級別的劃分，可根據(jù)求解總步數(shù)來確定。在文中將難度級別劃分為4個(gè)級別，則需要選定3個(gè)臨界值k1＜k2＜k3。當(dāng)步數(shù) d＜k1時(shí)，確定為第 1級；當(dāng)步數(shù)時(shí) k1≤d＜k2，確定為第 2級；當(dāng)步數(shù) k2≤d＜k3時(shí)，確定為第 3級；當(dāng)步數(shù) d≥k3時(shí)，確定為第4級。當(dāng)然劃分為其它難度級別也很容易變通，只要選定的不同的臨界值即可。

現(xiàn)在可以模仿人工智能策略求解數(shù)獨(dú)且生成難度了，具體步驟如下：

1）設(shè)定初始步數(shù)值d=0；

2）重復(fù)以下步驟直到數(shù)獨(dú)謎題解出或者數(shù)獨(dú)謎題無解：

①選擇當(dāng)前未使用過的最簡單的策略級別求解數(shù)獨(dú)，找出當(dāng)前級別成功的次數(shù)r，若r＞0，則繼續(xù)使用該級別的策略并使用公式（6）計(jì)算首次成功的期望值；若r=0，則跳到步驟②，并計(jì)算總經(jīng)歷的次數(shù)；

②使用比已經(jīng)使用過的策略級別高一級別的策略級別，找出此級別成功的次數(shù)r，若r＞0，則繼續(xù)使用該級別的策略并使用公式（6）計(jì)算首次成功的期望值；若r=0，則跳到步驟c，并計(jì)算總經(jīng)歷的次數(shù)；

③難度從低到高依次重新使用比b步驟策略級別難度低的策略級別，若其中有任何一個(gè)策略級別中，則跳回步驟a，否則使用比步驟b難度更高的策略級別。

3）根據(jù)上面的公式計(jì)算出總步數(shù)d，根據(jù)步數(shù)的區(qū)間輸出難度值。

3 臨界值的選定及合理性驗(yàn)證

嘗試文獻(xiàn)[7]中的4種難度（簡單，適中，困難，極難）的數(shù)獨(dú)謎題各100道，使用文中的人工智能求解算法求解他們，分別記錄下求解這4種不同難度的數(shù)獨(dú)謎題的步數(shù)，取平均值，得出以下4個(gè)數(shù)據(jù)：求解簡單難度的數(shù)獨(dú)謎題平均步數(shù)為10.64步、適中難度的步數(shù)為146.73步、困難難度的步數(shù)為317.12步、極難難度的步數(shù)為411.26步。

現(xiàn)在可以選定3個(gè)臨界值k1、k2、k3，取這4個(gè)數(shù)字中兩兩相鄰的平均值，即 k1=78.69、k2=231.93、k3=364.19，將數(shù)獨(dú)謎題的難度等級分成4個(gè)：

1） d∈[1， 78.69）時(shí)，數(shù)獨(dú)謎題難度為簡單；

2） d∈[93.69， 231.93）時(shí)，數(shù)獨(dú)謎題難度為適中；

3） d∈[281.93， 364.19）時(shí)，數(shù)獨(dú)謎題難度為困難；

4）d＞364.19時(shí)，數(shù)獨(dú)謎題難度為極難。

再次從文獻(xiàn)[7]中的4種難度（簡單，適中，困難，極難）中隨機(jī)抽取100道數(shù)獨(dú)謎題并對這400道數(shù)獨(dú)謎題使用人工智能的步數(shù)法，求出解出這些謎題的步數(shù)所在的區(qū)間，將4個(gè)難度等級分級方法重新分級。結(jié)果如表1所示。

表1 重新劃分難度級別的結(jié)果Tab.1 Result based on proposed difficulty metric mothod

進(jìn)一步計(jì)算得到Goodman-Kruskal相關(guān)系數(shù)

由于r已經(jīng)很大，因此我們有理由認(rèn)為我們的數(shù)獨(dú)謎題難度等級劃分原則與文獻(xiàn)[7]中數(shù)獨(dú)謎題數(shù)獨(dú)謎題難度等級劃分原則具有較強(qiáng)的相關(guān)性，證實(shí)了難度劃分原則的合理性。

4 結(jié) 論

模型化了求解數(shù)獨(dú)謎題的過程，將求解數(shù)獨(dú)謎題的過程拆分為16種策略6個(gè)級別由易到難的使用，根據(jù)使用策略的總步數(shù)將數(shù)獨(dú)謎題的難度分為成了簡單、適中、困難、極難這4個(gè)級別，并且通過文獻(xiàn)[7]中400道數(shù)獨(dú)謎題的數(shù)據(jù)分析，算出了Goodman-Kruskal相關(guān)系數(shù)為0.79，從而說明了我們的數(shù)獨(dú)謎題難度級別的劃分原則與文獻(xiàn)[6]中的劃分難度級別的原則具有很強(qiáng)的相關(guān)性，證明了這種分級方法的合理與有效。

當(dāng)然，這種分級方式也并不是沒有缺點(diǎn)，首先是策略的難易順序問題，本文按照技術(shù)性和觀察候選數(shù)的個(gè)數(shù)，這兩個(gè)原則來評判策略的難易程度，實(shí)際上，還有很多其他的難易程度標(biāo)準(zhǔn)，當(dāng)策略的順序使用出現(xiàn)不一致時(shí)，步數(shù)的差別會(huì)很大，這樣相應(yīng)的臨界值選擇又將發(fā)生變化，至于如何分配策略的順序使數(shù)獨(dú)謎題難度的分級更加合理，是下一步研究的問題。另外本文只將數(shù)獨(dú)謎題難度分成了4個(gè)，當(dāng)然可以分的更細(xì)，讓差異度更加明顯。

[1]雷蕾，沈?？?關(guān)于數(shù)獨(dú)問題的算法的設(shè)計(jì)與實(shí)現(xiàn) [J].電腦知識與技術(shù)，2007（2）：481-482.

LEI Lei，SHEN Fu-ke.The design and implementation of the algorithm aboutSudoku [J].ComputerKnowledgeand Technology，2007（2）：481-482.

[2]Gustavo S G，Palomino M.Solving Sudoku puzzles with rewriting rules[J].Electronic Notes in Theoretical Computer Science，2007（176）:79-93.

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

XIAO Hua-yong，TIAN Zheng，MA Lei.The design of the stepwise enumerative algorithm based on rule about Sudoku[J].Computer Engineering&Design，2010，31（5）:1035-1037.

[4]Moraglio A，Togelius J.Geometric particle swarm optimization for the Sudoku puzzle[J].GECCO，2007（5）:118-125.

[5]SUN Bao-chen，SUN Xi-wei， Yue，et al.A new algorithm for generating unique-solution Sudoku[C]//Fourth International Conference on Natural Computation，2008.

[6]Stuart A.Show Candidates[EB/OL]. （2012-01-03）[2012-02-18]http://www.sudokuwiki.org/sudoku.htm.

[7]Moritz L.Sudoku Garden[EB/OL]. （2012-02-16），[2012-02-18]http://sudokugarden.de/en.