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: yes
Solve time: 1m43s

Solution

Let the $1\times n$ puzzle be the string

$$ a_1a_2\cdots a_n, $$

where each $a_i$ is one of the $d$ letters in the alphabet. A solution of a hitori puzzle consists of the unshaded positions, because the shaded positions are determined as their complement.

In a valid solution, the unshaded positions must be connected. The graph of a $1\times n$ board is the path

$$ 1-2-\cdots-n, $$

so every connected set of unshaded positions is an interval

$$ [a,b]={a,a+1,\ldots,b}. $$

The letters in this interval must all be different, because the only possible duplicate conflicts occur in the single row.

The shaded positions are

$$ {1,\ldots,a-1}\cup{b+1,\ldots,n}. $$

Since shaded cells cannot be adjacent, the left shaded segment and the right shaded segment can each contain at most one position. Hence

$$ a-1\leq 1,\qquad n-b\leq 1. $$

Therefore the unshaded interval must be one of the following four forms:

$$ [1,n],\qquad [2,n],\qquad [1,n-1],\qquad [2,n-1], $$

whenever the indicated interval exists.

For $[1,n]$, the whole string must contain distinct letters. For $[2,n]$, only the first position is shaded, and the remaining string

$$ a_2a_3\cdots a_n $$

must contain distinct letters. For $[1,n-1]$, the remaining string

$$ a_1a_2\cdots a_{n-1} $$

must contain distinct letters. For $[2,n-1]$, both end positions are shaded, and the remaining string

$$ a_2a_3\cdots a_{n-1} $$

must contain distinct letters.

Conversely, each of these four possibilities gives a valid solution. If one of the four indicated intervals has pairwise distinct letters, leave precisely that interval unshaded. The unshaded cells form a connected path, so condition (i) of Hitori is satisfied. The shaded cells occur only at the two ends, with at most one shaded cell at either end, so no two shaded cells are adjacent. The unshaded letters are distinct, so the row condition is satisfied.

Thus a $1\times n$ puzzle on a $d$-letter alphabet is valid exactly when at least one of the four strings

$$ a_1a_2\cdots a_n,\qquad a_2a_3\cdots a_n,\qquad a_1a_2\cdots a_{n-1},\qquad a_2a_3\cdots a_{n-1} $$

that exists has no repeated letter. The corresponding solutions are obtained by leaving that string's positions unshaded and shading the omitted end positions.

This completes the proof.

∎