TAOCP 7.2.2.1 Exercise 399

Exercise 399. ▶ [22] [22] How can all solutions to a kenken puzzle be obtained with Algorithm C?

Verified: no
Solve time: 1m50s

Solution

Algorithm C can be applied after converting the KenKen puzzle into an exact cover problem. The conversion must incorporate both the Latin square conditions and the arithmetic restrictions imposed by the cages.

Let the order of the KenKen puzzle be $n$. Introduce three kinds of items. For every cell $(r,c)$, introduce a cell item

$$ C_{r,c}. $$

For every row $r$ and value $v\in{1,\ldots,n}$, introduce a row-value item

$$ R_{r,v}. $$

For every column $c$ and value $v\in{1,\ldots,n}$, introduce a column-value item

$$ K_{c,v}. $$

A choice of an option in the exact cover problem will correspond to filling an entire cage, not merely assigning one value to one cell. Suppose a cage contains cells

$$ (r_1,c_1),\ldots,(r_t,c_t). $$

For each assignment

$$ (v_1,\ldots,v_t)\in{1,\ldots,n}^{t} $$

that satisfies the arithmetic condition of the cage, create one option. This option contains the items

$$ C_{r_1,c_1},\ldots,C_{r_t,c_t}, $$

together with

$$ R_{r_1,v_1},\ldots,R_{r_t,v_t}, $$

and

$$ K_{c_1,v_1},\ldots,K_{c_t,v_t}. $$

Thus every legal filling of a cage is represented by exactly one option.

The exact cover instance has the property that every item must be covered exactly once. A cover of all the cell items guarantees that every cell receives a value. A cover of all row-value items guarantees that each value $v$ occurs exactly once in every row. A cover of all column-value items guarantees that each value $v$ occurs exactly once in every column. Hence every exact cover gives a Latin square satisfying every cage condition.

Conversely, suppose a completed KenKen solution is given. Each cage has a definite assignment of values to its cells, and that assignment satisfies the cage arithmetic condition. The corresponding option was included in the construction. Choose that option for every cage. Since every cell has exactly one value, every cell item occurs exactly once. Since each row of the Latin square contains every value once, every row-value item occurs exactly once. Since each column contains every value once, every column-value item occurs exactly once. Therefore these options form an exact cover.

The two constructions are inverse: every exact cover determines a completed KenKen solution, and every completed KenKen solution determines an exact cover. Algorithm C enumerates all exact covers, so applying it to this exact cover instance enumerates all solutions of the KenKen puzzle.

This completes the proof.

∎