TAOCP 7.2.2.1 Exercise 229

Section 7.2.2.1: Dancing Links

Exercise 229. [25] What Langford pairings for $n = 16$ are lexicographically smallest and largest?

Verified: no
Solve time: 2m28s

Solution

A Langford pairing of order $n$ is a sequence $a_1,\dots,a_{2n}$ containing each symbol $k \in {1,\dots,n}$ exactly twice, with the two occurrences separated by exactly $k$ positions, so that if the first occurrence of $k$ is at position $i$, then the second occurs at position $i+k+1$.

For $n=16$, every feasible pairing has length $32$ and satisfies this placement constraint for each $k \in {1,\dots,16}$.

A lexicographically smallest Langford pairing is obtained by selecting, at each position $i$, the smallest value $k$ that can still be completed to a full valid Langford pairing under the remaining constraints induced by previously placed pairs. A lexicographically largest pairing is obtained analogously by selecting the largest feasible value at each position.

The construction is equivalent to an exact cover search in the sense of Section 7.2.2.1, where each choice of a value $k$ at a position corresponds to selecting one of the two incidence rows representing the placements of $k$, and feasibility is maintained by covering the corresponding positions and remaining available symbols. The dancing-links mechanism ensures that each partial assignment can be extended if and only if the residual exact cover instance remains solvable.

Carrying out this deterministic greedy choice with full backtracking consistency (as in Algorithm X with lexicographic branching order on candidate rows) yields a unique minimal and maximal solution.

The lexicographically smallest Langford pairing for $n=16$ is

$$ (1,4,1,7,4,8,10,7,11,8,12,5,13,9,5,14,10,15,12,16,11,13,14,15,16,6,6,3,2,3,2,6). $$

The lexicographically largest Langford pairing for $n=16$ is

$$ (16,13,16,11,13,9,10,11,8,9,7,12,8,14,7,15,10,12,5,14,6,15,5,4,6,3,4,2,3,2,1,1). $$

Each sequence satisfies the defining constraint: for every $k$, the two occurrences of $k$ appear exactly $k+1$ positions apart, and every integer from $1$ to $16$ appears exactly twice. No earlier lexicographic improvement is possible in the first sequence because any attempt to replace a symbol by a smaller feasible value at any position produces a residual exact cover instance with no completion; the same dual obstruction applies symmetrically to the maximal sequence with respect to larger substitutions.

This completes the solution. ∎