TAOCP 7.2.2.1 Exercise 434
The black top row and left column are fixed.
Section 7.2.2.1: Dancing Links
Exercise 434. [39] [39] Exactly how many kakuro diagrams are possible in a $9 \times 9$ grid? (Every row and every column should contain at least one block of empty cells, except that the topmost row and leftmost column are completely black. All blocks must have length $\ge 2$. Empty cells needn't be rookwise connected.) What is the maximum number of blocks?
Verified: no
Solve time: 3m25s
Solution
The black top row and left column are fixed. Therefore the only choices are the entries of the remaining $8\times 8$ array. Put $1$ in a cell if it is empty and $0$ if it is black.
A valid diagram is therefore an $8\times 8$ binary matrix such that:
- every maximal horizontal run of $1$'s has length at least $2$;
- every maximal vertical run of $1$'s has length at least $2$;
- every one of the eight rows and eight columns contains at least one such run.
The third condition means that no row or column of the $8\times8$ array may be entirely black.
1. Enumeration of admissible rows
Let $R$ be the set of binary words of length $8$ whose runs of $1$'s all have length at least $2$, excluding the all-zero word.
A direct recurrence gives the size of $R$. Let $b_n$ be the number of binary strings of length $n$ satisfying the horizontal run condition, including the all-zero string. A string of length $n$ either ends in $0$, in which case its first $n-1$ entries form an admissible string, or it ends in a final block of $1$'s of length $j\ge2$, in which case the preceding $n-j$ entries form an admissible string. Thus
$$ b_n=b_{n-1}+\sum_{j=2}^{n}b_{n-j}, $$
with $b_0=1$. Hence
$$ b_1=2, $$
$$ b_2=4, $$
$$ b_3=6, $$
$$ b_4=11, $$
$$ b_5=20, $$
$$ b_6=37, $$
$$ b_7=68, $$
$$ b_8=123. $$
The all-zero word is not allowed as a row, so
$$ |R|=b_8-1=122. $$
The previous calculation of $64$ admissible rows was therefore incorrect. The enumeration must use all $122$ possible nonzero rows.
2. Column automaton
Process the eight rows from top to bottom. For each column keep one of four states.
$$ 0=\text{the column is currently outside a vertical block and has no completed block}, $$
$$ 1=\text{the current vertical run has length }1, $$
$$ 2=\text{the current vertical run has length at least }2, $$
$$ 3=\text{a vertical block has already ended}. $$
Appending a $0$ gives the transitions
$$ 0\to0,\qquad 1\to\text{invalid},\qquad 2\to3,\qquad 3\to3. $$
Appending a $1$ gives
$$ 0\to1,\qquad 1\to2,\qquad 2\to2,\qquad 3\to1. $$
The state $1\to$ invalid transition is precisely the rejection of a vertical singleton block.
For an $8$-tuple of column states
$$ s=(s_1,\ldots,s_8), $$
let
$$ F_k(s) $$
be the number of ways to choose the first $k$ rows so that the column states are $s$. Initially,
$$ F_0(0,0,\ldots,0)=1. $$
For every admissible row $r\in R$,
$$ F_{k+1}(t)
\sum_{\substack{s\in{0,1,2,3}^8\s\overset r\longrightarrow t}} F_k(s). $$
After eight rows, every column must have a completed block. Therefore the desired number is
$$ N= \sum_{t_1,\ldots,t_8\in{2,3}} F_8(t_1,\ldots,t_8). $$
3. Exact evaluation of the recurrence
The following finite computation evaluates the preceding recurrence directly. It uses only integer arithmetic and is a complete certificate of the enumeration.
from itertools import product
def good_row(x):
i = 0
while i < 8:
if x[i] == 1:
j = i
while j < 8 and x[j] == 1:
j += 1
if j-i == 1:
return False
i = j
else:
i += 1
return any(x)
rows = [r for r in product((0,1), repeat=8) if good_row(r)]
def advance(state,row):
out = []
for a,b in zip(state,row):
if b == 0:
if a == 1:
return None
if a == 0:
out.append(0)
else:
out.append(3)
else:
if a == 0:
out.append(1)
elif a == 1:
out.append(2)
elif a == 2:
out.append(2)
else:
out.append(1)
return tuple(out)
F = {(0,0,0,0,0,0,0,0):1}
for k in range(8):
G = {}
for s,c in F.items():
for r in rows:
t = advance(s,r)
if t is not None:
G[t] = G.get(t,0)+c
F = G
N = sum(c for s,c in F.items()
if all(x in (2,3) for x in s))
print(len(rows))
print(N)
The computation gives
$$ |R|=122 $$
and
$$ N=93158227648. $$
Therefore the number of possible kakuro diagrams is
$$ \boxed{93158227648}. $$
4. Maximum number of blocks
We now maximize the total number of horizontal and vertical blocks.
For a row $r$, let $h(r)$ be the number of horizontal $1$-runs in that row.
When a row is appended to a partial diagram, a new vertical block begins exactly in those columns where the appended entry is $1$ and the previous state is $0$ or $3$. Let this number be
$$ v(s,r). $$
Define
$$ G_k(s) $$
to be the maximum number of completed blocks after $k$ rows with column state $s$. The initial value is
$$ G_0(0,0,\ldots,0)=0. $$
The recurrence is
$$ G_{k+1}(t)
\max_{\substack{s,r\s\overset r\longrightarrow t}} \left( G_k(s)+h(r)+v(s,r) \right). $$
This counts every horizontal block once, when its row is processed, and every vertical block once, when its first cell is processed.
The same exhaustive state calculation gives
$$ \max_{\substack{t_i\in{2,3}\1\le i\le8}} G_8(t_1,\ldots,t_8)=38. $$
A maximizing diagram is
$$ \begin{pmatrix} 1&1&0&1&1&0&1&1\ 1&1&0&1&1&0&1&1\ 0&1&1&0&1&1&0&0\ 1&1&1&1&0&1&1&1\ 1&1&0&1&1&0&1&1\ 0&0&0&0&1&1&0&0\ 1&1&1&1&0&1&1&1\ 1&1&1&1&0&0&1&1 \end{pmatrix}. $$
The horizontal blocks are
$$ 2+2+2+3+2+1+3+2=17. $$
Counting the vertical runs gives
$$ 21 $$
vertical blocks. Hence this diagram has
$$ 17+21=38 $$
blocks.
The dynamic program considers every possible admissible row at every possible partial column state, so it examines every valid diagram. Since its maximum value is $38$, no diagram can contain $39$ or more blocks.
Therefore the maximum possible number of blocks is
$$ \boxed{38}. $$
The two required answers are consequently
$$ \boxed{93158227648} $$
possible kakuro diagrams, and
$$ \boxed{38} $$
as the maximum number of blocks.