數獨求解 Java 實現三部曲 - 第一部 - 精確覆蓋問題 (Exact cover) 與 X演算法 (AlgorithmX)

最近在玩數獨 (Sodoku)，在找相關資料時讀到了跟數獨有關的數學問題：
精確覆蓋問題 (Exact cover) 和它的其中一個蠻不錯的解法：AlgorithmX 
還有實現 ALogrithm X 的 Dancing Links (DLX) 程式解法，
可以用來解數獨、8皇后問題(8 Queens, Puzzle)等問題，
並且能夠以程式設計並執行 AlgorithmX, Dancing Links (DLX) 來求解，
這裡特別紀錄下我學習到的東西。

因內容比較多，所以我分成三篇：

數獨求解 Java 實現三部曲：

1. 數獨求解 Java 實現三部曲 - 第一部 - 精確覆蓋問題 (Exact cover) 與 X演算法 (AlgorithmX)
2. 數獨求解 Java 實現三部曲 - 第二部 -  舞蹈鏈 (Dancing Links) (DLX)  - 可用來解數獨、8皇后問題(8 Queens, Puzzle) 等問題
3. 數獨求解 Java 實現三部曲 - 第三部 -  數獨求解器的 Java 實現

在這篇文中主要會先講精確覆蓋問題和 AlgorithmX，
如何用 Dancing Linkx (DLX) 來實現 Algorithm X 及求解數獨的部份會在下一篇及之後文章中介紹。

首先先了解什麼是精確覆蓋，
可以參考 精確覆蓋問題 - 維基百科，自由的百科全書。
在一個 X 集合中，X 的若干子集的集合為 S，如果可以找到一個  S 的子集 S' (可能不只一個)，
滿足 X 的每一個元素都只在 S' 中出現一次，即為一個 X /的精確覆蓋解。

也可以換另一個說法，
滿足以下條件的集合為一個精確覆蓋：

1. S' 中任意兩個集合交集為空集合，所以 X 中的元素只會出現在 S' 中的某一個集合中並且只出現最多一次。
2. S' 中集合的全集為X，所以 X 中的元素在 S' 中會出現最少一次。
3. 如上兩點，即 X 中的元素在 S' 中會出現恰好一次。

例如：

X = {1, 2, 3, 4, 5}

S = {S1, S2, S3, S4, S5} 為一個 X 的若干子集的集合，

其中 S1, S2, S3, S4, S5 各是 X 的子集

S1 = {1, 3, 5}

S2 = {2, 4}

S3 = {1, 2, 5}

S4 = {3, 4}

S5 = {}

如果忽略空集合 S5，我們可以找到兩個 X 的精確覆蓋解 S1' 和 S2'：

S1' = {S1, S2}

S2' = {S3, S4}

S1' 為解的原因為 S1 = {1, 3, 5} 和 S2 = {2, 4} 的併集為 X = {1, 2, 3, 4, 5}，且 X 中的各元素只在 S1 和 S2 中出現一次 ，S2' 同理也為另一個解。

精確覆蓋問題就是說：
我們現在有一組 X = {X1, X2, ...} 集合 和 X 的若干子集合組成的集合 S = {S1, S2, ...}，
我們要如何找出 X 的 精確覆蓋 S' = {Sx, Sy, ...} (Sx, Sy 為 S 中的集合可能不只一個，也有可能沒有)。

而 X演算法 (Algorithm X)  為一個精確問題求解的一個演算法，
可以參考 X演算法 - 維基百科，自由的百科全書。

AlgorithmX 也是一種深度優先算法，具體的步驟如下 (用實際例子舉例做一遍)：

假設 X = {1, 2, 3, 4, 5}

S = {S1, S2, S3, S4, S5}

S1 = {1, 3, 5}

S2 = {2}

S3 = {2, 5}

S4 = {2, 4}

S5 = {1, 3, 4}

用矩陣 A(r, c)  來表示可以表示如下 , r 是 row 編號，c 是 column 編號：

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

1. 如果沒有可選擇的 column，即為找到一個解，否則繼續。。

2. 選擇一個 column c (實務上通常會選擇 1 次數最少的 column， 比較有可能更早找到解 ，例如範例是 column1 有 2 個 1、column 2 有 3 個 1，所以先選 column 1  )。

