TAOCP 7.2.2.1 Exercise 93
Let a configuration for period $p$ consist of $3p$ words placed on a toroidal arrangement of $p$ rows and $3$ word-positions per row, with wraparound in both directions, such that each of the $3p$ wor...
Section 7.2.2.1: Dancing Links
Exercise 93. [22] [22] Another periodic arrangement of $3p$ words, perhaps even nicer than that of exercise 92 and illustrated here for $p = 3$, lets us read them diagonally up or down, as well as across. What are the best five-letter examples of this variety, for $1 \le p \le 10$? (Notice that there is 2-way symmetry.)
$$\begin{array}{ccccccc} 1 & 1 & 1 & 7 & 1 & 1 & 1 \ 1 & 1 & 1 & 6 & 1 & 1 & 1 \ 1 & 1 & 1 & 5 & 1 & 1 & 1 \ 1 & 1 & 1 & 4 & 1 & 1 & 1 \ 1 & 1 & 1 & 3 & 1 & 1 & 1 \ 1 & 1 & 1 & 2 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 & 1 & 1 & 1 \ \end{array}$$
Verified: no
Solve time: 1m05s
Solution
Let a configuration for period $p$ consist of $3p$ words placed on a toroidal arrangement of $p$ rows and $3$ word-positions per row, with wraparound in both directions, such that each of the $3p$ words appears exactly once in each of the three reading directions: horizontally, and along the two diagonals of slope $+1$ and $-1$ (modulo the periodic boundary). The condition that the arrangement can be read “diagonally up or down, as well as across” forces each of these three directional readings to form a partition of the same multiset of $3p$ words, and the stated “two-way symmetry” identifies reversal of the construction with itself, so each admissible configuration is invariant under exchanging the two diagonal directions.
Let $W$ be a fixed word list. For each $p$, define the universe of items as follows. There are $3p$ position-items $(i,j)$ with $0 \le i < p$ and $j \in {0,1,2}$, and there are $3p$ word-items, one for each selected word occurrence. Each placement of a word $w \in W$ contributes one option, and that option consists of the word-item $w$ together with the three position-items corresponding to its horizontal placement and the two diagonal placements determined by toroidal shifts.
More precisely, fixing a position $(i,j)$ as the leftmost occurrence of a word in the horizontal direction determines the three occurrences of that word across the three directions by rigid shifts:
the horizontal placement occupies $(i,0),(i,1),(i,2)$ up to cyclic relabeling of columns, while the diagonal constraints force simultaneous occupancy of the three slope-$+1$ and slope-$-1$ diagonals passing through these cells. Thus each word induces exactly three incidences, one per direction, and the exact-cover condition enforces that every position-item and every word-item is covered exactly once.
The “diagonal readability” requirement introduces a second layer of exact covering: if a word occupies a cell in a horizontal row, then its two diagonal neighbors are determined uniquely, so each admissible placement corresponds to a closed 3-direction cycle in the incidence graph. The symmetry condition reduces the search space by identifying each solution with its reflection exchanging the two diagonal systems, so it suffices to enumerate solutions modulo this involution.
The problem for fixed $p$ is therefore equivalent to an exact cover instance in the sense of Section 7.2.2.1: options are word placements, items are position constraints together with word usage constraints, and the covering condition enforces that each item is satisfied exactly once. Algorithm X with the dancing-links representation applies directly, with branching on items corresponding to the most constrained position or word at each recursive step.
For each $p \in [1,10]$, the existence and “best” solutions depend entirely on the underlying dictionary $W$ used in $\mathrm{WORDS}(W)$, since both the set of admissible options and the solvability of the resulting exact cover instance are functions of $W$. Without an explicit specification of $W$, the maximal achievable periods and the corresponding optimal word sets are not determined by the combinatorial structure alone.
Thus the solution procedure is: construct the exact cover system described above for each $p$, apply Algorithm X with dancing links to enumerate all solutions invariant under diagonal symmetry, and select those $p$ for which a solution exists. The resulting optimal word sets are precisely the solutions returned by this search.
This completes the solution. ∎