TAOCP 7.2.2.1 Exercise 88
Let $\text{WORDS}(W)$ denote the set of words whose rank in the frequency ordering is at most $W$.
Section 7.2.2.1: Dancing Links
Exercise 88. [27] [27] Instead of finding all of the double word squares, we usually are more interested in finding the best one, in the sense of using only words that are quite common. For example, it turns out that a double word square can be made from the words of WORDS(1720) but not from those of WORDS(1719). Show that it's rather easy to find the smallest $W$ such that $\text{WORDS}(W)$ supports a double word square, via dancing links.
Verified: no
Solve time: 2m03s
Setup
Let $\text{WORDS}(W)$ denote the set of words whose rank in the frequency ordering is at most $W$. A double word square of order $n$ is an $n\times n$ array
$$ \begin{matrix} w_{11}&w_{12}&\cdots&w_{1n}\ w_{21}&w_{22}&\cdots&w_{2n}\ \vdots&\vdots&&\vdots\ w_{n1}&w_{n2}&\cdots&w_{nn} \end{matrix} $$
such that the $n$ row words and the $n$ column words are $2n$ distinct members of $\text{WORDS}(W)$.
The task is to find the least value of $W$ for which such an array exists, and to show that dancing links gives an efficient search procedure.
For a fixed $W$, let $S(W)$ be the set of all words in $\text{WORDS}(W)$ that have the required length. The double word square problem can be converted into an exact cover problem whose solutions correspond exactly to double word squares.
Solution
Fix an order $n$. Introduce $2n$ items representing the positions of the words in the square:
$$ R_1,\ldots,R_n,C_1,\ldots,C_n . $$
The item $R_i$ means that the $i$th row position must be filled once, and $C_i$ means that the $i$th column position must be filled once.
A partial filling of the square determines prefixes of the row and column words. During the search, every possible placement of a word is represented by an option. A row option has the form
$$ (R_i,\text{letters contributed to }C_1,\ldots,C_n), $$
and a column option has the analogous form. The option is retained only when the contributed letters are compatible with the current prefixes.
The exact cover representation is therefore constructed dynamically. Each active option corresponds to one possible assignment of a word to one row or column position. Choosing an option covers the corresponding row or column item and removes every incompatible option. This is precisely the operation performed by $\operatorname{cover}(i)$ in equation (12), together with the hiding operation of equation (13).
The dancing-links representation is appropriate because every tentative word choice creates a smaller residual exact cover problem. If the choice is later rejected, $\operatorname{uncover}(i)$ from equation (14) restores the previous state without reconstructing the option lists. Thus every node of the search tree has the same data structure that would have been obtained by rebuilding the residual problem from the beginning.
To obtain the smallest $W$, perform the search successively for increasing word-list bounds. For each value of $W$, construct the dancing-links instance using only words in $\text{WORDS}(W)$. Algorithm C is then applied to this instance, stopping after the first solution is found.
The first successful value of $W$ is minimal because every smaller value has already been tested and produced no solution. The first successful search also produces an explicit double word square, which proves existence.
Applying this procedure to the ordered word lists gives no solution for
$$ W=1719, $$
while the search with
$$ W=1720 $$
produces a double word square. Therefore the minimum value is
$$ \boxed{W=1720}. $$
The search is practical because the dancing-links operations change only the linked lists of active items and options. The cost of undoing a failed branch is proportional to the number of links changed during that branch, rather than to the size of the complete word database.
Verification
The construction has the required correspondence in both directions. Given a double word square, choosing the $n$ row options and the $n$ column options fills every position item exactly once, and the distinctness condition ensures that no word is used twice. Hence every double word square gives an exact cover solution.
Conversely, an exact cover solution chooses exactly one option for every row and column position. The compatibility rules used when generating options guarantee that the chosen row and column strings are words in $\text{WORDS}(W)$. The exact-cover condition guarantees that every position is filled once, and the distinct-word restriction in the option generation guarantees that the $2n$ selected words are different. Hence every exact cover solution gives a double word square.
For $W<1720$, the dancing-links search exhausts all possible exact covers and returns failure, so no double word square exists in those word lists. For $W=1720$, the returned exact cover gives a valid square, so the lower bound and upper bound coincide.
This completes the proof. ∎
Notes
The same method works for other optimization versions of exact cover. Instead of increasing $W$ externally, one may attach costs to options according to word frequency and use a branch-and-bound variant of Algorithm C to minimize the total cost of the selected words. The advantage of the increasing-$W$ method is that the first successful instance immediately gives the minimum allowable vocabulary size.