本文同步分享於個人Blog → InformisTry-HankLee

前言

昨天我們介紹了如何使用Backtracking的方式來破解數獨，這個Backtracking的解法在網路上可以找到很多資料參考學習，然而今天要講的這個 Algorithm X 好像比較沒什麼人在提，至少我好像沒有找到關於這個Algorithm X的中文介紹，今天就主要介紹什麼是Algorithm X。

Algorithm X是什麼

Algorithm X是在2000年Stanford University的Knuth教授提出來的概念（參考資料3），雖然在這篇paper中主要介紹的是Dancing Links這種資料結構，但是Algorithm X可以說是Dancing Links的前身，而Algorithm X一種包含Backtracking概念且用遞迴設計的演算法，主要是用來解決Exact Cover Problem，而透過Algortihm X來處理exact cover problem的時候，是將資料變成陣列(Matrix)，並在每個位置以0和1的方式紀錄每一筆資料的資訊，然後目標是找出一個對於所有欄（Column)都是1的一個組合，大概的流程如下：

1. 如果Matrix中已經沒有任何的欄(Column)時，表示目前已經取得的結果是有效的，因此結束程序。
2. 反之，則選擇其中一個欄(Column)作為目標。（需要設定如何選擇目標欄）
3. 藉由這個欄來選擇一個欄位值為1的列(row) -- M(r, c) = 1。
4. 將這一列資料作為解答的一部分。
5. 根據這一列的資料中，哪些欄位的值為1，就將這些欄位的『欄』刪除；同時將這些欄刪除時，也會對應到一些其他的列，將這些列也刪除。
6. 反覆1~5步。

好吧～我知道還是很抽象，因此下面我們來解說一個範例。

上面提到的Dancing Links就是將Matrix轉換成一個Doubly Linked List的資料結構，有興趣的人可以Google看看，資料也滿多的，我之後有空再來補一篇介紹Dancing Links的內容，但可能就只會發布在我個人Blog上了。

Algorithm X的範例

首先，Algorithm X的概念下，需要先將資料轉換成一個Matrix的形式，轉換的過程如下(這個範例中我就不把空的欄位補0了，這樣看可能比較清楚地可以看到1的分布狀況)：

有了上面的Matrix，我們就可以利用這個Matrix去進行Algorithm X，目標就是找出一個組合可以包含1~7：

在這個範例中，我們如何決定要從哪一個欄(Column)來作為目標呢？答案就是：合計每個欄中的1的數目，從總合最小的欄開始。從GIF中可以看到，一開始選了Column 1作為目標，因為針對Column 1計算1的數量，合計為2，且順序靠前；而有包含1的列(row)有A和B，因為順序的關係，先選了Ａ，結果當下一個要選擇的Column(2)的時候，發現在Column 2中並沒有其值為1的欄位，這就表示目前的解答是無效的（因為解答絕對沒有辦法包含1~7），因此就會進行backtracking，才去選了B，因為選Ｂ的話，Ｂ本身就包含了１，４，因此其他有含1或4的Row都要跟著刪除，故Ａ和Ｃ就被刪除了，剩下DEF；在計算每個欄的1數量後，Column 5的1數目只有1，因此選擇Column 5為下一個目標，又唯一有包含Column 5的列為Ｄ，因此先將Ｄ加入解答中，再依據Ｄ包含的數字(3, 5, 6)來刪除其他的Row（Ｅ），結果只剩下了Ｆ，因此最後也把Ｆ加入了解答，此時Matrix為空，因此程式終止，取得最後的結果是B, D, F。

小結

Algorithm X會需要先將資料轉換成Matrix的型態，然後再從中選出每個欄都被包含進去的組合作為解答。

預告

明天就是我們這三十天系列文的最後一篇文章了，最後一天我們來介紹Algorithm X與數獨的關係。

References

1. Knuth's Algorithm X
2. Knuth, Donald E. (2000), "Dancing links", in Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.), Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare, Palgrave, pp. 187–214