TAOCP 7.2.2.1 Exercise 403

The previous solution fails because it incorrectly restricts KenKen clues, ignores the need for a defined ordering of clues, and introduces an irrelevant Latin-square completion argument.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.1: Dancing Links

Exercise 403. ▶ [31] [31] Inspired by exercises 398(a) and 398(c), construct a valid $9 \times 9$ kenken puzzle whose clues exactly match the decimal digits of $\pi$, for as many places as you can.

Verified: no
Solve time: 5m13s

The previous solution fails because it incorrectly restricts KenKen clues, ignores the need for a defined ordering of clues, and introduces an irrelevant Latin-square completion argument. A correct approach must first fix the meaning of “clues match the digits of $\pi$” and then construct a legitimate KenKen instance under standard rules.

1. Correct interpretation of the problem

A $9\times 9$ KenKen puzzle consists of:

  • a $9\times 9$ grid filled with digits ${1,\dots,9}$,
  • a partition of the 81 cells into cages,
  • each cage having a target clue (an integer with an operation),
  • and a rule that the solution is the unique Latin square satisfying all cage constraints.

The exercise asks for a puzzle whose cage clues, read in a fixed natural order, match consecutive decimal digits of $\pi$ as long as possible.

We therefore fix the ordering:

Cages are listed in row-major order: left-to-right within each row, top-to-bottom across rows.

The sequence of cage clues is the list of clues of cages in this order.

2. Key correction: digits 0–9 are all valid clues

The previous solution incorrectly claimed that $0$ cannot be a KenKen clue.

This is false. KenKen clues are arbitrary integers produced by cage constraints. A clue may be $0$, for example via subtraction:

$$ a - a = 0. $$

More importantly, the clue is not restricted to being a cell value; it is a constraint on the cage.

Hence all decimal digits ${0,1,\dots,9}$ are admissible clues.

There is therefore no inherent obstruction to encoding all digits of $\pi$.

3. Construction of the puzzle

Let $\pi = 3.1415926535\ldots$ and let $d_k$ be its decimal digits.

Step 1: choose any Latin square solution

Construct any valid $9\times 9$ Latin square $L$ on symbols ${1,\dots,9}$. For example, the standard cyclic Latin square:

$$ L_{i,j} = (i+j-2 \bmod 9) + 1. $$

This ensures:

  • each row contains $1,\dots,9$ exactly once,
  • each column contains $1,\dots,9$ exactly once.

So $L$ is a valid KenKen solution grid.

Step 2: define cages

Make every cell its own cage. That is, each cage is the singleton:

$$ C_{i,j} = {(i,j)}. $$

Step 3: assign clues from $\pi$

Define the row-major enumeration of cells:

$$ (1,1),(1,2),\dots,(1,9),(2,1),\dots,(9,9). $$

Assign the clue of the $k$-th cage in this order to be:

$$ d_k. $$

Thus the cage clues are exactly:

$$ 3,1,4,1,5,9,2,6,5,\dots $$

for as many digits as available in $\pi$.

Since there are 81 cells, this encodes the first 81 decimal digits.

4. Validity of the KenKen puzzle

Solvability

The grid $L$ satisfies all cage constraints because each singleton cage simply fixes its cell value, and no contradiction arises.

Thus $L$ is a solution.

Uniqueness

Each cage is a singleton with a fixed required value equal to the value of $L$ at that cell. Therefore every cell is uniquely determined, so no alternative filling is possible.

Hence the solution is unique.

5. Matching with digits of $\pi$

By construction, the sequence of cage clues in row-major order is exactly:

$$ d_1,d_2,\dots,d_{81}, $$

the first 81 decimal digits of $\pi$ (including $0$ at position 32, which is allowed as a clue).

Thus the puzzle matches $\pi$ for 81 digits.

6. Optimality

A $9\times 9$ KenKen grid has exactly 81 cells, hence at most 81 cages if we use singleton cages. Since each cage contributes exactly one clue in the chosen ordering, no construction can produce more than 81 consecutive digits.

Therefore:

$$ \text{maximum possible match length} = 81. $$

7. What was corrected

  • The bound “31 digits” was based on the false claim that $0$ is not a valid clue.
  • The Latin square completion argument was unnecessary and incorrect.
  • The construction is simplified: no partial placement or greedy embedding is needed.
  • The correct maximal structure is achieved by using all 81 singleton cages with a fixed ordering.

Conclusion

A valid $9\times 9$ KenKen puzzle is obtained by taking any Latin square solution grid, partitioning into 81 singleton cages, and assigning cage clues in row-major order equal to the first 81 decimal digits of $\pi$. This achieves the maximum possible match length, since there are 81 cages in total.

$$ \boxed{\text{Maximum length } = 81.} $$