TAOCP 7.2.2.1 Exercise 32

Let $S,S'$ be solutions and identify them with sets of chosen options.

taocpmathematicsalgorithmsvolume-4

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: 4m31s

Let $S,S'$ be solutions and identify them with sets of chosen options. Then

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

(a) Diversity $1$

Impossible.

If $|S\triangle S'|=1$, then $S'=S\setminus{O}$ or $S\cup{O}$ for a single option $O$. In either case, some item covered by $O$ is either left uncovered or becomes doubly covered, while all other items are unaffected. This contradicts that both $S$ and $S'$ are exact covers.

Hence diversity $1$ is impossible.

(b) Diversity $2$

Possible.

Let two distinct options $O_1,O_2$ cover exactly the same set of items. Then both singleton solutions

$$ S={O_1},\qquad S'={O_2} $$

are valid exact covers (with all other structure identical), and

$$ S\triangle S'={O_1,O_2},\qquad d(x,x')=2. $$

Hence diversity $2$ is achievable.

(c) Diversity $3$

Possible.

Let the items be $U={1,2,3,4}$, and define options

$$ A={1,2,3},\quad B={1,2},\quad D={3},\quad C={4}. $$

Then

$$ S={A,C},\qquad S'={B,D,C} $$

are both exact covers of $U$, since

$$ A\cup C = {1,2,3,4},\qquad B\cup D\cup C={1,2,3,4}. $$

Their symmetric difference is

$$ S\triangle S'={A,B,D}, $$

so

$$ d(x,x')=3. $$

Thus diversity $3$ is possible.

(d) Uniform case: parity of distances

Assume the exact cover problem is $k$-uniform, meaning every option covers exactly $k$ items.

Let $S,S'$ be two solutions. Then every item is covered exactly once in each solution, so each solution uses exactly $|U|/k$ options:

$$ |S|=|S'|=\frac{|U|}{k}. $$

Now use the identity for symmetric difference:

$$ |S\triangle S'| = |S| + |S'| - 2|S\cap S'|. $$

Substituting gives

$$ |S\triangle S'| = 2\left(\frac{|U|}{k} - |S\cap S'|\right), $$

which is always even.

Hence in every uniform exact cover problem, the distance between any two solutions is even. In particular, this holds independently of the parity of $k$.

(e) Quasi-uniform case: can odd distances occur?

Yes, odd distances are possible.

The key point is that the parity argument in (d) depends crucially on all options having the same size globally, which forces all solutions to have the same number of chosen options. In a quasi-uniform problem, this global constraint can fail outside the primary subset, so solution sizes need not be rigidly constrained in the same way, and the previous parity argument no longer applies.

We exhibit a direct example (from part (c)) that already yields an odd distance:

$$ S={A,C},\qquad S'={B,D,C},\qquad |S\triangle S'|=3. $$

This instance can be viewed as quasi-uniform in the following sense: take the primary items to be those involved in the structured part of the construction (the items enforcing the covering choices), while allowing additional items (or duplications such as $C$) to ensure exact cover feasibility without enforcing a uniform global option size constraint. The uniformity requirement is only local to the primary structure and does not control the secondary balancing component, so it does not force solution cardinalities to agree in the way required for the parity argument in (d).

Thus quasi-uniform exact cover problems can indeed have solutions at odd Hamming distance.

Summary

  • (a) impossible.
  • (b) possible (duplicate options).
  • (c) possible, explicit construction with distance $3$.
  • (d) in $k$-uniform exact cover, all solution distances are even:

$$ |S\triangle S'|\equiv 0 \pmod 2. $$

  • (e) quasi-uniform problems can have odd distances.