TAOCP 7.2.2 Exercise 25
Let $W$ be the set of all admissible $5$-letter words.
Exercise 25. ▶ [25] [25] Explain how to use orthogonal lists, as in Fig. 13 of Section 7.2.6, so that it's easy to visit all 5-letter words whose $k$th character is $c$, given $1 \le k \le 5$ and $a \le c \le z$. Use those sublists to speed up the algorithm of exercise 24.
Verified: yes
Solve time: 48s
Solution
Let $W$ be the set of all admissible $5$-letter words. Exercise 24 uses Algorithm B to construct the rectangle row by row. At level $l$, the predicate $P_l$ requires that every column prefix formed by the first $l$ rows be the prefix of at least one $6$-letter word. The expensive operation is finding all candidate fifth-letter words that agree with prescribed letters in specified positions.
An orthogonal-list representation removes this bottleneck.
For each position $k$, $1 \le k \le 5$, and each letter $c$, $a \le c \le z$, define
$$ L_{k,c}={,w\in W\mid\text{the $k$th character of $w$ is }c,}. $$
Each word belongs to exactly one list for each value of $k$. Hence every word appears in exactly five lists.
Represent every list $L_{k,c}$ as a doubly linked list. Every word record therefore contains five independent pairs of links,
$$ (\mathrm{left}_k,\mathrm{right}_k),\qquad 1\le k\le5, $$
one pair for each position. The header for list $L_{k,c}$ stores the first and last elements of that list. This is precisely the orthogonal-list organization of Section 7.2.6: Each record simultaneously belongs to several independent linked lists, one in each direction.
Suppose the search has reached level $l$, and suppose that the partial rectangle determines that the next row must satisfy character constraints
$$ w_{i_j}=c_j,\qquad 1\le j\le r, $$
where the positions $i_1,\ldots,i_r$ are distinct. The desired candidates are
$$ L_{i_1,c_1}\cap L_{i_2,c_2}\cap\cdots\cap L_{i_r,c_r}. $$
Choose among these lists one having minimum length, say $L_{i_t,c_t}$. Traverse only that list. For each word encountered, test the remaining $r-1$ specified positions directly in the word record. Since each test consists only of character comparisons, the total work is proportional to
$$ |L_{i_t,c_t}|,r, $$
instead of scanning the entire dictionary.
This organization speeds the algorithm of exercise 24 as follows.
When Algorithm B enters level $l$, the column-prefix tests determine which letters are permissible in each of the five positions of row $l$. If any position admits no letter, step B3 fails immediately. Otherwise the candidate row words are obtained by intersecting the corresponding orthogonal sublists as described above. Every word surviving these character tests is then subjected to the remaining prefix tests required by $P_l$. Since the overwhelming majority of words are discarded before those prefix tests are attempted, the branching factor of the search tree is reduced substantially.
The data structure requires only linear storage. If $N=|W|$, there are $5N$ list nodes, because each word participates in exactly one list for each of the five character positions. The list headers contribute only $5\cdot26=130$ additional records. Insertions and deletions, if desired, take constant time because every list is doubly linked, and merely visiting all words with prescribed $k$th character requires traversing the corresponding list.
Thus orthogonal lists provide direct access to every set
$$ {,w\in W\mid w_k=c,}, $$
and replacing repeated scans of the entire dictionary by intersections of these sublists gives a substantially faster implementation of the backtrack algorithm from exercise 24.