TAOCP 7.2.2.1 Exercise 430

The supplied statement does not include the two diagrams referred to in parts (a) and (c).

taocpmathematicsalgorithmsvolume-4hard

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: 2m44s

Solution

The supplied statement does not include the two diagrams referred to in parts (a) and (c). Those diagrams specify the incidence structure of the horizontal and vertical blocks. Without them, the actual cell values cannot be determined. Parts (b) and (d), however, are independent of the missing figures and can be solved completely.

(a) Mini-kakuro

The diagram of the mini-kakuro is required. The text gives only examples of possible combinations, not the locations of the six blocks or their intersections. Consequently, the unique filling cannot be reconstructed from the supplied statement alone.

(b) Table of all $n$-in-$k$ combinations

A block of length $k$ is determined by a subset of $k$ distinct digits chosen from

$$ {1,2,\ldots,9}. $$

The order of the digits in the block does not matter when generating the possible digit sets, because all permutations of a valid set are allowed later.

A convenient representation is a bitmap of length $9$. Bit $i$ is $1$ exactly when digit $i$ occurs in the set. Thus every subset of the nine digits has a unique bitmap.

For each $k$, generate all bitmaps having exactly $k$ bits set. For each bitmap $B$, compute

$$ n=\sum_{i=1}^{9} i b_i , $$

where $b_i$ is the $i$-th bit of $B$. Store $B$ in the table entry indexed by $(n,k)$.

There are only

$$ \sum_{k=2}^{9}\binom{9}{k}=502 $$

such subsets, so the entire table is very small. A bitmap representation also makes testing whether a digit belongs to a combination a single bit operation.

The number of combinations in each entry is

$$ N(n,k)= #\left{ S\subseteq{1,\ldots,9}: |S|=k,\ \sum_{x\in S}x=n \right}. $$

Enumerating the $502$ possible subsets gives the largest value

$$ \max_{n,k}N(n,k)=12. $$

The maximum occurs for

$$ (n,k)=(20,4). $$

Thus there are twelve distinct four-digit sets whose digits sum to $20$. For example,

$$ {1,2,8,9},\quad {1,3,7,9},\quad {1,4,6,9}, $$

and so on, give the possible entries in that table position.

(c) Generalized kakuro instance

The diagram specifying the block intersections is missing from the supplied statement. The lists of allowed digit sets alone do not determine which horizontal and vertical blocks meet at which cells. Therefore the unique solution cannot be recovered.

(d) Efficient XCC formulation of generalized kakuro

The naive XCC formulation uses one option for every possible filling of an entire block. A block of length $k$ could then require as many as

$$ k! $$

options for a single allowed digit set, which is wasteful. Instead, introduce one option for each assignment of a single digit to a single cell.

Let $c$ be a cell. Let $H(c)$ and $V(c)$ denote its horizontal and vertical blocks.

For each cell $c$, digit $d$, horizontal allowed set $A$, and vertical allowed set $B$, where

$$ d\in A,\qquad d\in B, $$

create one XCC row representing the choice

$$ c=d. $$

This row covers the following items.

  1. The primary column

$$ \text{cell }c, $$

which guarantees that every cell receives exactly one digit.

  1. A colored column for the horizontal block $H(c)$, with color $A$.
  2. A colored column for the vertical block $V(c)$, with color $B$.

The color mechanism requires all rows that cover the same block column to have the same color. Hence all cells in a block must select the same allowed digit set.

To enforce that digits do not repeat inside a block, add secondary columns

$$ (H,d),\qquad (V,d) $$

for every block and every digit $d\in{1,\ldots,9}$. A row covering a cell with digit $d$ also covers the corresponding secondary columns. Since secondary columns may be covered at most once, no block can contain the same digit twice.

Therefore a valid XCC solution has the following properties:

  • every cell column is covered once, so every cell is assigned a digit;
  • all rows belonging to a block use one common color, so the chosen digits form one allowed combination;
  • the secondary digit columns prevent repetitions inside a block.

The number of rows is proportional to the number of cells times the number of allowed digit choices containing those digits. It is not proportional to

$$ 9!, $$

or to the number of permutations of every block. Hence generalized kakuro has an efficient XCC formulation.