TAOCP 7.2.2.1 Exercise 432

The missing “solution” failed because it never instantiated the diagrams, so we restart from the underlying combinatorial model of a Kakuro region: each white run is a sequence of distinct digits from...

taocpmathematicsalgorithmsvolume-4math-medium

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

Figure: Two generic kakuro diagrams labeled a) and b)

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: 3m14s

The missing “solution” failed because it never instantiated the diagrams, so we restart from the underlying combinatorial model of a Kakuro region: each white run is a sequence of distinct digits from ${1,\dots,9}$, and constraints couple runs only through shared cells.

The key experimental point in this exercise is not global structure but the non-injectivity of the map

$$ {\text{filled runs}} \longrightarrow {\text{run sums}}. $$

We analyze each generic diagram as the smallest coupled systems where this failure already appears.

Diagram (a)

The generic diagram (a) is the standard $2\times 2$ fully white block:

$$ \begin{matrix} a & b\ c & d \end{matrix} $$

with four runs:

  • rows: $(a,b)$, $(c,d)$
  • columns: $(a,c)$, $(b,d)$

1. Number of valid fillings

Constraints are exactly:

$$ a\neq b,\quad c\neq d,\quad a\neq c,\quad b\neq d. $$

No other restrictions exist.

Thus we are counting proper colorings of $K_{2,2}$ with 9 symbols:

$$ 9\cdot 8\cdot 7\cdot 6 = 3024. $$

So:

$$ N_a = 3024. $$

2. Reconstruction from sums

Each run is of length 2. A sum $s$ corresponds to unordered pairs ${x,y}\subset{1,\dots,9}$, $x<y$.

For length 2, the multiplicity of representations of a sum is:

  • unique only for $s=3$ (pair $1+2$)
  • unique only for $s=17$ (pair $8+9$)
  • all other sums have at least two representations

Hence a run sum determines its pair only in these two extreme cases.

To have a globally unique reconstruction from all four sums, every run would need to be uniquely determined as a pair. Thus all four runs would have to be either (\