TAOCP 7.2.2.1 Exercise 390
Edit Let the entries of an (n\times n) futoshiki puzzle be (x_{r,c}), where [ 1\le r,c\le n,\qquad x_{r,c}\in{1,\ldots,n}.
Section 7.2.2.1: Dancing Links
Exercise 390. ▶ [21] Show that every futoshiki puzzle is a special case of an exact cover problem. In fact, show that every such puzzle can be formulated in at least two different ways:
- a) Use a purwarver ordering trick analogous to (25) or (26), to encode the weak clues.
- b) Use color controls to formulate an XCC problem suitable for Algorithm C.
Verified: no
Solve time: 2m12s
Edit
Solution
Let the entries of an (n\times n) futoshiki puzzle be (x_{r,c}), where
[ 1\le r,c\le n,\qquad x_{r,c}\in{1,\ldots,n}. ]
A solution is a Latin square satisfying all strong clues and all weak clues. We first encode the Latin-square conditions and then show two ways to encode the weak inequalities.
For every possible assignment
[ x_{r,c}=v ]
introduce an option denoted by
[ (r,c,v). ]
The option covers the three primary items
[ \operatorname{cell}(r,c),\qquad \operatorname{row}(r,v),\qquad \operatorname{col}(c,v). ]
Every exact cover must cover each (\operatorname{cell}(r,c)) item once, so every cell receives exactly one value. The row items force every value to occur exactly once in each row, and the column items force every value to occur exactly once in each column. Therefore these options give exactly the Latin squares.
A strong clue
[ x_{r,c}=v ]
is handled by deleting all options involving (\operatorname{cell}(r,c)) except the option ((r,c,v)). Hence only Latin squares satisfying the strong clues remain.
It remains to encode a weak clue
[ x_{r,c}<x_{r',c'}. ]
(a) Pairwise ordering trick
For one weak clue, introduce a separate auxiliary item
[ p_{u,v} ]
for every forbidden pair
[ v\ge u, ]
where (v) is a possible value of (x_{r,c}) and (u) is a possible value of (x_{r',c'}).
Modify the options for the two cells as follows.
If the first cell receives value (v), the option ((r,c,v)) additionally covers every auxiliary item
[ p_{u,v} ]
with
[ 1\le u\le v. ]
If the second cell receives value (u), the option ((r',c',u)) additionally covers every auxiliary item
[ p_{u,v} ]
with
[ u\le v\le n. ]
Consider choosing values (v) and (u) for the two cells.
If
[ v\ge u, ]
then the two options both cover the auxiliary item
[ p_{u,v}, ]
so they cannot occur together in an exact cover.
If
[ v<u, ]
then there is no auxiliary item common to the two options. Indeed, the first option only covers items whose second index is its value (v), and the second option only covers items whose first index is its value (u). A common item would have to be (p_{u,v}), which exists only when (u\le v). Thus no conflict is created.
Therefore the two options can be chosen together exactly when
[ v<u. ]
Applying this construction separately to every weak clue gives an ordinary exact cover problem. The exact covers are precisely the Latin squares satisfying all strong and weak clues.
(b) Color-controlled XCC formulation
We now use Algorithm C and color controls. The Latin-square part remains unchanged. For each weak clue
[ x_{r,c}<x_{r',c'}, ]
introduce secondary items
[ s_1,s_2,\ldots,s_{n-1}. ]
The options for the first cell are given the following colored secondary items. If
[ x_{r,c}=v, ]
then the option ((r,c,v)) covers
[ s_1,\ldots,s_v, ]
and each of these occurrences has color (A).
The options for the second cell are given the following colored secondary items. If
[ x_{r',c'}=u, ]
then the option ((r',c',u)) covers
[ s_u,\ldots,s_{n-1}, ]
and each of these occurrences has color (B), where
[ A\ne B. ]
Recall that in XCC a secondary item may occur in several selected options only when all occurrences have the same color. Hence two selected options conflict exactly when they cover a common secondary item with different colors.
Suppose the chosen values are (v) and (u).
If
[ v\ge u, ]
then the two options both cover the secondary item
[ s_u. ]
The first option covers it with color (A), while the second covers it with color (B). Since
[ A\ne B, ]
the two options are incompatible.
If
[ v<u, ]
then the first option only covers secondary items with indices at most (v), while the second only covers secondary items with indices at least (u). These sets are disjoint, so no color conflict occurs.
Thus the XCC constraints permit exactly the assignments satisfying
[ x_{r,c}<x_{r',c'}. ]
Using separate secondary items for each weak clue gives an XCC instance whose solutions are exactly the solutions of the futoshiki puzzle.
The two formulations differ in how the ordering information is represented. The first replaces every forbidden value pair by an ordinary exact-cover conflict. The second uses the color mechanism of XCC to make incompatible choices disagree on a shared secondary item.
Therefore every futoshiki puzzle is a special case of an exact cover problem, and every futoshiki puzzle also has an equivalent XCC formulation suitable for Algorithm C. (\square)