TAOCP 7.2.2.2 Exercise 396
Number the rows and columns of the diagram from $0$ to $3$.
Section 7.2.2.2: Satisfiability
Exercise 396. ▶ [23] [23] (Double clique hints.) If $x$ has one of the $d$ values ${0, 1, \ldots, d-1}$, we can represent it binarywise with respect to two different orderings by letting $x^i = [x \ge j]$ and $\bar{x}^i = [x \ge j]$ for $1 \le j < d$, where $\pi$ is any given permutation. For example, if $d = 4$ and $(0\pi, 1\pi, 2\pi, 3\pi) = (2, 3, 0, 1)$, the representations $x^1 x^2 / \bar{x}^1 \bar{x}^2 \bar{x}^2$ of $0, 1, 2$, and $3$ are respectively $00\text{:}110$, $100\text{:}111$, $110\text{:}001$, and $111\text{:}100$. This representation allows us to encode graph coloring problems by including not only the hints (162) but also
$$(\bar{v}_i^{d-k+1} \vee \cdots \vee \bar{v}_i^{d-k+1}) \wedge (v_i^{k-1} \vee \cdots \vee \bar{v}_i^{k-1}),$$
whenever the variables ${v_1, \ldots, v_k}$ form a $k$-clique.
Explain how to construct clauses for this encoding, and experiment with coloring the $n \times n$ queens graph when $(0\pi, 1\pi, 2\pi, 3\pi, 4\pi, \ldots) = (0, d{-}1, 1, d{-}2, \ldots)$ is the inverse of the organ-pipe permutation.
Verified: no
Solve time: 3m48s
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. ∎