另類DLX算法解sudoku游戲

摘要：sudoku是風靡全球的一款智力游戲。本文通過分析數據結構，算法思想，提出了一種與Knuth不同的DLX算法，給出了具體代碼實現（參考文獻3）。

關鍵詞：sudoku游戲 另類DLX 雙向十字鏈表 遞歸

1.sudoku簡介

2012年07月01日，媒體爆料芬蘭數學家因卡拉花三個月時間設計出世界上最難的數獨游戲。如下圖：

上圖中給出了21個數字和60個空格，要求填滿剩余的數字使得滿足三個條件：每一行有且僅有1，2，3，4，5，6，7，8，9九個數字；每一列有且僅有1，2，3，4，5，6，7，8，9九個數字。每一宮有且僅有1，2，3，4，5，6，7，8，9九個數字；上圖整個圖中有九個宮，每一宮有九個格子，三行三列。所有的9*9sudoku游戲，只是給出的數字和位置與上面的芬蘭題不同，要滿足的三個條件一樣。

2.回溯法及遞歸思想

當確定性技巧無法再填數，也無法刪除任一小格的任一候選數，就不得不嘗試，回溯法用遞歸函數滿足了這一要求。 一般情況都是將所有沒有填數的空格統計它們的候選數，后按候選數個數從小到大排列每個空格。最后以此順序來試探回溯，這稱為深度優先搜索DFS。

我在實際編程測試中屢次發現DFS的效率低于，自然順序搜索（在sudoku圖表從左到右，從上到下，對沒有填數的空格進行試探回溯）。一般認為空格越多，越難的用DFS，簡單的用自然搜索，但實踐證明再難的數獨用自然搜索更快。遞歸思想通過遞歸函數的遞歸調用實現，有的遞歸調用自己，有的遞歸調用的復雜，但總體趨勢是調用規模越來越小，接近錯誤和正確結果越來越近。遞歸函數一般可以和全局變量或者局部變量結合，和全局變量結合恢復函數會復雜些，和局部變量結合很多函數的參數會復雜些。遞歸和計算機的計算能力結合使得人們以前花一年解決的事情，一秒就能解決。本文用的是DFS。遞歸得到錯誤后要返回，遞歸是有內在的邏輯順序，不同的數據結構就會產生不同的遞歸邏輯。本文的數據結構采用雙向十字鏈表。

3.數據結構分析

Pro_k_col中的k表示不同的候選數，col代表不同的列（0——80） pro_col_k 和probable 是為了調試的方便而設置，調試期間易于觀察全局變量的變化。Pro_k_col[0][col]填寫col列所對應的空格或格子還有幾個候選數可填，初始值為9.pro_k_col[1][col]——pro_k_col[9][col]為1表示col對應的空格可以填相應的候選數，為0表示不能填。Pro_k_col[10][col]存儲col對應的空格所填的值。

int int_start[K*K*K*K]； 用來把從文件中讀取的題目存儲到int_start中。

試探回溯過程中會假設某個空格填某個數，隨之而來要把空格所在行列宮的那個數減去，must_add2是個全局變量，用于保存哪些格子刪除了某個數，以便恢復。

}； 此結構對應于上面數據結構圖中的一個節點。每個節點有四個指針，兩個數據圖中沒有給出。node* a[COL]； 在上圖網狀結構圖的第一行節點有COL+1個，除去頭節點有COL個，每個節點對應一個地址，分別存到a[]中。這樣可方便subtraction（ ）操作。

}graph； 此結構對應于上圖也就是那張網狀圖。當然上面的網狀圖會隨著sudoku題目的不同而不同，要形成上面的網狀圖（形象地稱為舞池）還要運行cregraph（）函數。graph G；

4.算法分析

sudoku題目有81個格子，每個格子都歸屬于3個小集體，行列宮。數據結構分析中的網狀圖只是一個很小規模問題的精確覆蓋問題，解決sudoku的網狀數據結構規模要比上面的網狀圖規模大，規律要強。sudoku對應的網狀結構圖有81*9行，81*3列。每一個格子可以填9個候選數，所以有81*9行。某一行被選擇隱含了sudoku中某個確定的格子填了確定的候選數，選了81行就正好覆蓋了sudoku所有的空格，題目也就解決了。每一個格子都同時歸屬于3個集體，0--80對應第0行到第8行的格子，81--161對應第0列到第8列的格子，162--242對應于第0宮到第8宮的格子。0--80個格子對應于sudoku81個格子，只要這81個列被覆蓋，后面的81*2自然也被覆蓋，所以第一行節點中的雙向鏈表僅僅指前面82個節點（包含頭節點）。至此，可以知道sudoku的網狀結構圖有著極強的規律，每一行有三個節點（每一個空格歸屬3個小集體），每一列有9個節點（每個空格可填就個候選數）。通過cregraph（）函數構造如數據結構分析中的網狀結構圖。因為sudoku的舞池有很強的規律，且對任一個sudoku都一樣，所以在做算法測試時，數據結構只需建立一次就夠。也因此在數據結構分析中，分析的都是全局變量，把它們設置為全局變量。

Subtraction（）函數是某個格子填了某候選數k后，對格子所在的行列宮中的其他格子減去它們的候選數k.

remove（）就是某個空格填過數后，空格對應的列要離開鏈表。

resume（）恢復刪除的列。

add（）根據全局變量must_add2恢復。

DFS（）每次試探選取最小候選數的格子，從1往9試探，本文DFS和全局變量配合。

本文的代碼解sudoku簡介耗時大概在400ms，knuth的dlx大概耗時2ms。一般數據結構是三維空間的結構體，算法是DFS耗時大概在3s。Knuth快的原因有兩個：他包含了隱含唯一數的情形，他的試探點更多有243個。同樣是DFS本文的數據結構要好于傳統的三維的結構體機構，理論上找不到任何解釋。

參考文獻：

[1].Donald E.knuth，Standford University.Dancing Links knuth原始論文.

[2]嚴蔚敏，吳偉明.數據結構（c語言版）[M].北京：清華大學出版社，2008：164--166

[3] http：//blog.csdn.net/for_every_one/article/details/8035796