數獨謎題難度級別劃分的步數法研究

程 曦，肖華勇

（西北工業大學 理學院，陜西 西安 710129）

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

一個數獨謎題通過給定的一定格子的數字，通過這些初始數字確保能產生的唯一填滿數字的棋盤，把填滿數字的棋盤稱為解決數獨謎題的一種解題方法。數獨謎題游戲的目標是通過初始給定的格子中數字，找出唯一的解題方法。

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

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

1 常用數獨謎題策略

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

圖1 數獨謎題的標號Fig.1 Sudoku puzzle’s mark

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

策略16：試探法，若某個空格的候選數只有兩個時，進行試探填寫其中一個候選數，若填寫成功則該試探成功，若導致矛盾則另外一個候選數應填該空格。

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

級別1：顯性唯一候選數法、隱性唯一候選數法；

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

級別3：顯性三數集候選數法、隱性三數集候選數法、二鏈數刪減法、XY形態匹配法；

級別4：顯性四數集候選數法、隱性四數集候選數法、三鏈數刪減法、XYZ形態匹配法；

級別5：四鏈數刪減法、WXYZ形態匹配法；

級別6：試探法。

2 難度級別的劃分方法

文中研究：給定一個數獨謎題，如何定義以及確定它的難度？

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

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

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

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

因此，始終有：

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

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

因此采用某個層次策略求解經歷的總步數采用下式計算：

對任何一個級別的策略，計算使用該級別策略的總步數都采用（7）式計算。

設求解一個數獨總共使用了L個級別的策略，則求解該數獨的總步數為：

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

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

現在可以模仿人工智能策略求解數獨且生成難度了，具體步驟如下：

1）設定初始步數值d=0；

2）重復以下步驟直到數獨謎題解出或者數獨謎題無解：

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

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

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

3）根據上面的公式計算出總步數d，根據步數的區間輸出難度值。

3 臨界值的選定及合理性驗證

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

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

1） d∈[1， 78.69）時，數獨謎題難度為簡單；

2） d∈[93.69， 231.93）時，數獨謎題難度為適中；

3） d∈[281.93， 364.19）時，數獨謎題難度為困難；

4）d＞364.19時，數獨謎題難度為極難。

再次從文獻[7]中的4種難度（簡單，適中，困難，極難）中隨機抽取100道數獨謎題并對這400道數獨謎題使用人工智能的步數法，求出解出這些謎題的步數所在的區間，將4個難度等級分級方法重新分級。結果如表1所示。

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

進一步計算得到Goodman-Kruskal相關系數

由于r已經很大，因此我們有理由認為我們的數獨謎題難度等級劃分原則與文獻[7]中數獨謎題數獨謎題難度等級劃分原則具有較強的相關性，證實了難度劃分原則的合理性。

4 結 論

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

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

[1]雷蕾，沈福可.關于數獨問題的算法的設計與實現 [J].電腦知識與技術，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]肖華勇，田錚，馬雷.數獨基于規則的逐步枚舉算法設計[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.