TAOCP 7.2.2.1 Exercise 401

Section 7.2.2.1: Dancing Links

Exercise 401. [22] [22] Find all $4 \times 4$ kenken puzzles whose unique solution is the latin square shown at the right, and whose clues belong to two cells. Furthermore, there should be exactly two cages for each of the four operations $+, -, \times, \div$.

$$\begin{matrix} 1 & 2 & 3 & 4 \ 2 & 1 & 4 & 3 \ 4 & 3 & 1 & 2 \ 3 & 4 & 2 & 1 \end{matrix}$$

Verified: no
Solve time: 4m15s

The previous argument fails because a 2-cell KenKen cage does not determine a unique unordered pair of values. The corrected solution must therefore rebuild the reasoning from the actual constraint semantics.

1. Correct meaning of a 2-cell cage

Let a cage consist of two cells $\alpha,\beta$. In the solution Latin square $L$, these contain values

$$ (L(\alpha),L(\beta)) = (a,b). $$

A cage is given by an operation and a target computed from $(a,b)$. In a candidate filling $X$, the cage is satisfied if the values $(x,y)$ in its two cells satisfy the same operation constraint and yield the same target.

Crucially, the constraint defines a set of admissible unordered pairs, not a single pair. For example:

$$ \text{sum } 5 \Rightarrow {1,4}, {2,3}. $$

Thus a cage induces a binary relation on ${1,2,3,4}$, not a fixed assignment.

2. Global structure of the problem

We fix:

a partition of the 16 cells into 8 disjoint 2-cell cages,
each cage labeled by one of $+, -, \times, \div$, with each label used exactly twice,
each cage assigned the target induced by the given Latin square $L$.

This produces a constraint system $P$ on fillings of the grid.

A valid solution is a Latin square $X$ satisfying all cage constraints.

We must characterize all $P$ such that:

$L$ satisfies $P$,
$L$ is the unique Latin square satisfying $P$.

3. Reformulation as elimination of competing Latin squares

Let $\mathcal{L}$ be the set of all $4\times 4$ Latin squares on symbols ${1,2,3,4}$.

Each cage constraint removes some Latin squares from $\mathcal{L}$. Therefore the puzzle corresponds to

$$ \mathcal{L}(P) \subseteq \mathcal{L}. $$

We require:

$$ \mathcal{L}(P) = {L}. $$

Thus a valid puzzle is exactly a constraint system whose induced filtering leaves only $L$.

This already shows the earlier “independent cage” decomposition is invalid: cages interact through the global Latin property.

4. Structure of alternative Latin squares

The given Latin square is

$$ L_{ij} = i \oplus j $$

where $\oplus$ is the Klein four-group operation. Hence all Latin squares isotopic to $L$ arise by:

permuting rows,
permuting columns,
permuting symbols via an automorphism of the Klein group,
composing these operations.

There are 576 Latin squares of order 4, all isotopic to this group table.

Thus uniqueness means: the cage system must eliminate all nontrivial isotopisms.

5. Effect of a single cage

A cage on cells ${\alpha,\beta}$ forbids certain pairs $(x,y)$ inconsistent with its operation/target.

Hence each cage imposes a constraint of the form:

$$ (X_\alpha, X_\beta) \in S_c $$

for some subset $S_c \subseteq {1,2,3,4}^2$ symmetric under swapping coordinates.

Unlike the flawed argument, $S_c$ is typically not a singleton.

Therefore:

cages do not determine values,
cages only restrict possibilities,
interaction among cages is essential for uniqueness.

6. Correct characterization of all valid puzzles

We now describe all constructions that satisfy the problem conditions.

Construction

A valid puzzle is obtained by:

Choosing any partition of the 16 cells into 8 disjoint unordered pairs.
Assigning to each pair one operation $+, -, \times, \div$, with each used exactly twice.
Assigning to each cage the target induced by $L$.

This defines a constraint system $P$.

Validity condition

Such a construction is valid if and only if it isolates $L$ among all Latin squares, i.e.

$$ \mathcal{L}(P) = {L}. $$

Equivalently:

Every Latin square $X \neq L$ violates at least one cage constraint.

7. What replaces the false “decoupling” argument

The earlier proof incorrectly assumed:

$$ \text{cage} \Rightarrow \text{fixed pair}. $$

The correct replacement is:

each cage defines a constraint relation on pairs,
the full puzzle is the intersection of these relations with the Latin square conditions,
uniqueness is a global property, not a local one.

Thus there is no structural simplification beyond constraint satisfaction over $\mathcal{L}$.

8. Final answer

All valid KenKen puzzles satisfying the conditions are exactly those obtained as follows:

Choose a partition of the 16 cells into 8 unordered pairs, assign to the pairs the operations $+, -, \times, \div$ with each used exactly twice, and assign each cage the target computed from the given Latin square $L$.

Such a construction yields a valid puzzle if and only if the resulting constraint system has a unique Latin square solution, namely $L$. Equivalently, the intersection of all Latin squares satisfying the cage constraints is the singleton set ${L}$.

No simpler decomposition into independent cages is valid, since each cage admits multiple compatible value-pairs and interacts with all others through the Latin square constraints. ∎