Exact Cover

The exact cover problem can be stated as follows:

You are given a set and a collection of subsets of the given set. An exact cover is a subcollection of the given collection such that each element in the given set belongs to exactly one subset of the subcollection. Decide whether there exists an exact cover.

For example, you are given the set U = {1, 2, 3, 4}. For the collection of subsets of U, you are given {1, 3}, {2, 4}, {1, 2, 4}. Does there exist an exact cover?

In this case, there does exist an exact cover. Namely, the subcollection {1, 3}, {2, 4} is an exact cover. Each element in U belongs to exactly one subset of that subcollection.

In contrast, the subcollection {1, 3}, {1, 2, 4} is not an exact cover, because 1 belongs to more than one subset of that subcollection. For a subcollection to be an exact cover, each element in U must belong to exactly one subset of the subcollection.

Of course, the subcollection {1, 3} is not an exact cover, either. In no sense does {1, 3} cover {1, 2, 3, 4}.

The exact cover problem is a decision problem. So, the task is to decide whether an exact cover exists. A related task is the problem of finding exact covers. The two tasks are obviously related, because if you find an exact cover, then you know that one exists.

The problem of finding Langford strings can be generalized to the problem of finding exact covers. For example, let the order of the Langford string be 3. Then U = {1, 2, 3, 4, 5, 6, A, B, C}, and the collection of subsets of U is

{1, 3, A}, {2, 4, A}, {3, 5, A}, {4, 6, A},
{1, 4, B}, {2, 5, B}, {3, 6, B},
{1, 5, C}, {2, 6, C}.

The elements of a subset correspond to the positions of a letter in a presumptive Langford string. So, {1, 3, A} means that “A” occurs in the first and third positions in a string.

You can see that the subcollection {3, 5, A}, {1, 4, B}, {2, 6, C} and the subcollection {2, 4, A}, {3, 6, B}, {1, 5, C} are exact covers of U. And, indeed, “BCABAC” and “CABACB” are the Langford strings of order 3.

(As an aside, I want to point out that the exact cover problem is NP-complete. As you can see, it is easy to verify whether a subcollection is an exact cover. However, for an arbitrary set and an arbitrary collection of subsets, it is as difficult to decide whether an exact cover exists as it is solve any other NP problem.)

In order to illustrate a clever data structure, Donald Knuth presented an algorithm that finds all of the exact covers of a given set.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s