Section 7.2.2.1: Dancing Links

Exercise 32. [**] [HM?] The solution to an exact cover problem (1) can be regarded as a binary vector $x = x_1 \ldots x_M$, with $x_k = [\text{option } k]$. The distance between two

solutions $x$ and $x'$ can then be defined as the Hamming distance $d(x, x') = \nu(x \oplus x')$, the number of places where $x$ and $x'$ differ. The diversity of the problem is the minimum distance between two of its solutions. (If there's at most one solution, the diversity is $\infty$.)

a) Is it possible to have diversity 1?

b) Is it possible to have diversity 2?

c) Is it possible to have diversity 3?

d) Prove that the distance between solutions of a uniform exact cover problem, that is, a problem having the same number of items in each option, is always even.

e) Most of the exact cover problems that arise in applications are at least quasi-uniform, in the sense that they have a nonempty subset of primary items such that the problem is uniform when restricted to only those items. (For example, every polyomino or polycube packing problem is quasi-uniform, because every option specifies exactly one piece name.) Can such problems have odd distances?

Verified: no
Solve time: 2m53s

---

Edit

Solution.

Let a solution be identified with the set of options that it contains. The Hamming distance between two solutions is the size of their symmetric difference:

[ d(x,x')=|S\triangle S'|. ]

(a)

Diversity (1) is impossible.

Suppose two solutions (S) and (S') differ in exactly one option. Without loss of generality, suppose that

[ S'=S\cup{A} ]

or

[ S'=S\setminus{A}. ]

In the second case, removing (A) from an exact cover leaves at least one item uncovered, because every option in an exact cover is responsible for covering each of its items. Thus the remaining options cannot form another exact cover.

In the first case, adding (A) to an exact cover causes every item of (A) to be covered twice, because all of those items were already covered by (S). Hence the new set of options cannot be an exact cover.

Therefore two exact covers cannot differ in exactly one option, and diversity (1) is impossible.

(b)

Diversity (2) is possible if options are regarded as distinct rows of the exact cover matrix, even when two rows specify the same set of items.

Take a problem with one item (a) and two distinct options

[ A={a},\qquad B={a}. ]

The two solutions are

[ S={A},\qquad S'={B}. ]

Their binary vectors, with respect to the two option coordinates, are

[ (1,0)\qquad\text{and}\qquad(0,1), ]

so

[ d(x,x')=2. ]

Thus diversity (2) is possible.

If one imposes the additional convention that duplicate options are forbidden, then diversity (2) cannot occur. Indeed, two solutions at distance (2) must differ by replacing one option (A) by one option (B). Since all other options are identical in the two solutions, (A) and (B) must cover exactly the same set of items. With no duplicate options allowed, this is impossible.

(c)

Diversity (3) is possible.

Consider the options

[ {a,b,c,d},\qquad {a,b},\qquad {c,d}. ]

There are two exact covers:

[ S={{a,b,c,d}} ]

and

[ S'={{a,b},{c,d}}. ]

With the three options listed above, their binary vectors are

[ (1,0,0) ]

and

[ (0,1,1). ]

These vectors differ in all three positions, so

[ d(x,x')=3. ]

Hence diversity (3) is possible.

(d)

Suppose the exact cover problem is uniform, with every option containing exactly (r) items. Let the total number of items be (n).

Every solution must cover all (n) items exactly once. Since every selected option covers exactly (r) items, every solution contains exactly

[ \frac nr ]

options.

Let (S) and (S') be two solutions. Their distance is

|S|+|S'|-2|S\cap S'|. ]

Because both solutions have the same number of options,

[ |S|=|S'|=\frac nr, ]

and therefore

2\frac nr-2|S\cap S'|. ]

Both terms on the right are even integers, so

[ |S\triangle S'|\equiv 0\pmod 2. ]

Thus the distance between any two solutions of a uniform exact cover problem is always even.

(e)

Now suppose the problem is quasi-uniform. Let (P) be a nonempty set of primary items such that the restriction of every option to (P) has the same size, say (r).

Let the number of primary items be (n). Every solution must cover the primary items exactly once. Since each selected option covers exactly (r) primary items, every solution contains exactly

[ \frac nr ]

options.

Therefore, for any two solutions (S) and (S'),

|S\triangle S'|

|S|+|S'|-2|S\cap S'|. ]

The number of selected options in each solution is the same, so

[ |S|=|S'|=\frac nr. ]

Consequently,

2\frac nr-2|S\cap S'|, ]

which is even.

Hence odd distances cannot occur in quasi-uniform exact cover problems. In particular, all exact cover problems arising from such applications have only even distances between their solutions.