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: yes
Solve time: 1m12s

Solution

A KenKen puzzle on an $n\times n$ grid defines variables $x_{ij}\in{1,\dots,n}$ subject to Latin constraints (all rows and columns are permutations) and cage constraints (each cage satisfies a fixed arithmetic condition).

The problem is reduced to an exact cover instance in the sense of Section 7.2.2.1 by constructing items and options so that every valid grid corresponds to a disjoint family of options covering all items exactly once.

The item set consists of three kinds of requirements. For each cell $(i,j)$ there is an item $(i,j)$ requiring that the cell be filled once. For each row $i$ and value $v$ there is an item $(i,v)$ requiring that value $v$ appears exactly once in row $i$. For each column $j$ and value $v$ there is an item $(j,v)$ requiring that value $v$ appears exactly once in column $j$. For each cage $k$ there is an item $K_k$ requiring that the cage constraint is satisfied exactly once.

An option corresponds to a complete local realization of a cage. Let cage $k$ consist of cells $(i_1,j_1),\dots,(i_t,j_t)$. An option for $k$ is a choice of values $(x_{i_1 j_1},\dots,x_{i_t j_t})$ such that the multiset of values satisfies the arithmetic condition of the cage. Each such assignment induces an option consisting of all items enforced by that assignment: the cell items $(i_\ell,j_\ell)$ for $1\le \ell\le t$, the row-value items $(i_\ell,x_{i_\ell j_\ell})$, the column-value items $(j_\ell,x_{i_\ell j_\ell})$, and the single cage item $K_k$.

Every option therefore covers exactly one cage item, exactly one cell item for each cell in the cage, and contributes the corresponding row and column value constraints. Distinct options for the same cage differ by at least one assigned value, so they differ in at least one row-value or column-value item.

A selection of options is a solution of the exact cover instance if and only if every item is covered exactly once. The Latin constraints are enforced because for fixed $i$ and $v$, the item $(i,v)$ can be covered only once, so $v$ appears at most once in row $i$; similarly for columns. Each cell item $(i,j)$ is covered exactly once, so every cell receives exactly one value. Each cage item $K_k$ is covered exactly once, so exactly one admissible assignment is chosen for each cage, ensuring the arithmetic condition is satisfied.

Conversely, any valid KenKen solution assigns to each cage $k$ a unique admissible assignment, producing one option per cage. These options are disjoint on cell items because each cell receives a single value, and they collectively cover every row, column, and cage item exactly once. Hence they form an exact cover.

Running Algorithm C on this exact cover formulation generates all disjoint families of options covering all items. By the correspondence above, each such family is in one-to-one correspondence with a complete KenKen solution. Therefore Algorithm C enumerates all solutions of the given KenKen puzzle, and every solution arises from exactly one search branch that covers all items and terminates when no items remain.

This completes the proof. ∎