TAOCP 7.2.2.1 Exercise 88
The flaw in the previous solution is not a minor modeling issue but a fundamental misuse of exact cover.
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: 2m52s
The flaw in the previous solution is not a minor modeling issue but a fundamental misuse of exact cover. A double word square is not a structure where rows and columns are independently chosen objects; the columns are fully determined by the rows. Any correct reduction must respect this dependency.
We restart from the correct combinatorial formulation.
A double word square of size $n$ is an $n \times n$ grid over an alphabet such that every row is a word in $\mathrm{WORDS}(W)$, every column is also a word in $\mathrm{WORDS}(W)$, and all $2n$ words (rows and columns) are pairwise distinct.
For a fixed $W$, the decision problem is therefore: does there exist a choice of $n$ words $r_1,\dots,r_n \in \mathrm{WORDS}(W)$ such that if we define the grid by $A(i,j) = r_i[j]$, then every column word $c_j = A(1,j)\cdots A(n,j)$ also lies in $\mathrm{WORDS}(W)$, and all $r_i$ and $c_j$ are distinct?
The key correction is that we do not construct a pure exact cover instance whose solutions are in bijection with squares. Instead, we use dancing links (Algorithm X) as a controlled backtracking engine for selecting row words, and we enforce column constraints incrementally as pruning conditions. This is the standard way DLX is used in many Knuth-style applications when some constraints are functional consequences of others.
We construct a search tree where at level $i$ we choose the $i$-th row word $r_i \in \mathrm{WORDS}(W)$. The branching structure over choices of words can be implemented with dancing links by treating each word occurrence as a selectable row in the DLX matrix with a single primary constraint “row position $i$ is filled”. Concretely, for each pair $(i,w)$ with $w \in \mathrm{WORDS}(W)$, we create a DLX row that represents assigning word $w$ to row $i$, and it covers exactly one primary column: $(i)$, ensuring exactly one word per row.
All other constraints are enforced by propagation rather than by exact cover columns.
When we have chosen the first $k$ rows, the partial grid is determined on the first $k$ rows. For each column $j$, we maintain the current prefix $p_j$ of length $k$. We maintain a trie built from $\mathrm{WORDS}(W)$, so we can test two properties in optimal time: whether a prefix $p_j$ can still be extended to some word in $\mathrm{WORDS}(W)$, and whether $p_j$ is already a complete word in $\mathrm{WORDS}(W)$.
Thus during the DLX search, whenever we tentatively select a row word $w$ for row $i$, we update all column prefixes. If any column prefix ceases to be a prefix of any dictionary word, we immediately backtrack. This restores the missing consistency constraints that were incorrectly modeled as exact cover constraints in the flawed solution.
At depth $n$, we obtain a full grid. We then compute all column strings $c_1,\dots,c_n$ and check two final conditions: each $c_j \in \mathrm{WORDS}(W)$, and all $r_1,\dots,r_n,c_1,\dots,c_n$ are distinct. If both hold, we have found a valid double word square.
This correction fixes the central error: columns are not independent objects to be chosen in an exact cover instance. They are deterministic functions of the row choices, and therefore their constraints must be enforced dynamically rather than encoded as independent DLX rows.
The binary search over $W$ is now justified cleanly. Define $P(W)$ as “there exists a valid double word square using words of rank at most $W$”. If $P(W)$ holds, then $P(W')$ holds for all $W' > W$, since enlarging the dictionary cannot destroy an existing solution. Hence $P$ is monotone.
We compute the smallest $W$ with $P(W)$ by binary search. Each feasibility check runs the DLX-based backtracking described above, restricted to the subset $\mathrm{WORDS}(W)$.
Finally, we note that distinctness of all $2n$ words is enforced explicitly during the search. Row words are distinct by construction of the DLX constraint system (one word per row). Column words are computed at the leaves, and we reject any solution where a column word repeats another column word or matches any row word.
This yields a correct reduction: DLX is used to enumerate row assignments efficiently, while column validity and global distinctness are enforced as dynamic constraints. The resulting procedure correctly decides feasibility for each $W$, and binary search returns the minimal $W$ supporting a double word square.