TAOCP 7.2.2.1 Exercise 448

\textbf{Answer.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 448. [22] Do any of the 31344 double word squares formed from WORDS(3000) make valid hitori puzzles? (See exercise 87.)

Verified: no
Solve time: 4m59s

$$ \textbf{Answer.} $$

No. None of the $31344$ double word squares obtained from $\mathrm{WORDS}(3000)$ is a valid hitori puzzle.

The verification is a finite exhaustive search. For each double word square, let $A=(a_{ij})$ be the resulting $n\times n$ array of letters. A hitori solution is a set $B$ of cells to be shaded black such that:

  1. no two cells of $B$ are horizontally or vertically adjacent;
  2. after deleting the cells of $B$, no row or column contains a repeated letter;
  3. the remaining cells form a connected subset of the grid graph $P_n\mathbin{\Box}P_n$.

For each of the $31344$ arrays, the search enumerates possible black-cell sets subject to condition (1). Each candidate is then tested for conditions (2) and (3). Equivalently, this can be formulated as an exact cover instance with additional connectivity checks, using the same dancing-links machinery used to generate the double word squares.

The exhaustive test produced zero arrays having a surviving black-cell set satisfying all three hitori conditions. Therefore the number of valid hitori puzzles among the $31344$ double word squares is

$$ 0 . $$

Hence no double word square formed from $\mathrm{WORDS}(3000)$ gives a valid hitori puzzle.