TAOCP 7.2.2.1 Exercise 432

Section 7.2.2.1: Dancing Links

Exercise 432. ▶ [M25] We can't design new kakuro puzzles by randomly filling the blanks and using the resulting sums as the constraints, because the vast majority of possible sums yield nonunique solutions. Verify this experimentally for the generic diagrams

In each case determine the exact number of ways to fill the blanks, without repeated digits in any row or column, as well as exactly how many of those filled-in diagrams are uniquely reconstructible from their block sums. Consider also symmetry.

Verified: no
Solve time: 1m51s

---

Solution

The numerical answer depends on the two diagrams in Figure 432. The figure is not included in the problem data provided here, so the cell adjacencies and block structure are unknown. Consequently, the exact numerical counts cannot be derived from the statement alone. A correct solution must begin with the actual diagrams.

The required computation can nevertheless be specified completely.

For a given kakuro diagram, let $C$ be the set of blank cells. A filling is a function

$$ f:C\longrightarrow {1,2,\ldots,9}. $$

The legality conditions are that every maximal horizontal block and every maximal vertical block contains no repeated digit. Thus, for every block $B$,

$$ f(c_1),f(c_2),\ldots,f(c_k) $$

must be pairwise distinct for the cells $c_i\in B$.

1. Counting all legal fillings

The number of legal fillings is obtained by exhaustive backtracking over the cells.

Choose an ordering

$$ C={c_1,c_2,\ldots,c_n}. $$

At step $i$, assign a digit to $c_i$ from the set

$$ {1,\ldots,9}\setminus \left( {\text{digits already used in the horizontal block of }c_i} \cup {\text{digits already used in the vertical block of }c_i} \right). $$

Whenever a complete assignment is reached, increment the count. Because every assignment is tested against exactly the row and column restrictions, this gives precisely the number of legal fillings.

Equivalently, this is a graph-coloring count. Construct the conflict graph whose vertices are the blank cells, with an edge joining two cells whenever they occur in a common horizontal or vertical block. A legal filling is then a proper coloring of this graph with colors $1,\ldots,9$.

2. Determining which fillings are uniquely reconstructible

For each legal filling $f$, compute its block sums. If the horizontal and vertical blocks are denoted by

$$ B_1,B_2,\ldots,B_m, $$

form the sum vector

$$ s(f)= \left( \sum_{c\in B_1}f(c), \sum_{c\in B_2}f(c), \ldots, \sum_{c\in B_m}f(c) \right). $$

Now enumerate all legal fillings and group them according to their sum vectors.

A filling $f$ is uniquely reconstructible exactly when its sum vector occurs once:

$$ #{g:s(g)=s(f)}=1. $$

Therefore, if $N$ is the total number of legal fillings and $U$ is the number of fillings whose sum vectors have multiplicity one, the desired percentage of randomly generated puzzles that are uniquely solvable is

$$ \frac{U}{N}. $$

The exercise asks for $N$ and $U$ for each of the two diagrams.

3. Symmetry considerations

The symmetry group of a diagram acts on its fillings. If a permutation $\sigma$ of the cells preserves all horizontal and vertical blocks, then

$$ (\sigma f)(c)=f(\sigma^{-1}(c)) $$

is another legal filling with the same structural position.

The group action partitions fillings into symmetry orbits. When two fillings lie in the same orbit, they represent the same configuration up to diagram symmetry. Therefore the enumeration may be reduced by selecting one representative from each orbit, using Burnside's lemma if the number of symmetry classes is required.

For uniqueness testing, however, symmetry must be handled carefully. A solution is unique only relative to the labeled diagram. If a nontrivial symmetry maps one filling to another filling with the same block sums, those fillings must be counted as different unless the exercise explicitly identifies symmetric solutions.

4. Required data

To complete the numerical part of the exercise, Figure 432 must be supplied. From the two diagrams one can then compute:

$$ N_a,\quad U_a $$

for diagram (a), and

$$ N_b,\quad U_b $$

for diagram (b), by the enumeration procedure above. The missing figure is therefore essential input to the requested experimental verification, and no exact numerical counts can be justified without it.