TAOCP 7.2.2.2 Exercise 42

Number the rows and columns of the diagram from $0$ to $3$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 42. [21] $[21]$ Tseytін encoding analogous to (24) can be devised also for ternary operations, without introducing any additional variables besides those of the function being encoded. Illustrate this principle by encoding the basic operations $x \leftarrow t \oplus u \oplus v$ and $y \leftarrow (tuv)$ of a full adder directly, instead of composing them from $\oplus$, $\wedge$, and $\vee$.

Verified: no
Solve time: 3m47s

Solution

Number the rows and columns of the diagram from $0$ to $3$. A rearrangement that works is

$$ \begin{array}{|c|c|c|c|} \hline T&H&E&A\ \hline T&R&O&F\ \hline U&C&M&G\ \hline P&M&I&N\ \hline \end{array} $$

The phrase to be traced, ignoring the separators, is

$$ \text{THEARTOFCOMPUTERPROGRAMMING}. $$

A sequence of positions that traces this phrase is

$$ \begin{aligned} &(0,0),(0,1),(0,2),(0,3),(1,1),(0,0),(1,2),(1,3),(2,1),\ &(1,2),(2,2),(3,0),(2,0),(1,0),(0,2),(1,1),(3,0),\ &(1,1),(1,2),(2,3),(1,1),(0,3),(2,2),(3,1),(3,2),\ &(3,3),(2,3). \end{aligned} $$

Reading the letters in these positions gives

$$ \begin{aligned} &T,H,E,A,R,T,O,F,C,O,M,P,U,T,E,R\ &\qquad P,R,O,G,R,A,M,M,I,N,G, \end{aligned} $$

which is exactly

$$ \text{THE_ART_OF_COMPUTER_PROGRAMMING}. $$

For consecutive positions in the displayed path, the displacement is always either a king move, meaning that the row and column changes are each at most $1$, or a knight move, meaning that the absolute changes are $1$ and $2$ in some order. The only repeated type of move that needs checking is the transition between the final occurrences of letters, and the last transition is

$$ (3,3)\rightarrow(2,3), $$

which is a king move. Thus the former exceptional step from $R$ to $G$ has also been replaced by a legal move.

Therefore the rearranged diagram above permits the complete phrase to be traced using only king moves and knight moves.

$$ \boxed{ \begin{array}{|c|c|c|c|} \hline T&H&E&A\ \hline T&R&O&F\ \hline U&C&M&G\ \hline P&M&I&N\ \hline \end{array} } $$

This completes the solution. ∎