一、算法的主要流程
有了子集的矩阵表达形式之后，我们就可以用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}，现在，容易验证这是一个可行解，算法结束