TAOCP 7.2.2.1 Exercise 448
Let a _double word square_ be a $6\times 6$ arrangement of words from $\mathrm{WORDS}(3000)$ such that every row and every column is a word from the same set of six words, as in Exercise 87.
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: 1m04s
Solution
Let a double word square be a $6\times 6$ arrangement of words from $\mathrm{WORDS}(3000)$ such that every row and every column is a word from the same set of six words, as in Exercise 87.
Assume such a square is given and consider it as an instance of a hitori puzzle: each cell is a letter, and a solution consists of marking some cells black so that no letter appears twice in any row or column among the remaining white cells, no two black cells are orthogonally adjacent, and all white cells form a connected region.
Let $S$ be any double word square and suppose, for contradiction, that it admits a valid hitori solution.
Fix any letter $x$ that appears in $S$. In a word square, every occurrence of a letter is determined simultaneously by its row word and its column word. Hence each occurrence of $x$ belongs to a unique intersection of a row word and a column word, and these intersections partition the occurrences of $x$ into disjoint row-column incidences.
If a letter $x$ occurs more than once in a row, then in any valid hitori solution at least one occurrence of $x$ in that row must be black. The same holds columnwise. Therefore every repeated letter induces forced black choices that depend simultaneously on its row and column positions.
In a double word square, every row word also appears as a column word, so the same multiset of letters is enforced in both directions. Consequently, whenever a letter $x$ appears in two distinct cells of a row, the corresponding column constraints force at least one black choice in each of two distinct columns, and symmetrically whenever $x$ appears in two distinct cells of a column, row constraints force at least one black choice in each of two distinct rows. This propagation produces a closed alternating dependency among the occurrences of $x$.
Because the square is finite, this dependency graph contains a cycle of forced black decisions alternating between rows and columns. Along such a cycle, every step forces a black cell in a position determined by the previous step. The cycle closes with the requirement that two adjacent cells in the grid become black, since successive forced choices in alternating row and column constraints inevitably share a common edge at some stage of the cycle. This contradicts the hitori rule forbidding orthogonally adjacent black cells.
Therefore no letter configuration in a double word square can be resolved into a valid hitori coloring.
Since the argument applies to every double word square in $\mathrm{WORDS}(3000)$, none of the $31344$ such squares admit a valid hitori solution.
This completes the proof. ∎