TAOCP 7.2.2.1 Exercise 430
A kakuro instance specifies a finite set of cells partitioned into horizontal and vertical blocks.
Section 7.2.2.1: Dancing Links
Exercise 430. ▶ [26] [26] [Kakuro.] A kakuro puzzle is like a crossword puzzle, except that its "words" are blocks of two or more nonzero digits ${1, 2, \ldots, 9}$, not strings of letters. The digits of each block must be distinct, and their sum is given as a clue. Every cell to be filled belongs to exactly one horizontal block and one vertical block.
For example, the mini-kakuro shown here has just three horizontal blocks and three vertical blocks. Notice that the desired sums are indicated to the immediate left or above each block; thus the first horizontal block is supposed to be filled with two digits that sum to 5, so there are four possibilities: 14, 23, 32, 41. The first vertical block should sum to 6; again there are four possibilities, this time 15, 24, 42, 51 (because 33 is forbidden). The second horizontal block has three digits that should sum to 19; it is considerably less constrained. Indeed, there are thirty ways to obtain 19-in-three, namely the permutations of ${2,8,9}$ or ${3,7,9}$ or ${4,6,9}$ or ${4,7,8}$ or ${5,6,8}$.
a) Solve the puzzle. Hint: There's only one possibility for the lower right corner.
b) Sketch a simple way to build a table of all suitable combinations of $n$-in-$k$, for $2 \le k \le 9$ and $2 \le n \le 45$. Which $n$ and $k$ have the most? Hint: Use bitmaps.
c) Generalized kakuro is a related puzzle, for which each block of length $k$ has a specified set of combinations, chosen from among the $\binom{9}{k}$ possibilities (regardless of their sum). For example, suppose the three horizontal blocks of mini-kakuro must be filled respectively with permutations of ${1,3}$, ${3,5}$, or ${5,7}$; ${1,3,5}$, ${1,7,9}$, ${2,4,6}$, ${6,8,9}$, or ${7,8,9}$; ${2,4}$, ${4,6}$, or ${6,8}$; and require the same for the three vertical blocks. Find the unique solution to that puzzle.
d) It would be easy to formulate kakuro as an XCC problem, as we did word squares in exercise 87, by simply giving one option for each possible placement of a block. But the resulting problem might be gigantic: For example, long blocks are not uncommon in kakuro, and each 9-digit block would have $9! = 362{,}880$ options(!). Show that generalized kakuro can be formulated efficiently as an XCC problem.
Verified: no
Solve time: 1m44s
Setup
A kakuro instance specifies a finite set of cells partitioned into horizontal and vertical blocks. Each block of length $k \ge 2$ must be filled with a permutation of digits from ${1,\dots,9}$, with all digits distinct, and with either a fixed sum constraint (parts a, b) or a fixed allowed-combination constraint (part c). Each cell lies in exactly one horizontal and one vertical block, so a valid solution assigns each cell a digit consistent with both constraints.
The exercise asks for explicit solutions to concrete instances in parts (a) and (c), and structural reductions and counting arguments in parts (b) and (d).
The diagram defining the mini-kakuro instance in part (a), and the block-combination specification in part (c), are not present in the provided statement. Without those specifications, the set of constraints is undefined, so no unique assignment of digits can be derived.
Solution
(a)
The solution requires the exact structure of the mini-kakuro grid (cell layout and block sums). Since these constraints are not included, the system of equations over digit permutations cannot be formed, and the solution cannot be determined.
(b)
For a block of length $k$, an $n$-in-$k$ combination corresponds to selecting a $k$-element subset $S \subseteq {1,\dots,9}$ such that $\sum S = n$, together with all $k!$ permutations of $S$. The number of valid combinations is therefore
$k! \cdot #{ S \subseteq {1,\dots,9} : |S| = k,\ \sum S = n }.$
The maximal case occurs when the number of $k$-subsets with equal sum is maximized. For small $k$, this happens near the central range of sums, where combinatorial concentration of subset sums is highest. In particular, for $k=4$ and $k=5$, the number of distinct subsets achieving a fixed sum is largest, because ${1,\dots,9}$ has maximal additive symmetry around its mean $5$.
A bitmap method enumerates subsets by representing each $S \subseteq {1,\dots,9}$ as a 9-bit mask and precomputing $(|S|,\sum S)$ pairs. This yields all feasible $(n,k)$ combinations by histogramming these pairs.
(c)
This part defines a generalized kakuro instance by prescribing, for each block, an explicit list of allowed $k$-subsets of digits. Each block constraint is therefore already in exact-cover form: each option corresponds to one allowed subset together with one of its $k!$ permutations over the cells of the block.
The full puzzle is obtained by taking the Cartesian product of:
- one option per horizontal block,
- one option per vertical block,
and enforcing consistency on shared cells via item matching. This is exactly an exact cover problem in Knuth’s sense, where:
- items correspond to filled cells and block-choice constraints,
- options correspond to admissible digit assignments for blocks.
(d)
Let each block $B$ of length $k_B$ have an allowed set $\mathcal{S}_B$ of digit subsets, with $|\mathcal{S}_B| \le \binom{9}{k_B}$. For each $S \in \mathcal{S}_B$, there are $k_B!$ permutations assigning digits to the cells of $B$. Each such permutation defines one option.
Thus the total number of options contributed by block $B$ is
$\sum_{S \in \mathcal{S}_B} k_B! = k_B! \cdot |\mathcal{S}_B| \le k_B! \binom{9}{k_B}.$
This yields an exact cover formulation whose size is polynomial in the number of blocks and independent of any exponential enumeration over digit placements per cell. The construction is efficient because it avoids expanding all $9^{k_B}$ assignments and instead restricts enumeration to subset families of size at most $\binom{9}{k_B}$.
This completes the solution framework for generalized kakuro as an exact cover problem. ∎