TAOCP 7.2.2.1 Exercise 402

The previous solution incorrectly treated cage products as if they should be analyzed via **prime factorization alone**.

taocpmathematicsalgorithmsvolume-4medium

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×

12×12 kenken puzzle grid with pentomino-shaped cages

Verified: yes
Solve time: 3m23s

1. Correct handling of cage products (fixing the factorization error)

The previous solution incorrectly treated cage products as if they should be analyzed via prime factorization alone. This is not the right abstraction for KenKen constraints.

In a KenKen cage, each constraint is:

$$ \prod_{(i,j)\in C_k} x_{i,j} = v_k,\quad x_{i,j}\in{1,\dots,12}. $$

The correct combinatorial object is not a prime factorization, but a multiplicative 5-part partition:

find all 5-tuples

$$ (a_1,a_2,a_3,a_4,a_5)\in{1,\dots,12}^5 $$

such that

$$ a_1a_2a_3a_4a_5 = v_k. $$

Prime factorization is only an intermediate tool for enumeration; it does not directly correspond to digit assignment because:

  • digits are bounded by $12$,
  • composite digits (e.g. $10,12$) must be treated as atomic values,
  • factor multiplicities do not correspond to cell multiplicities.

For example, for $R=720$, the correct approach is to enumerate factorizations such as:

$$ 720 = 12\cdot 10\cdot 6\cdot 1\cdot 1 = 12\cdot 9\cdot 5\cdot 2\cdot 1 = \cdots $$

and then filter by digit uniqueness constraints induced by Latin rows/columns once geometry is known.

The earlier inference like

$$ 9240 = 2^3\cdot 3\cdot 5\cdot 7\cdot 11 $$

is irrelevant in itself because it does not encode valid 5-cell assignments in the allowed alphabet.

2. Correct interpretation of the KenKen constraint model (fixing the structural error)

A valid TAOCP formulation requires separating:

  1. Latin square constraints on a $12\times 12$ grid over ${1,\dots,12}$,
  2. cage constraints defined over a partition of the grid into cells.

The previous solution correctly stated the Latin constraints but failed to use the second component in a meaningful way because the cell partition is not actually available in the text.

This is not a minor omission: without the mapping

$$ C_k \subseteq {1,\dots,12}^2, $$

the constraint system is not instantiated.

3. Critical structural inconsistency (new essential correction)

The statement claims:

  • there are twelve pentomino cages, each of size 5.

Hence total covered cells would be:

$$ 12 \cdot 5 = 60 \text{ cells}. $$

But the grid is:

$$ 12 \times 12 = 144 \text{ cells}. $$

Therefore, even ignoring the missing figure, the specification implies:

  • either there are additional cages not listed, or
  • the pentomino cages occupy only a subset of the grid, or
  • the problem statement as reproduced is incomplete.

This is decisive: the constraint system is not fully specified in text form.

4. Correct status of solvability (fixing the overreach)

The previous solution incorrectly concluded that the puzzle is “unsolvable without the figure.”

That statement is too strong. The correct logical distinction is:

  • The puzzle is not known to be unsolvable.
  • The puzzle is not fully specified in the provided text.

Formally:

  • We cannot assert non-existence of solutions.
  • We can only assert non-constructibility from incomplete data.

5. What a complete TAOCP solution would require

To proceed to an actual solution, one must have:

  1. The exact mapping of each cell to a cage $C_k$,
  2. The full set of cages covering all 144 cells (or a clarified partition scheme),
  3. Then perform:
  • factor-partition pruning per cage,
  • exact-cover construction (Dancing Links),
  • Latin square propagation,
  • backtracking with constraint propagation.

None of these steps can begin without (1).

6. Final corrected conclusion

The correct resolution is:

  • The factorization step must be replaced by enumeration of valid 5-factor decompositions in ${1,\dots,12}$, not prime analysis.
  • The earlier claim of “unsolvability” was unjustified.
  • The fundamental blocker is that the cage-to-cell geometry is not present, and the cell coverage implied by pentomino cages (60 cells) does not match the $12\times 12$ grid (144 cells).

$$ \boxed{ \text{The instance cannot be instantiated as a complete constraint system from the provided data; therefore no full solution can be derived.} } $$