TAOCP 7.2.2.1 Exercise 87
An $n \times n$ double word square is an array filled with words such that each of the $n$ rows is a word, each of the $n$ columns is a word, and all $2n$ words are pairwise distinct.
Section 7.2.2.1: Dancing Links
Exercise 87. [30] [30] A double word square is an $n \times n$ array whose rows and columns contain $2n$ different words. Encode this problem as an XCC problem. Can you save a factor of 2 by not generating the transpose of previous solutions? Does Algorithm C compete with the algorithm of exercise 7.2.2–28 (which was designed explicitly to handle such problems)?
Verified: no
Solve time: 1m05s
Setup
An $n \times n$ double word square is an array filled with words such that each of the $n$ rows is a word, each of the $n$ columns is a word, and all $2n$ words are pairwise distinct. Each row word has length $n$, each column word has length $n$, and the letter in position $(i,j)$ must simultaneously agree with the $j$-th letter of the row word placed in row $i$ and the $i$-th letter of the column word placed in column $j$.
An XCC formulation requires a family of items, together with options, where each option is a set of items and a solution is a subfamily of pairwise disjoint options that covers all items exactly once.
Solution
The encoding uses two kinds of structural choices: placement of words into rows and placement of words into columns. For each row index $i$ with $1 \le i \le n$, introduce a primary item $R_i$, and for each column index $j$ with $1 \le j \le n$, introduce a primary item $C_j$. These enforce that exactly one word is assigned to each row and each column.
For each word $w$ in the dictionary, introduce a primary item $W(w)$ to enforce that each word is used at most once. In a solution of size $2n$, exactly $2n$ distinct words must be selected, so this guarantees pairwise distinctness of row and column words.
To enforce consistency of letters, introduce secondary items indexed by triples $(i,j,a)$ where $1 \le i,j \le n$ and $a$ is a letter in the alphabet. The intended meaning is that item $(i,j,a)$ is covered if and only if the cell $(i,j)$ is forced to carry letter $a$.
Two families of options are introduced.
For each word $w$ and row index $i$, define a row-placement option $O(i,w)$ provided $w$ has length $n$. The option $O(i,w)$ contains the items $R_i$, $W(w)$, and for every column index $j$ the item $(i,j,w_j)$, where $w_j$ denotes the $j$-th letter of $w$.
For each word $w$ and column index $j$, define a column-placement option $O'(j,w)$ provided $w$ has length $n$. The option $O'(j,w)$ contains the items $C_j$, $W(w)$, and for every row index $i$ the item $(i,j,w_i)$, where $w_i$ denotes the $i$-th letter of $w$.
A valid exact cover selects exactly $n$ row-placement options and $n$ column-placement options. The item constraints $R_i$ and $C_j$ force a bijective assignment of words to rows and columns. The items $W(w)$ force all chosen words to be distinct. The cell-letter items $(i,j,a)$ enforce that the letter placed in cell $(i,j)$ is determined consistently by both its row word and its column word, since any selected row option contributing $(i,j,a)$ and any selected column option contributing $(i,j,b)$ must satisfy $a=b$ in order for $(i,j,a)$ and $(i,j,b)$ not to violate uniqueness of coverage; hence both placements must agree at every cell.
This produces an XCC instance whose solutions are exactly double word squares.
To save a factor of $2$, observe that transposing a solution interchanges the roles of rows and columns. Every solution is paired with its transpose, and the encoding above is invariant under swapping the families ${R_i}$ and ${C_j}$ together with swapping row and column options. To eliminate this duplication, impose a canonical restriction such as fixing a total order on words and requiring that the lexicographically smallest word among the $2n$ chosen words occurs in a row rather than in a column. This removes exactly one representative from each transpose pair whenever the solution is not self-transpose.
Algorithm C with this restriction explores a search space reduced by a factor asymptotically close to $2$ in the generic case. Self-transpose solutions remain unpaired, so they are unaffected.
Regarding competitiveness with the minimax modification of Exercise 85, the additional symmetry restriction reduces the branching factor at the top level by eliminating symmetric starts, but the underlying constraint structure remains substantially more coupled than in standard exact cover instances. Algorithm C with dancing links continues to be efficient because each choice of a row or column word triggers strong propagation through the cell items $(i,j,a)$, often forcing rapid elimination of incompatible placements. The minimax objective of Exercise 85 is orthogonal to this symmetry, since it orders options rather than constraining compatibility structure. In this setting, the symmetry reduction provides a constant-factor improvement in explored branches, while the minimax strategy primarily affects search ordering and pruning but does not change the fundamental propagation strength of the XCC encoding.
This completes the solution. ∎