TAOCP 7.2.2.1 Exercise 402

Section 7.2.2.1: Dancing Links

Exercise 402. [24] [24] Solve this $12 \times 12$ kenken puzzle, using hexadecimal digits from 1 to C:

The five-cell cages that play multiplicative clues, associated with the names of the twelve pentominoes:

O,  9240×
P,  5184×
Q,  1638×
R,  720×
S,  15840×
T,  19800×
U,  10560×
V,  4032×
W,  1620×
X,  5600×
Y,  576×
Z,  17248×

Verified: no
Solve time: 2m19s

Solution

The exercise refers to a $12\times12$ KenKen puzzle whose cage layout is given in a figure. The supplied material does not contain that figure or an equivalent description of the cage coordinates. Therefore the puzzle constraints are not completely specified, and a completed Latin square cannot be derived from the data provided.

The information that is available is only the list of multiplicative clues:

$$ \begin{array}{c|c} \text{pentomino cage} & \text{product}\ \hline O&9240\ P&5184\ Q&1638\ R&720\ S&15840\ T&19800\ U&10560\ V&4032\ W&1620\ X&5600\ Y&576\ Z&17248 \end{array} $$

Each cage contains five cells and corresponds to one of the twelve pentomino shapes. The products constrain only the values occurring in those five cells. A KenKen solution, however, also requires the positions of those cells, because the Latin-square conditions are imposed on rows and columns:

$$ {1,2,\ldots,C} $$

must occur exactly once in every row and every column, where $C$ denotes the hexadecimal digit $C=12$.

The cage products alone do not determine which row and column restrictions interact with each product. For example, the clue

$$ 9240=2^3\cdot3\cdot5\cdot7\cdot11 $$

only implies that the five cells of cage $O$ contain digits whose product is $9240$. It gives no information about which rows or columns contain those digits. The same multiset of five digits can impose very different restrictions depending on the cage placement.

The pentomino names $O,P,\ldots,Z$ also do not resolve this ambiguity. A pentomino name identifies a shape, but not its position or orientation in the $12\times12$ board. Without the figure, there is no way to know whether a particular pentomino occupies, for example,

$$ {(1,1),(1,2),(2,1),(2,2),(3,1)} $$

or some translated or rotated copy elsewhere in the board. These alternatives lead to different row and column constraints and therefore to different KenKen instances.

Consequently, a valid solution of Exercise 7.2.2.1.402 requires the missing cage layout. Once the figure is supplied, the puzzle can be solved by imposing:

1. the Latin-square constraints on the $12\times12$ array;
2. the five-cell product constraint for each pentomino cage;
3. the hexadecimal digit condition that each entry belongs to

$$ {1,2,\ldots,9,A,B,C}. $$

The completed array can then be checked by verifying every row, every column, and all twelve cage products.

With only the twelve products and the pentomino names, there is no uniquely determined puzzle to solve, so no completed Latin square can be rigorously supplied. The missing figure or a coordinate list for the twelve cages is necessary.