TAOCP 7.2.2.1 Exercise 440
The statement is false.
Section 7.2.2.1: Dancing Links
Exercise 440. [21] True or false: If the letter A occurs exactly twice in the top row of a valid hitori puzzle, exactly one of those occurrences will survive in the solution.
Verified: no
Solve time: 1m33s
Solution
The statement is false. Consider the $3 \times 3$ hitori puzzle
$$ \begin{pmatrix} A & B & A\ C & D & E\ F & G & H \end{pmatrix}. $$
Color the two occurrences of $A$ in the top row black, and leave the other seven cells white. The two black cells are not adjacent, so the adjacency condition for black cells is satisfied. The white cells form a connected region, because the cells
$$ B,\ C,\ D,\ E,\ F,\ G,\ H $$
are connected through horizontal and vertical adjacencies. No row or column contains the same letter twice among the white cells, since every remaining white entry is distinct. Hence this coloring is a valid hitori solution.
In this solution both occurrences of $A$ are removed, so neither occurrence survives. The claimed conclusion that exactly one occurrence of $A$ must survive is therefore false.
$\boxed{\text{false}}$
This completes the proof.
∎