TAOCP 7.2.2.2 Exercise 399

Section 7.2.2.2: Satisfiability

Exercise 399. [23] [23] If the variables $u$ and $v$ range over $d$ values ${1, \ldots, d}$, it's natural to encode them directly as sequences $u_1 \ldots u_d$ and $v_1 \ldots v_d$, where $u_i = [u = i]$ and $v_j = [v = j]$, using the at-least-one clauses and the at-most-one clauses (17). A binary constraint tells us which pairs $(i, j)$ are legal; for example, the graph-coloring constraint says that $i \ne j$ when $i$ and $j$ are the colors of adjacent vertices in some graph.

One way to specify such a constraint is to assert the preclusion clauses $(\bar{u}_i \vee \bar{v}_j)$ for all illegal pairs $(i, j)$, as we did for graph coloring in (16). But there's also another general way: We can assert the support clauses

$$\bigwedge_{i=1}^{d} \Bigl(\bar{u}i \vee \bigvee{v_j \mid (i,j) \text{ is legal}}\Bigr) ;\wedge; \bigwedge{j=1}^{d} \Bigl(\bar{v}_j \vee \bigvee{u_i \mid (i,j) \text{ is legal}}\Bigr)$$

instead. Graph coloring with $d$ colors would then be clauses such as $(u_3 \vee v_1 \vee v_2 \vee v_4 \vee \cdots \vee v_d)$, when $u$ and $v$ are adjacent.

a) Suppose $f$ of the $d^2$ pairs $(i, j)$ are legal. How many preclusion clauses are needed? How many support clauses? b) Prove that the support clauses are always at least as strong as the preclusion clauses, in the sense that all consequences of the preclusion clauses under unit propagation are also consequences of the support clauses under unit propagation, given any assignment consistent with the binary variables $(u_1, \ldots, u_d, v_1, \ldots, v_d)$. c) Conversely, in the case of the graph-coloring constraint, the preclusion clauses are also at least as strong as the support clauses (hence equally strong). d) However, exhibit a binary constraint for which the support clauses are strictly stronger than the preclusion clauses.

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. ∎