TAOCP 7.2.2.1 Exercise 87

Let $W$ be the dictionary, consisting of words of length $n$.

taocpmathematicsalgorithmsvolume-4hard

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: 3m14s

Solution

Let $W$ be the dictionary, consisting of words of length $n$. We construct an XCC instance whose solutions correspond exactly to double word squares.

The difficulty is that a choice of $n$ row words determines an $n\times n$ array, while the column words must be chosen consistently with the letters already placed. XCC colors provide the required consistency condition.

XCC construction

Introduce the following primary items:

$$ R_1,\ldots,R_n,\qquad C_1,\ldots,C_n , $$

where $R_i$ means that row $i$ has been assigned a word and $C_j$ means that column $j$ has been assigned a word.

To enforce that the $2n$ selected words are all different, introduce one additional primary item for each dictionary word:

$$ D_w\qquad(w\in W). $$

The item $D_w$ will ensure that the word $w$ is used at most once.

The remaining constraints are letter agreements. For every cell $(i,j)$, introduce a colored secondary item

$$ P_{i,j}. $$

A color on $P_{i,j}$ represents the letter placed in that cell.

Now create options.

For every row position $i$ and every word

$$ w=w_1w_2\cdots w_n\in W, $$

create a row option

$$ (i,w). $$

This option covers the primary items

$$ R_i,\qquad D_w, $$

and places color $w_j$ on the secondary item $P_{i,j}$ for every

$$ 1\leq j\leq n. $$

Thus, choosing $(i,w)$ means that row $i$ contains $w$.

Similarly, for every column position $j$ and every word

$$ w=w_1w_2\cdots w_n\in W, $$

create a column option

$$ (j,w). $$

This option covers

$$ C_j,\qquad D_w, $$

and places color $w_i$ on $P_{i,j}$ for every

$$ 1\leq i\leq n. $$

Thus, choosing $(j,w)$ means that column $j$ contains $w$.

The primary items require every row position and every column position to receive exactly one word. The $D_w$ items ensure that no word is used twice. The colored secondary items require that the letter supplied by the chosen row word agrees with the letter supplied by the chosen column word at every cell.

Correctness of the encoding

Suppose first that an $n\times n$ double word square is given. For every row $i$, choose the row option corresponding to the word in that row. For every column $j$, choose the column option corresponding to the word in that column.

Each $R_i$ and $C_j$ is covered exactly once. Since the $2n$ words in a double word square are different, each $D_w$ is covered exactly once.

It remains to check the colored secondary items. At cell $(i,j)$, the row option gives color

$$ w_j, $$

where $w$ is the word in row $i$. The column option gives the color

$$ v_i, $$

where $v$ is the word in column $j$. These two letters are equal because the row and column words come from the same array. Hence the two colors on $P_{i,j}$ are compatible.

Therefore the selected options form an XCC solution.

Conversely, suppose an XCC solution is given. Since every $R_i$ is primary, exactly one row option is chosen for each row position. Let the chosen word in row $i$ be

$$ u^{(i)}=u^{(i)}_1u^{(i)}_2\cdots u^{(i)}_n . $$

Similarly, every $C_j$ is covered exactly once, so exactly one column option is chosen for each column position. Let the chosen word in column $j$ be

$$ v^{(j)}=v^{(j)}_1v^{(j)}_2\cdots v^{(j)}_n . $$

For the secondary item $P_{i,j}$, the row option contributes the color

$$ u^{(i)}_j, $$

while the column option contributes

$$ v^{(j)}_i. $$

Compatibility requires

$$ u^{(i)}_j=v^{(j)}_i . $$

Hence the entry in row $i$, column $j$ of the array formed by the row words is exactly the letter specified by the selected column word. Therefore the selected row words and column words form a single $n\times n$ array.

Finally, because each $D_w$ is a primary item, no word can occur more than once. Thus the $2n$ row and column words are distinct.

Therefore the XCC solutions are exactly the double word squares.

The transpose question

A double word square and its transpose are both double word squares. In the above XCC formulation they correspond to two different solutions, because the roles of the row options and column options are exchanged.

Algorithm C enumerates solutions of the XCC instance. Merely noticing after a solution has been generated that its transpose has already appeared does not reduce the amount of search performed. The algorithm has already spent the work required to find the duplicate solution. Therefore there is no factor-of-2 saving in the straightforward XCC formulation.

A factor-of-2 reduction is possible only if the symmetry is removed before the search, by adding a symmetry-breaking condition. For example, one could require that the sequence of row words be lexicographically no greater than the sequence of column words.

Let

$$ (r_1,\ldots,r_n) $$

be the ordered list of row words and

$$ (c_1,\ldots,c_n) $$

the ordered list of column words. The added condition is

$$ (r_1,\ldots,r_n)\leq_{\mathrm{lex}}(c_1,\ldots,c_n). $$

This condition is invariant under transposition except that the two sides are exchanged. Therefore every pair consisting of a nonsymmetric square and its transpose has exactly one member satisfying the condition. If the square equals its transpose, then

$$ (r_1,\ldots,r_n)=(c_1,\ldots,c_n), $$

so the condition holds and the square is retained.

Thus this symmetry breaking would remove the duplicate transpose solutions. However, this is an additional constraint that must be encoded into the XCC instance. It is not obtained automatically by Algorithm C, and the original XCC construction does not contain it. Without such an explicit symmetry-breaking mechanism, Algorithm C searches both orientations.

Comparison with the algorithm of exercise 7.2.2-28

The dedicated algorithm of exercise 7.2.2-28 exploits the special structure of word squares. When a row word is selected, it immediately determines the required prefixes of the future column words. Thus the search can branch on partial words and reject impossible prefixes before complete row and column assignments have been formed.

The XCC formulation above treats the problem as a general colored exact-cover problem. It contains

$$ 2n|W| $$

possible row and column placement options before preprocessing, together with

$$ n^2 $$

colored secondary items and

$$ |W| $$

word-use primary items. Algorithm C has no inherent knowledge that these colored constraints arise from word prefixes. It only sees compatibility among options.

Consequently, the specialized algorithm can prune much earlier and usually searches a substantially smaller tree. Algorithm C remains applicable and may compete on moderate instances because XCC is a powerful general framework, but the algorithm of exercise 7.2.2-28 is better adapted to double word squares and can exploit information that the generic XCC formulation does not expose.

Hence the answers are:

  1. The double word square problem has the XCC encoding described above.
  2. A factor of $2$ cannot be saved merely by discarding transposes after they are generated. It can only be saved by adding a valid symmetry-breaking condition to the XCC instance.
  3. Algorithm C can solve the problem, but the specialized algorithm of exercise 7.2.2-28 has an advantage because it exploits the prefix structure of word-square construction.

$$ \boxed{\text{The XCC encoding is exact, but transpose elimination requires explicit symmetry breaking.}} $$