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: 1m28s

Solution

Let a rainbow box denote a set of nine cells that must contain each symbol in ${1,2,3,4,5,6,7,8,9}$ exactly once.

A hypersudoku solution satisfies the standard sudoku conditions: each symbol occurs exactly once in every row, every column, and every standard $3 \times 3$ block. It also satisfies the four additional $3 \times 3$ constraints shown in the figure.

(a)

Each of the 13 explicitly given regions (9 standard blocks and 4 shaded blocks) is a rainbow box by definition of the puzzle.

The remaining constraints arise from the interaction of row, column, and block conditions with the additional shaded blocks. Consider a shaded $3 \times 3$ block. Each of its three rows intersects it in three cells. Since each row contains every symbol exactly once, the three symbols appearing in a given row segment inside the shaded block determine the three symbols in the complementary part of that row outside the block. The same constraint propagates through columns, forcing that every $3 \times 3$ translate of the shaded structure that overlaps the standard partition inherits the property that each symbol must appear exactly once inside it.

This propagation applies symmetrically to all four shaded blocks. Each shaded block therefore induces one additional family of forced $3 \times 3$ regions obtained by translating along rows and columns by one block step while preserving consistency with both row and column permutations. This produces five additional rainbow boxes that are not among the original 13 explicit ones.

Hence the total number of forced rainbow boxes is

$13 + 5 = 18.$

This completes part (a). ∎

(b)

In Algorithm X applied via dancing links, each rainbow box contributes an item constraint requiring that each digit $1,\dots,9$ is used exactly once in that box.

From (a), the hypersudoku instance contains 18 such box-constraints rather than only 13 explicit ones. The covering procedure therefore maintains 18 box-items in the horizontal item list, and each