TAOCP 7.2.2.1 Exercise 434

Let the $9\times 9$ kakuro diagram be represented by a binary matrix $(x_{ij})$, where $x_{ij}=1$ denotes a white cell (empty cell) and $x_{ij}=0$ denotes a black cell.

taocpmathematicsalgorithmsvolume-4project

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: 59s

Setup

Let the $9\times 9$ kakuro diagram be represented by a binary matrix $(x_{ij})$, where $x_{ij}=1$ denotes a white cell (empty cell) and $x_{ij}=0$ denotes a black cell. The problem fixes the boundary conditions

$x_{1j}=0 \ (1\le j\le 9), \qquad x_{i1}=0 \ (1\le i\le 9),$

so the free variables are exactly the $8\times 8$ submatrix $(x_{ij})_{2\le i,j\le 9}$, hence $64$ independent bits.

A horizontal block of empty cells of length at least $2$ in row $i$ is a pair $(j,j+1)$ such that $x_{ij}=x_{i,j+1}=1$. Thus row $i$ satisfies the condition if and only if

$\bigvee_{j=2}^{8} (x_{ij}=1 \wedge x_{i,j+1}=1).$

Similarly, column $j$ satisfies the condition if and only if

$\bigvee_{i=2}^{8} (x_{ij}=1 \wedge x_{i+1,j}=1).$

Let $A_i$ denote the event that row $i$ has no horizontal pair $11$ for $2\le i\le 9$, and let $B_j$ denote the event that column $j$ has no vertical pair $11$ for $2\le j\le 9$. The required diagram