一、問題描述
精確覆蓋問題(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的一個精確覆蓋。這就是用矩陣描述精確覆蓋問題的威力所在。
