舞蹈鏈演算法

❶ 動手實現Dancing Links

前幾天提到 舞蹈鏈演算法 ，這兩天有時間就動手實現了一下。

舞蹈鏈（Dancing links）實際上是一種數據結構，可以用來實現 X演算法，以解決精確覆蓋問題。

什麼是精確覆蓋（Exact Cover）問題呢？維基網路上對精確覆蓋的定義如下：在一個全集 X 中若乾子集的集合為 S。S* 是 S 的一個子集，當且僅當 X 中的每一個元素在 S* 中恰好出現一次時，S* 稱之為一個精確覆蓋。在計算機科學中，精確覆蓋問題指找出這樣的一種覆蓋，或證明其不存在。這是一個NP-完全問題。

例如，S = {A，B，C，D，E，F} 是全集 X = {1，2，3，4，5，6，7} 的一個子集的集合，其中：
A = {1, 4, 7}
B = {1, 4}
C = {4, 5, 7}
D = {3, 5, 6}
E = {2, 3, 6, 7}
F = {2, 7}
那麼，S 的一個子集 S* = {B, D, F} 是 X 的一個精確覆蓋，因為 X 中的每個元素恰好在 S* 中出現了一次。

可以用 0-1 矩陣來表示精確覆蓋問題。我們用矩陣的每行表示 S 的一個元素，也就是 X 的一個子集；用矩陣的每列表示 X 的一個元素。矩陣中的 1 代表這一列的元素存在於這一行對應的子集中，0 代表不存在。那麼精確覆蓋問題可以轉化成求出矩陣若干行的集合，使得集合中的每一列恰明滑好都有一個 1。

比如前面的問題可以用矩陣的形式表示成

那麼選擇紅色的 B，D，F 能滿足每列都恰好包含一個 1。

可以用 Knuth 提出的 X演算法 來解決精確覆蓋問題。X演算法是一個非確定性的深度優先回溯演算法。它的具體步驟如下：

讓我們用 X演算法 解決上面的精確覆蓋問題。

首先，當前矩陣不為空，演算法繼續進行。那麼先選擇 1 最少的一列。因為 1，2，3，5，6 列都只有 2 個 1，因此我們隨便選擇 1 個，比如第 1 列。

行 A 和 B 都含有 1，因此要在這兩行中進行選擇。

第 0 層也沒有其他可以選擇的行，演算法終止。

以上就是 X 演算法的執行過程。Knuth 提出 X 演算法主要是為了說明舞蹈鏈的作用，他發現用舞蹈鏈來執行 X 演算法效率特別高。那麼什麼是舞蹈鏈呢？它是基於雙向鏈表的一種數據結構。

讓我們先來看看雙向鏈表：

上圖是一個簡單的雙向鏈表，每個節點有兩個指針，分別指向自己的前驅和後繼節點。那麼昌櫻如果我們想把其中一個節點，比如 B 從鏈表中刪掉，只需要執行下面的操作：

注意：此時雖然 B 從鏈表中移除了，但它的兩個指針依然保持不變，還是指向之前的前驅和後繼節點。

因此，如果我想把 B 再添加到鏈表原來的位置上，此時並不需要修改 B 的指針，只需要再把 B 的前驅和後繼節點的指針恢復就可以了：

理解了這一點之後，讓我們再來看看舞蹈鏈的結構是怎麼樣的：

上面這個圖是一個舞蹈鏈的結構，描述的是前面 X 演算法中用到的矩陣。它由幾部分構成：

最上面的藍色部分是一個水平的環狀雙向鏈表。最左邊是頭節點，它是整個數據結構的根節點。其餘是耐槐叢列頭節點，每個代表矩陣中的一列。

每一列又是一個縱向的環狀雙向鏈表。除了最上面的列頭節點，其他的每個節點都代表前面的矩陣中的一個 1。這實際上是一個稀疏矩陣，為了優化存儲和效率，只保留了值為 1 的節點，把每個節點按順序保存到數組中。最早的 Dancing Links 演算法，也就是 Knuth 在 2000 年發表的論文中，下面的每一行也都是一個雙向鏈表。但後來他發現每一行在演算法執行過程中實際上不會發生變化，因此他把水平的雙向鏈表取消了，只保留了最頂上的列頭節點之間的水平雙向鏈表。下面的每一行之間的前後節點可以直接通過數組的索引得到。兩邊是Space節點，用來標記一行的開始和結束。

每個普通節點 A 都包含 4 個 欄位，A.up 和 A.down 代表雙向鏈表的兩個指針，分別指向 A 上面和下面的節點。還有一個 A.col ，指向 A 所在列的頭節點，需要根據這個欄位定位到節點所在的列。另外還有一個 A.row，主要是方便在遞歸的過程中緩存當前的解。

列頭節點還要再多幾個欄位，left 和 right 分別指向水平雙向鏈表的左節點和右節點。另外還有一個 count 欄位，代表這一列當前一共有幾個元素。X 演算法的第 2 步，選擇 1 最少的列時會用到這個欄位。

理解了舞蹈鏈的數據結構之後，我們再來看看是怎樣用舞蹈鏈來實現 X 演算法的。這部分演算法很精妙，也是舞蹈鏈這個名字的來由，通過對鏈表上的節點反復刪除和插入實現了遞歸的回溯，就好像一個個鏈表在舞台上翩翩起舞一樣。

具體的演算法實現可以參照 Knuth 的論文，我們還是用圖的方式來說明一下。

以上就是舞蹈鏈演算法的執行過程。

❷ 有沒有好的演算法編程解決數獨的正確答案

有啊，而且各種語言基本都有。
其中比較經典的舞蹈鏈演算法對常見的標准數獨來說簡直就是秒解！甚至每秒解幾千個幾萬個。