TAOCP 7.2.2.1 Exercise 60

Exercise 7.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.1: Dancing Links

Exercise 60. [30] [30] (The Puzzlium Sudoku ABC.) Complete these hexomino-shaped boxes:

Figure 60: Three hexomino-shaped sudoku puzzles labeled (a), (b), (c)

Verified: no
Solve time: 2m17s

Setup

Exercise 7.2.2.1.60 requires the three specific hexomino Sudoku instances shown in Figure 60. A complete solution depends on two kinds of input data from that figure:

  1. The initial entries (the given digits).
  2. The partition of the cells into the hexomino-shaped regions.

Neither the given digits nor the region layouts are present in the supplied material. The text description alone,

$$ \text{“Complete these hexomino-shaped boxes”}, $$

does not determine a unique Sudoku instance.

For a hexomino Sudoku, a solution is a $6\times 6$ array of digits satisfying:

  • every row contains each digit exactly once,
  • every column contains each digit exactly once,
  • every hexomino region contains each digit exactly once,
  • all given digits are preserved.

The missing figure is therefore part of the formal specification of the problem.

Solution

The three completed grids cannot be derived from the information provided. Any proposed grids would necessarily introduce assumptions about the missing region shapes or clues and would not constitute a solution to Exercise 7.2.2.1.60.

To solve the exercise, the data from Figure 60 must first be transcribed. Once the three diagrams are available, each puzzle can be represented as an exact-cover problem with constraints for:

$$ \text{cell occupancy},\qquad \text{row-digit pairs},\qquad \text{column-digit pairs},\qquad \text{hexomino-digit pairs}. $$

Solving the resulting exact-cover instances yields the completed Sudoku grids.

Verification

No verification can be performed because no candidate grids have been obtained. In particular, there is no way to check:

$$ \forall r,\quad {x_{r,1},\ldots,x_{r,6}}={1,\ldots,6}, $$

$$ \forall c,\quad {x_{1,c},\ldots,x_{6,c}}={1,\ldots,6}, $$

or the corresponding condition for each hexomino region.

Notes

The previous response was incomplete as a solution to the exercise because it stopped at identifying the missing input. That observation was correct, but the actual computation of the three completions requires Figure 60. A complete corrected solution is therefore conditional on receiving the figure or an equivalent transcription of the three puzzles.