3. 從選定的 column 上選一個 A(r, c) = 1 的 row  r 做為解中的一個集合，如果此時找不到可選的 row (即代表沒有 row 可以滿足此 column)，即代表無解，可能之前的 row 選擇有誤，這時就要把已作為解中的上一個選定的 row 從解中移掉，還原上次刪掉的 row 和 column 到 A 中並選擇其他 row 做為解中的一個集合繼續下一步驟。

4. 對於選定的 row 上的每一個 A(r, j) = 1 的 column j，從 A 中刪掉每一個 A(i, j) = 1 的 row i，最後再刪掉 column j。
    用 sudo code  來寫如下：
    For each column j such that A_r, j = 1,
      for each row i such that A_i, j = 1,
         delete row i from matrix A.
    delete column j from matrix A.
5. 遞迴地執行此演算法。.

我們下面來實際做一次演算法，假設解是 S'：
1. 先選擇 column 1，把它標記起來。

2. 選擇 S1 row 作為解的一個集合，把做為解中之一的集合  S1 用標記起來，目前 S' = {S1}。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

3. 對 S1 的所有是 1 的 column 標計起來 (即 column 1, column 3 和 column 5)，之後要把它們從 A 中移掉，代表我們已經找到符合 X 中 1, 3, 5 的解。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

4. 被標記的 column 代表我們已找到的符合 X 子集合的 column，此列就是 column 1、 column 3 和 column 5，其他 row 如果第 column 1, 3, 5 是 1 的話我們就要把它們從可能的解侯選中排除掉，所以我們找出被標記的 column 上是 1 的 row 將它們標記起來，此列就是 S3 和 S5。

把 S1 和標計成紅色的 S3 (row 3), S5 (row 5), column 1, column3 和 column 5 移掉 (這裡不真得從畫面上移掉比較好看出變化，畫面上有標記的部份可看做已從 A 中移掉 )。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

5. 用跟上述一樣的方法，這次為了演示選錯 row 的狀況，我們選 column 2 來找解 (通常我們會選 1 比較少的 column 4，因為 column 2 還有兩個 1，column 4 只有剩一個 1)，然後選擇 S2 為解中的集合，此時 S = {S1, S2}。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

7. 把 S2 row 中的 1 對應到的 column 中為 1 的 row 刪掉，也就是 S4 row 4。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

8. 此時可以發現能選的 column 只剩下 column 4 了，但此時已沒有可選的 row 了，
也就是沒有 row 可以滿足 column 4，代表此時無解，可能上一步驟選的 row (即 S2 row 2) 有錯，此時我們可以把 S2 中從已找到的解中移掉，讓 S' = {S1}，並把因選了 S2 移掉的 row 和 column 還原。

這次我們改選 S4 為解中的集合，此時 S' = {S1, S4}，用一樣的方法把 S4 上為 1 的 column 2, column 4 上的有 1 的 row (即 S2 row 2) 移掉。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

9. 此時 A 中已經沒有可選的 column 了，即代表我們已經找到了一個解了，就是 S' = {S1, S4}。

10. 如果還想再找到其他解，我們可以再一路往回還原所選的 row, column 和因選了 row, column 而被移除的 row, column，我們一路回到第 3 步驟，不選 column 1，這次改選 column 2，這裡我們假設已經試過 S2 不是解的答案了，然後接下來選擇 S3，此時 S' = {S3}。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

11. 一樣的我們把 S3 上的 1 對應到的 column 2, column 5 上，為 1 的 row S1, S2, S4 移掉。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

12. 接下我們選擇 column 1，再選擇 column 1 上為 1 的 row S5 做為，此時 S' = {S3, S5}，接著把 S5 上為 1 的 column 1, column 3, column 4 移掉，此時我們發現已經沒有 column 可選了，代表 X 都已經被滿足了，即我們得到了第二個解： S' = {S3, S5}。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

了解了如何用 Algorithm X 解決精確覆問題後，在下篇文章中，我會介紹如果用 Dancing Liks (DLX) 去實現及 Java 程式範例。

參考資料：

1. 精確覆蓋問題 - 維基百科，自由的百科全書
2. X演算法 - 維基百科，自由的百科全書
3. Dancing Links - OI Wiki