TAOCP 7.2.2.1 Exercise 67

Section 7.2.2.1: Dancing Links

Exercise 67. ▶ [22] [22] Hypersudoku extends normal sudoku by adding four more (shaded) boxes in which a complete "rainbow" ${1, 2, 3, 4, 5, 6, 7, 8, 9}$ is required to appear:

(Such puzzles, introduced by P. Ritmeester in 2005, are featured by many newspapers.)

a) Show that a hypersudoku solution actually has 18 rainbow boxes, not only 13.

b) Use that observation to solve hypersudoku puzzles efficiently by extending (30).

c) How much does that observation help when solving (i) and (ii)?

d) True or false: A hypersudoku solution remains a hypersudoku solution if the four $4 \times 4$ blocks that touch its four corners are simultaneously rotated $180°$, while also flipping the middle half-rows and middle half-columns (keeping the center fixed).

Verified: no
Solve time: 2m21s

---

Solution

Let the rows and columns of the $9\times9$ array be numbered $1,\ldots,9$. A rainbow box is a set of nine cells containing each of the digits $1,\ldots,9$ exactly once.

The four additional hypersudoku boxes are the $3\times3$ regions

$$ {2,3,4}\times{2,3,4},\quad {2,3,4}\times{6,7,8}, $$

$$ {6,7,8}\times{2,3,4},\quad {6,7,8}\times{6,7,8}. $$

Together with the nine ordinary sudoku boxes, these give the usual thirteen rainbow boxes.

For part (a), consider the four pairs of adjacent ordinary boxes in the top, bottom, left, and right parts of the grid. For example, the union of the two ordinary boxes in columns $1$ and $4$ of the top three rows contains the cells

$$ {1,2,3}\times{1,2,3,4,5,6}. $$

The four corresponding columns contain every digit three times, because each column is a permutation of ${1,\ldots,9}$. The six columns in the displayed set therefore contain each digit six times. The hypersudoku box occupying columns $2,3,4$ of rows $2,3,4$ already contains every digit once. Removing that box from the union leaves

$$ {1,2,3}\times{1,5,6} \cup {1,2,3}\times{7,8,9} $$

as two complementary sets. The same counting argument applied to the corresponding three-row or three-column unions gives a rainbow box in each of the four positions obtained by taking the complement of two known rainbow boxes. These are the four additional boxes lying between the shaded boxes and the boundary.

Finally, the complement of the union of the four shaded boxes and these four newly obtained boxes inside the middle three rows and middle three columns gives one further rainbow box. Thus the number of rainbow boxes is

$$ 9+4+4+1=18. $$

Hence every hypersudoku solution contains eighteen rainbow boxes.

$$ \boxed{18\text{ rainbow boxes}} $$

For part (b), the exact-cover formulation used for ordinary sudoku can be enlarged by adding the five new forced rainbow boxes from part (a). In the exact-cover matrix, each possible placement of a digit in a cell remains an option. The usual item types are the cell items, row-digit items, column-digit items, and ordinary box-digit items. The four original hypersudoku constraints add four groups of box-digit items.

The observation from part (a) supplies five further groups of box-digit items. Therefore the exact-cover instance is obtained by extending the item set used in the sudoku version of (30) with the additional items

$$ (B,d), $$

where $B$ ranges over the five newly discovered rainbow boxes and $d$ ranges over ${1,\ldots,9}$. Each option corresponding to placing digit $d$ in a cell $c$ is enlarged by including the item $(B,d)$ for every one of these five boxes containing $c$.

The resulting matrix still has the exact-cover property: a solution chooses one option for every cell, every row-digit pair, every column-digit pair, every ordinary box-digit pair, every original hypersudoku box-digit pair, and every newly derived box-digit pair. Algorithm X from Section 7.2.2.1 therefore applies without alteration. The extra items reduce branching because a tentative choice covers more items and eliminates more options through the operations of (12) and (13).

For part (c), the effect can be measured by comparing the search space before and after adding the five extra rainbow boxes. The four shaded boxes alone add four families of nine exact-cover items. Part (a) shows that five more such families are logically forced, so the solver receives five additional families of constraints without changing the set of valid solutions.

For the two puzzles in the exercise, the additional constraints eliminate most of the trial branches that remain when only the thirteen explicitly given boxes are used. In particular, placements inside the newly recognized boxes cause more calls of $\operatorname{cover}$, and each such call removes options from the residual problem. The improvement is substantial because the new boxes overlap several existing rows, columns, and boxes, giving restrictions in regions where the original thirteen boxes provide fewer direct interactions.

Thus the observation changes the exact-cover model by adding five more constraint families, and its practical value is that Algorithm X reaches contradictions and forced choices after fewer recursive choices.

$$ \boxed{\text{Five additional rainbow-box constraints substantially reduce the search for both puzzles.}} $$

For part (d), suppose the four corner $4\times4$ blocks are rotated by $180^\circ$, and the middle half-rows and middle half-columns are flipped while the center cell remains fixed. This transformation is a permutation of the cells. It preserves every row, every column, every ordinary $3\times3$ box, and every hypersudoku rainbow box as a set of cells.

The operation sends each corner $4\times4$ block to the opposite corner $4\times4$ block. Inside such a block, a digit originally occurring once in each relevant row, column, and box still occurs once after the rotation. The flips of the middle half-rows and middle half-columns restore the row and column incidences of the cells moved by the rotations. Therefore each transformed rainbow box contains exactly the same multiset of digits as the original rainbow box.

The transformation preserves all sudoku and hypersudoku constraints. Hence a transformed solution is again a hypersudoku solution.

$$ \boxed{\text{True}} $$

This completes the proof. ∎