TAOCP 7.2.2 Exercise 24
A $5 \times 6$ word rectangle consists of - $5$ rows, each a **six-letter** dictionary word, and - $6$ columns, each a **five-letter** dictionary word.
Exercise 24. [20] [20] Customize Algorithm B so that it will find all $5 \times 6$ word rectangles.
Verified: yes
Solve time: 1m42s
Solution
A $5 \times 6$ word rectangle consists of
- $5$ rows, each a six-letter dictionary word, and
- $6$ columns, each a five-letter dictionary word.
Algorithm B should therefore choose the rows as its search variables.
Let
$$ x_1,x_2,x_3,x_4,x_5 $$
denote the five horizontal words, where each $x_i$ is taken from the dictionary of six-letter words. After level $l$, the partial assignment is
$$ x_1,\ldots,x_l,\qquad 0\le l\le5. $$
For each column $j$, where $1\le j\le6$, define the current column prefix
$$ \pi_j=x_{1j}x_{2j}\cdots x_{lj}, $$
where $x_{ij}$ denotes the $j$th letter of row $x_i$. Thus each $\pi_j$ has length $l$.
To support the cutoff test, preprocess the dictionary of five-letter words into a trie, or equivalently into prefix tables. For each $k$ with
$$ 0\le k\le4, $$
define
$$ T_k(\alpha)= \begin{cases} 1,&\text{if }\alpha\text{ is a prefix of some five-letter dictionary word},\ 0,&\text{otherwise.} \end{cases} $$
For completed columns, define
$$ T_5(\alpha)= \begin{cases} 1,&\text{if }\alpha\text{ is itself a five-letter dictionary word},\ 0,&\text{otherwise.} \end{cases} $$
Thus $T_5$ tests dictionary membership, not merely prefix admissibility. In a trie this is implemented by marking terminal nodes.
The cutoff predicate is
$$ P_l(x_1,\ldots,x_l) $$
defined by
$$ P_l(x_1,\ldots,x_l) \iff T_l(\pi_j)=1 \quad\text{for every }1\le j\le6. $$
For $l<5$, this means that every current column prefix can still be extended to a five-letter dictionary word. For $l=5$, every column has length $5$, so $T_5$ requires each completed column to be an actual five-letter dictionary word.
The maintained state consists only of the six current column prefixes
$$ \pi_1,\ldots,\pi_6. $$
Descending one level appends one letter to each prefix. Backtracking deletes the last letter from each prefix. These operations are exact inverses, satisfying the update and downdate requirements of Algorithm B.
The customized algorithm is therefore as follows.
B1$^*$. [Initialize.]
Construct the prefix tables $T_0,T_1,\ldots,T_5$ from the dictionary of five-letter words.
Set
$$ l\leftarrow1, $$
and initialize
$$ \pi_1=\pi_2=\cdots=\pi_6=\epsilon, $$
where $\epsilon$ denotes the empty word.
B2$^*$. [Enter level $l$.]
If $l>5$, visit
$$ (x_1,x_2,x_3,x_4,x_5) $$
and go to B5$^*$.
Otherwise initialize the candidate list consisting of all six-letter dictionary words.
B3$^*$. [Try the current row.]
Let the current candidate row be
$$ w=w_1w_2w_3w_4w_5w_6. $$
For each column $j$, form
$$ \pi_j'=\pi_jw_j. $$
If
$$ T_l(\pi_j')=1 \qquad(1\le j\le6), $$
then set
$$ x_l\leftarrow w, $$
replace every
$$ \pi_j\leftarrow\pi_j', $$
set
$$ l\leftarrow l+1, $$
and return to B2$^*$.
Otherwise continue with B4$^*$.
B4$^*$. [Try again.]
If another six-letter dictionary word remains, make it the current candidate and return to B3$^*$.
Otherwise proceed to B5$^*$.
B5$^*$. [Backtrack.]
Set
$$ l\leftarrow l-1. $$
If
$$ l=0, $$
terminate.
Otherwise delete the final letter from each current column prefix
$$ \pi_1,\ldots,\pi_6, $$
and continue at B4$^*$ with the next candidate after the previously chosen row.
Correctness
Every reported object is a valid $5\times6$ word rectangle.
Each selected row is a six-letter dictionary word because every assignment to $x_l$ is chosen from the six-letter dictionary.
After five rows have been selected, each column has length $5$. The condition
$$ T_5(\pi_j)=1 $$
holds for every column, and by definition of $T_5$ this means that each completed column is a five-letter dictionary word. Hence every reported rectangle satisfies both the row and column requirements.
Conversely, every valid $5\times6$ word rectangle is generated.
Suppose the rows of such a rectangle are
$$ x_1,\ldots,x_5. $$
After the first $l$ rows have been chosen, each current column prefix is exactly the length-$l$ prefix of the corresponding five-letter column word. Therefore every prefix satisfies the test
$$ T_l(\pi_j)=1. $$
No branch leading to the rectangle is ever pruned, and Algorithm B eventually reaches the complete rectangle. Since the sequence of chosen rows uniquely determines the rectangle, it is generated exactly once.
Therefore the customized Algorithm B enumerates precisely all $5\times6$ word rectangles.