The exact cover problem asks whether a finite set 
has an exact cover by a given collection
of its subsets. An exact cover is a subcollection 
in which every element
of 
occurs in exactly one member. Thus the members of 
are disjoint sets whose union is 
.
The decision problem is NP-complete (Karp 1972). The restricted exact cover by 3-sets problem,
abbreviated X3C, requires every member of 
to have cardinality 3 and is also NP-complete.
In the word game Connections, players divide 16 words into four groups of four words sharing a common theme within each group. Once the allowed four-word groups have been identified, the remaining grouping problem is an exact cover of the 16-word set by four such groups. Pairwise associations alone do not establish that four words share a common theme.
