一、算法的主要流程
有了子集的矩陣表達形式之後，我們就可以用Knuth發明的X算法來求出精確覆蓋問題的解。（如果你在研究算法，但是沒聽過knuth的名字並且你又不是計算機的天才的話，請在閱讀完本文後立刻去拜讀Knuth的大作，呵呵）。
這個遞歸算法（設算法函數的名字為search）的主要流程是
1、設置一個子集編號集合S,用來存儲本次得到的部分解。開始時S為空。
2、判斷當前矩陣M是否為空，為空的話表示已經沒有待處理子集和元素，此時求解成功，返回true.
3、判斷當前矩陣M中是否有全1的行，有的話則則該行是一個當前的可行解，將其加入到S中,函數返回true。
4、判斷當前矩陣M中是否有全0的列，有的話則代表該列的所對應的元素一定不在剩下的所有子集裡，此時當前問題無解，函數返回false。
5、從M中找出含1個數最少的列，設選出這個的列號為c。如果有多個列的含1個數都相同，則取最左邊的那一列。
6、找出所有滿足M(r,c)=1的行. 即所有含元素c的子集。 用一個循環來處理這些行，當處理完某一行之後如果得到了一個可行解，則算法結束。具體的處理過程是
a、設當前待處理的行為r
b、找出本行所有為1的列，然後用一個循環處理這些列，循環體的處理過程是
b.1 設j為當前待處理的列號
b.2 遍歷矩陣M,將所有滿足M(i,j)=1的行i從M中刪除， 這一步的目的將所有和子集r有共同元素的子集從矩陣中刪掉。
b.3 將列j從矩陣M中刪除， 這意味著本列所對應的元素已經被處理過了，已經屬於A的並集了。以後再加入的子集中不需要再含有這些元素了。
總體來說，步驟b的目的就是在矩陣中刪除所有和r相交的行和列，得到一個新的子矩陣M'。
c. 對新的矩陣M'，繼續調用函數search(這是一個遞歸過程),設遞歸調用的結果為flag。
d.如果上一步得到的flag為真，意味著得到了一個可行解，此時在上一步得到的局部可行解s'中加入行號r,就是本次函數調用的可行解。本次函數調用結束,函數返回true。
7、當步驟6中的循環結束後仍未找到一個可行解，則函數結束，返回false.
二、一個運行實例
對我們所舉的例子，矩陣M的初始狀態為
1 2 3 4 5 6 7
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1
1、找出含1個數最少的列，即找出在子集中出現次數最少的那個元素。顯然，元素1、2、3、5、6的總出現次數都為2，而我們是從左到右遍歷的，故這一步的選擇列號為1.
2、找出所有含有元素1的子集，即A和B，也就是第一行和第二行。現在S={}
3、我們先考慮子集A、先嘗試將子集A加入到解集S中。現在S={A},
4、現在將所有和A有交集的子集從矩陣中刪除。具體做法是，子集A對應3個列1,4,7。那麼從矩陣中把所有在這3列中含1的行刪掉。
比如對第1列，含1的行有A,B；對第4列，含1的行有A,B,C；對第7列，含1的行有A,C,E,F。 因此刪除的就是A 、B、 C、 E 、F等5行
5、刪除所有和A有交集的列，即第1、4、7列。
現在矩陣的狀態為
2 3 5 6
D 0 1 1 1
6、由於現在的矩陣只剩下1行，且第2列為0，這意味著，當前解S={A,D}的並集中肯定不含元素2，
所以S={A,D}不是一個可行解，因此要回退到第2步的狀態，然後從子集B開始求解
7、回退到步驟2將子集B加入到S中,S={B}
8、將所有和B有交集的行和列從矩陣中刪除。即刪除行A,B,C和列1,4，刪除之後，矩陣M的新狀態為
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
9、找出目前M中含1最少的列，顯然這一步得到的列號為5.
10、和第5列有交集的行（即含元素5的子集）只有D。
11、將D加入到解集中，現在S={B,D}
12、刪除所有和D相交的行和列，於是刪除了列3,5,6和行D、E，現在矩陣的狀態為
2 7
F 1 1
13、由於現在剩下的是全1行，因此把F加入到解集中，S={B,D,F}，現在，容易驗證這是一個可行解，算法結束
