TAOCP 7.2.2.1 Exercise 441

Exercise 441. [18] Describe every valid hitori puzzle of size $1 \times n$ on a $d$-letter alphabet.

Verified: no
Solve time: 58s

Solution

Let the instance be a string $S[1],\dots,S[n]$ over an alphabet of size $d$. In a $1\times n$ hitori grid, any white set of cells must be connected, hence must be a single interval $[l,r]$. Every other position is black. Thus every solution is determined by a choice of $(l,r)$ with $1 \le l \le r \le n$ such that the letters $S[l],\dots,S[r]$ are pairwise distinct.

Black cells must be non-adjacent. In one dimension this means no two consecutive positions can both be black. If the white interval is $[l,r]$, then the black region is the union of the prefix $[1,l-1]$ and the suffix $[r+1,n]$. Therefore each of these two segments must have length at most $1$. This gives

$$ l-1 \le 1,\qquad n-r \le 1, $$

hence $l \in {1,2}$ and $r \in {n-1,n}$ with $l \le r$. The only admissible candidates are

$$ [1,n],\quad [1,n-1],\quad [2,n],\quad [2,n-1]. $$

A candidate interval is feasible exactly when its letters are all distinct. Define the predicates

$$ A:\ S[1..n]\ \text{has all distinct letters}, $$

$$ B:\ S[1..n-1]\ \text{has all distinct letters}, $$

$$ C:\ S[2..n]\ \text{has all distinct letters}, $$

$$ D:\ S[2..n-1]\ \text{has all distinct letters}. $$

Each feasible solution corresponds exactly to one true predicate among these four.

A valid hitori puzzle in this setting is one that has a unique solution, so exactly one of $A,B,C,D$ must hold.

If $A$ holds, then every subinterval is also injective, so $B,C,D$ all hold, contradicting uniqueness. Hence $A$ never occurs in a valid puzzle.

Assume $D$ holds. Then $S[2..n-1]$ has no repeats. The interval $[1,n-1]$ f