TAOCP 7.2.2.2 Exercise 391

The required phrase contains \text{THEARTOFCOMPUTERPROGRAMMING} as its sequence of letters.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.2: Satisfiability

Exercise 391. [M25] [M25] The values of two integer variables satisfy $0 \le x, y < d$, and they are to be represented as $l$-bit quantities $x_{l-1} \ldots x_0, y_{l-1} \ldots y_0$, where $l = \lfloor \lg d \rfloor$. Specify three different ways to encode the relation $x \ne y$:

a) Let $x = (x_{l-1} \ldots x_0)2$ and $y = (y{l-1} \ldots y_0)2$; and let the encoding enforce the conditions $(x{l-1} \ldots x_0)2 < d$, and $(y{l-1} \ldots y_0)2 < d$, as well as ensuring that $x \ne y$ by introducing $2l + 1$ additional clauses in $l$ auxiliary variables. b) Like (a), but there are $l$ additional clauses (not $2l + 1$), and no auxiliaries. c) All bit patterns $x{l-1} \ldots x_0$ and $y_{l-1} \ldots y_0$ are valid, but some values might have two different patterns. The encoding has $d$ clauses and no auxiliary variables.

Verified: no
Solve time: 3m48s

Solution

The required phrase contains

$$ \text{THEARTOFCOMPUTERPROGRAMMING} $$

as its sequence of letters. A rearrangement is obtained by placing these letters in a $4\times 7$ array, leaving one cell unused, as follows:

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

The trace begins at the upper left corner and follows the cells in the order

$$ (1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7), $$

then continues through the second row from right to left,

$$ (2,7),(2,6),(2,5),(2,4),(2,3),(2,2),(2,1), $$

then through the third row from left to right,

$$ (3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(3,7), $$

and finally through the fourth row from right to left,

$$ (4,7),(4,6),(4,5),(4,4),(4,3),(4,2). $$

Reading the letters in this order gives

$$ T,H,E,A,R,T,O,F,C,O,M,P,U,T,E,R,P,R,O,G,R,A,M,M,I,N,G, $$

which is exactly

$$ \text{THEARTOFCOMPUTERPROGRAMMING}. $$

For consecutive cells in each row, the move is a horizontal king move. The transition from the end of one row to the beginning of the next row is a vertical king move:

$$ (1,7)\to(2,7),\qquad (2,1)\to(3,1),\qquad (3,7)\to(4,7). $$

The final transition is

$$ (4,2)\text{ with the letter }G, $$

so no additional exceptional move is needed. Every consecutive pair of letters in the phrase is therefore connected by a legal king move.

The rearranged diagram is

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