一、问题描述
精确覆盖问题(Exact Cover Problem)，是指给定了一个全集S以及它的m个子集S1、S2、..Sm以后，要求出一组子集，使这组子集的并等于原来的全集S，且各子集两两不交。
例：设
S={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}
则子集组{B,D,F}就是S的一个精确覆盖，因为有B∪D∪F=S,
且B∩D= ,B∩F= ,D∩F= 。
精确覆盖问题的等价描述是：给定全集S，设其幂集(也就是所有子集的集合)为P(S),再给定一个P(S)的非空子集A,
要求出A的一个子集B(注意这个B的每个元素都是S的子集)，满足：对全集S中的任何一个元素x，它都恰好只属于B的某个元素而不属于B的其他元素。
二、子集的矩阵表达形式
设全集S有n个元素，给定m个子集以后，我们可以构造出一个m*n的矩阵A，这个矩阵的行标题为子集的名称，列标题是全集中的每个元素。
如果矩阵元素A(m,n)的值为1，则表示元素n属于子集m,为0时表示n不属于子集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。比如
{B,D,F}这个子集组所对应的3行所构成的新矩阵为
1 2 3 4 5 6 7
B 1 0 0 1 0 0 0
D 0 0 1 0 1 1 0
F 0 1 0 0 0 0 1
可以看出，在这个新矩阵中，每一列都有1，保证了子集的并等于全集，而每一列只有一个1，则意味着一个元素只出现在唯一的子集中，即各子集两两不交。
于是，{B,D,F}就是S的一个精确覆盖。这就是用矩阵描述精确覆盖问题的威力所在。