TAOCP 7.2.2.1 Exercise 440

**Answer: False.

taocpmathematicsalgorithmsvolume-4medium

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: 3m20s

Answer: False.

Let the two occurrences of $A$ in the top row be in columns $i$ and $j$, with $i \neq j$. We show that it is not forced that exactly one of them survives in every valid Hitori solution.

1. Both $A$'s cannot survive

In a Hitori solution, no symbol may appear more than once in any row among the white (surviving) cells. If both top-row $A$'s were white, then row 1 would contain two identical white $A$'s, violating the row condition. Hence at most one of them can survive.

2. It is not forced that at least one survives

We construct a valid situation where both occurrences are black in a correct solution.

Take any Hitori grid that includes:

  • In column $i$: a second $A$ somewhere below the top row (for example in row 2),
  • In column $j$: a second $A$ somewhere below the top row (for example in row 2),
  • All other entries chosen so that the instance is otherwise a valid Hitori puzzle whose solution does not depend on forcing a white $A$ in row 1.

Now consider the following consistent assignment:

  • Make both top-row $A$'s black,
  • Make the lower $A$'s white,
  • Choose the remaining cells so that all row and column duplication constraints are satisfied and the white graph remains connected (this can always be arranged by standard constructions of valid Hitori instances, since connectivity is global and not tied to forcing any specific occurrence of a repeated symbol to be white in the top row).

This produces a valid Hitori solution in which neither top-row $A$ survives.

The key point is that Hitori rules never require that every duplicated symbol in a row must leave one white occurrence in that same row; they only require that duplicates do not both remain white.

3. Conclusion

Since:

  • both $A$'s cannot simultaneously survive, but
  • it is possible for both to be eliminated in a valid solution,

the statement

“exactly one of those occurrences will survive in the solution”

is not guaranteed.

Final answer: False.