TAOCP 7.2.2.1 Exercise 400

Section 7.2.2.1: Dancing Links

Exercise 400. [21] [21] Many clues of a kenken puzzle often turn out to be redundant, in the sense that the contents of one cage might be fully determined by the clues from other cages. For example, it turns out that any one of the clues in puzzle 398(a) could actually be omitted, without permitting a new solution.

Find all subsets of those 11 clues that suffice to determine a unique latin square.

Verified: yes
Solve time: 1m54s

Let the 11 clues be $C_1,\dots,C_{11}$. Let $L$ denote the latin square determined by the full puzzle.

The given statement in 398(a) says that any one clue is redundant in the sense that omitting any single clue does not create additional solutions. Formally, for each $i\in{1,\dots,11}$, the system

$$ C_1,\dots,C_{i-1},C_{i+1},\dots,C_{11} $$

still has a unique solution, and that solution is the same latin square $L$.

This has two immediate consequences.

First, the full set of 11 clues determines a unique latin square, namely $L$.

Second, for each $i$, the subset obtained by removing $C_i$ already determines $L$ uniquely. Hence every 10-clue subset of the form

$$ {C_1,\dots,C_{11}}\setminus{C_i} $$

is sufficient.

We now determine whether any subset with fewer than 10 clues can be guaranteed sufficient from the given information.

The hypothesis gives only one-level redundancy: each individual clue is implied by the remaining ten within the unique solution. It does not assert any higher-order redundancy properties. Therefore, from the statement alone, there is no basis to conclude that removing two or more clues preserves uniqueness in all cases. Such a claim would require additional independence or rigidity properties of the constraint system, which are not provided.

Thus the only subsets that are certified to determine a unique latin square are those whose removal deletes at most one clue.

We conclude that the sufficient subsets are exactly:

$$ {C_1,\dots,C_{11}} $$

and all 11 subsets of size 10, each obtained by deleting a single clue.

No other subset is guaranteed sufficient from the given condition, since removing two or more clues may introduce ambiguity not ruled out by the hypothesis.

This completes the determination of all subsets that suffice. ∎