TAOCP 7.2.2.1 Exercise 447
We restart from the definitions.
Section 7.2.2.1: Dancing Links
Exercise 447. [22] (Johan de Ruiter.) Are there any values of $m > 1$ and $n > 1$ for which the first $mn$ digits of $\pi$ define a valid $m \times n$ hitori puzzle?
Verified: yes
Solve time: 3m27s
We restart from the definitions.
A Hitori puzzle consists of an $m \times n$ grid filled with positive integers. One must mark some cells black such that the following conditions hold for the remaining white cells:
First, in every row and in every column, no integer appears more than once among the white cells. Second, no two black cells are orthogonally adjacent. Third, all white cells form a single connected region under orthogonal adjacency.
In the construction in the exercise, the grid is formed by taking the first $mn$ decimal digits of $\pi$ and placing them row by row into an $m \times n$ array.
We are asked whether there exist $m>1$ and $n>1$ such that this specific grid admits a valid Hitori solution.
The key point is that existence only requires producing one valid pair $(m,n)$, not showing that all grids work.
We take $m=n=2$. The first four digits of $\pi$ are
$$ 3,\ 1,\ 4,\ 1. $$
So the grid is
$$ \begin{matrix} 3 & 1 \ 4 & 1 \end{matrix}. $$
We now show this grid admits a valid Hitori marking.
The only violation of the row and column uniqueness rule occurs in the second column, which contains two copies of $1$. To fix this, at least one of these two cells must be black. We choose to mark the top-right cell $(1,2)$ black and leave all other cells white.
The resulting configuration is:
$$ \begin{matrix} 3 & \blacksquare \ 4 & 1 \end{matrix} $$
with white cells at $(1,1)$, $(2,1)$, and $(2,2)$.
Now we verify the Hitori conditions.
In each row and column, the white entries are all distinct. Row 1 has only $3$. Row 2 has $4$ and $1$, which are distinct. Column 1 has $3$ and $4$, which are distinct. Column 2 has only $1$, so there is no repetition.
No two black cells are adjacent, since there is exactly one black cell.
Finally, the white cells form a connected region: $(1,1)$ is adjacent to $(2,1)$, which is adjacent to $(2,2)$, so all white cells lie in a single connected component.
All Hitori conditions are satisfied, so this is a valid solution.
Therefore, there do exist values $m>1$ and $n>1$ such that the first $mn$ digits of $\pi$ define a valid Hitori puzzle, and one such pair is $m=n=2$.