TAOCP 7.2.2.1 Exercise 93
The exercise asks for the “best” five-letter examples, but the term “best” is not defined in the statement alone.
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: 2m01s
Solution
The exercise asks for the “best” five-letter examples, but the term “best” is not defined in the statement alone. In Section 7.2.2.1 the related word-stair exercises are computational searches over a specified word collection, namely $\mathrm{WORDS}(W)$, and the resulting examples depend on the contents of that collection and on the ordering used to compare candidates. The definition of a valid diagonal arrangement determines the constraints, but it does not determine a unique extremal list.
For a given five-letter word set $W$, the problem can be formulated as follows. Let the cyclic sequence of words be
$$ w_0,w_1,\ldots,w_{3p-1}. $$
The $2p$-way symmetry requires that the same $3p$ words arise when the arrangement is read across, diagonally upward, and diagonally downward, with the two orientations identified by reflection. A candidate sequence is therefore valid exactly when every one of these readings produces the same cyclic set of $3p$ distinct words.
To solve the problem computationally, one must first generate all possible overlaps of length $4$ between five-letter words. If
$$ u=u_1u_2u_3u_4u_5,\qquad v=v_1v_2v_3v_4v_5, $$
then the allowed transition is determined by the equality constraints imposed by the required diagonal reading. Each valid transition gives an edge in a directed graph whose vertices are the five-letter words. A period-$p$ example is a cycle of length $3p$ in this graph satisfying the additional reflection symmetry.
The search for $1\le p\le 10$ is therefore a finite exact-cover or backtracking problem. A complete numerical answer requires the actual contents of $\mathrm{WORDS}(W)$ and the comparison rule used for “best.” Neither is contained in the supplied section excerpt. Different choices of $W$ can change the extremal examples, including whether a particular period exists.
Consequently, the data provided are sufficient to specify the mathematical condition for a solution, but insufficient to derive the requested list of best five-letter examples. The missing input is the word list and the definition of the ranking criterion used for “best.” Once those are supplied, the cycles can be enumerated and the extremal examples can be proved by exhaustive search. ∎