Exact Cover - Formal Definition

Formal Definition

Given a collection of subsets of a set X, an exact cover of X is a subcollection of that satisfies two conditions:

• The intersection of any two distinct subsets in is empty, i.e., the subsets in are pairwise disjoint. In other words, each element in X is contained in at most one subset in .
• The union of the subsets in is X, i.e., the subsets in cover X. In other words, each element in X is contained in at least one subset in .

In short, an exact cover is "exact" in the sense that each element in X is contained in exactly one subset in .

Equivalently, an exact cover of X is a subcollection of that partitions X.

For an exact cover of X to exist, it is necessary that:

• The union of the subsets in is X. In other words, each element in X is contained in at least one subset in .

If the empty set ∅ is contained in, then it makes no difference whether or not it is in any exact cover. Thus it is typical to assume that:

• The empty set is not in . In other words, each subset in contains at least one element.