TAOCP 7.2.2 Exercise 28
Let the $m \times n$ rectangle be filled one cell at a time in row-major order.
Exercise 28. ▶ [23] [23] The method of exercises 24 and 25 does $n$ levels of backtracking to fill the cells of an $m \times n$ rectangle one column at a time, using a trie to detect illegal prefixes in the rows. Devise a method that does $mn$ levels of backtracking and fills just one cell per level, using tries for both rows and columns.
Verified: yes
Solve time: 3m04s
Solution
Let the $m \times n$ rectangle be filled one cell at a time in row-major order. Define a bijection between levels $1 \le l \le mn$ and cell coordinates $(i,j)$ by
$i = \left\lfloor \frac{l-1}{n} \right\rfloor + 1,\qquad j = (l-1) \bmod n + 1.$
Let $T_R$ be a trie containing all words of length $n$ used for rows, and let $T_C$ be a trie containing all words of length $m$ used for columns. Each node of $T_R$ represents a prefix of some row-word; each node of $T_C$ represents a prefix of some column-word.
For each level $l$, maintain pointers
$u_i \in T_R \quad (1 \le i \le m), \qquad v_j \in T_C \quad (1 \le j \le n),$
where $u_i$ is the node corresponding to the current prefix of row $i$, and $v_j$ is the node corresponding to the current prefix of column $j$.
The invariant at level $l$ is that for all $i < \left\lfloor \frac{l-1}{n} \right\rfloor + 1$, the prefix of row $i$ of length $n$ is consistent with a path in $T_R$, and for all columns $j < (l-1 \bmod n)+1$, the prefix of column $j$ of length $m$ is consistent with a path in $T_C$. At level $l$, only row $i$ and column $j$ are potentially extended.
At level $l$, a candidate letter $x_l = a$ is admissible if and only if there exists an outgoing edge labeled $a$ from both $u_i$ in $T_R$ and $v_j$ in $T_C$. Equivalently, if $\delta_R(u_i,a)$ and $\delta_C(v_j,a)$ are defined.
The backtracking algorithm proceeds as follows.
B1$^\dagger$. Set all row pointers $u_i$ to the root of $T_R$ for $1 \le i \le m$, set all column pointers $v_j$ to the root of $T_C$ for $1 \le j \le n$, and set $l \leftarrow 1$.
B2$^\dagger$. If $l > mn$, visit the constructed rectangle and go to B5$^\dagger$. Otherwise determine $(i,j)$ from $l$ and set $t \leftarrow$ first symbol of the alphabet.
B3$^\dagger$. If $\delta_R(u_i,t)$ is undefined or $\delta_C(v_j,t)$ is undefined, go to B4$^\dagger$. Otherwise set
$u_i' \leftarrow \delta_R(u_i,t), \qquad v_j' \leftarrow \delta_C(v_j,t),$
store $x_l \leftarrow t$, replace $u_i \leftarrow u_i'$, $v_j \leftarrow v_j'$, set $l \leftarrow l+1$, and go to B2$^\dagger$.
B4$^\dagger$. If $t$ is not the last symbol of the alphabet, replace $t$ by the next symbol and return to B3$^\dagger$.
B5$^\dagger$. Set $l \leftarrow l-1$. If $l > 0$, recover $(i,j)$ from $l$ and set $t \leftarrow x_l$. Then restore the previous trie states by moving $u_i$ and $v_j$ to their parent nodes in $T_R$ and $T_C$, respectively, and return to B4$^\dagger$. If $l = 0$, stop. $\blacksquare$
Correctness follows from the invariant that each row prefix is always a path in $T_R$ and each column prefix is always a path in $T_C$. Any complete construction corresponds to $mn$ successful extensions, hence each row is a word of length $n$ in the language of $T_R$ and each column is a word of length $m$ in the language of $T_C$. Conversely, any valid word rectangle yields a sequence of admissible choices at every level since every row and column word induces a full root-to-leaf path in the corresponding trie. This completes the proof. ∎