TAOCP 7.2.2.1 Exercise 27

Section 7.2.2.1: Dancing Links

Exercise 27. [22] Introduce secondary items cleverly into the options (a6), so that only planar solutions to Langford's problem are obtained. (See exercise 7.5–8.)

Verified: yes
Solve time: 1m17s

Solution

Let Langford’s problem be represented in the usual exact-cover form of Section 7.5–8, where each option represents a placement of a pair of equal integers $k$ into positions $i$ and $i+k+1$ of a length $2n$ sequence. Thus an option has the form

$$ (i,k)\quad\text{meaning the pair }k\text{ occupies positions }i\text{ and }i+k+1, $$

subject to $1 \le i < i+k+1 \le 2n$.

In the standard formulation (a6), the primary items are the position items $1,2,\dots,2n$, each required to be covered exactly once, together with the symbol-choice constraints ensuring that each value $k$ is used exactly twice in the required separated form.

A solution of Langford’s problem can be represented geometrically by arcs connecting the two occurrences of each value $k$ in the linear order $1,\dots,2n$. A solution is planar precisely when these arcs do not cross, meaning that there do not exist two chosen options $(i,k)$ and $(j,\ell)$ with

$$ i < j < i+k+1 < j+\ell+1. $$

The modification required is to augment the option system (a6) with secondary items that forbid crossings while preserving the exact-cover structure for valid configurations.

For each ordered pair of distinct options $A=(i,k)$ and $B=(j,\ell)$ such that the corresponding arcs cross in the sense

$$ i < j < i+k+1 < j+\ell+1 \quad \text{or} \quad j < i < j+\ell+1 < i+k+1, $$

introduce a secondary item denoted $C_{A,B}$ (with $C_{A,B}=C_{B,A}$). These secondary items are not required items in the exact-cover sense; they are secondary items in the sense of DLX, meaning they may be covered at most once and are not part of the requirement that all primary items must be covered.

For each option $A$, define the set of secondary items attached to $A$ by

$$ S(A) = {, C_{A,B} \mid B \text{ is an option that crosses } A ,}. $$

Then extend each option $A$ in (a6) by adjoining all secondary items in $S(A)$.

The primary items remain exactly the position constraints and symbol constraints from the original Langford encoding. The secondary items are appended without changing the requirement that primary items must be covered exactly once.

If two options $A$ and $B$ cross, then both contain the secondary item $C_{A,B}$. Therefore any attempt to include both $A$ and $B$ in a partial solution would require covering $C_{A,B}$ twice. In the dancing-links interpretation, this is impossible, since each item node can be removed at most once from the vertical list, and a second attempt to cover it finds no available occurrence. Thus any exact-cover solution automatically excludes every pair of crossing options.

Conversely, if a set of Langford options contains no crossing pair, then no secondary item $C_{A,B}$ is ever duplicated, since every such item corresponds only to a forbidden crossing pair. Hence all secondary items remain covered at most once, and no conflict arises beyond the primary exact-cover constraints. Therefore every noncrossing Langford solution extends to a valid solution of the modified system.

The resulting exact-cover instance has the property that its solutions are exactly those Langford solutions in which no two arcs cross, hence precisely the planar solutions.

This completes the construction. ∎