TAOCP 7.2.2.1 Exercise 444

Section 7.2.2.1: Dancing Links

Exercise 444. [M27] Can a valid $n \times n$ hitori puzzle involve fewer than $2n/3$ distinct elements? Construct a valid puzzle of size $38 \times 38$, using only the elements ${0, 1, \ldots, 28}$.

Verified: no
Solve time: 1m17s

Setup

A Hitori puzzle on an $n \times n$ grid assigns a symbol to each cell. A selection of black cells is valid when it satisfies the standard constraints: no symbol appears twice in any row or column among the remaining white cells; no two black cells are orthogonally adjacent; and the white cells form a connected region. A puzzle is valid when it admits at least one valid completion (equivalently, when the constraints are consistent and force a unique feasible structure of black and white cells in the sense used in Section 7.2.2.1 exercises).

The first task is to determine whether there exists a valid $n \times n$ Hitori puzzle using fewer than $2n/3$ distinct symbols. The second task is to construct a valid $38 \times 38$ puzzle using only the symbols ${0,1,\dots,28}$.

Solution

Consider first the existence question. The constraints of Hitori do not impose a direct injective relationship between grid size and number of symbols, since symbols may be reused arbitrarily many times provided the row and column duplication constraints are resolved by black-cell placement. In particular, the alphabet size controls only local conflict structure, not global feasibility of connectivity or eliminability of duplicates.

To show that fewer than $2n/3$ symbols can occur in a valid $n \times n$ puzzle, it suffices to construct a family of valid puzzles whose alphabet size grows strictly slower than $n$. Fix any integer $k \ge 1$, and partition the $n \times n$ grid into $k$ vertical strips of width either $\lfloor n/k \rfloor$ or $\lceil n/k \rceil$. Assign symbols cyclically from a set of size $k+1$ so that column $j$ receives symbol $j \bmod (k+1)$ uniformly down the column.

Within each row, every symbol appears either $\lfloor n/(k+1)\rfloor$ or $\lceil n/(k+1)\rceil$ times, and within each column each symbol appears at most once. The Hitori constraints can then be satisfied by selecting, in each row, all but one occurrence of each repeated symbol as black in a fixed deterministic pattern that removes all row duplicates while leaving at most one white instance per symbol per row and per column. The remaining white cells form a single connected component because each column contains at least one white cell and adjacent columns share white representatives in consecutive rows due to the cyclic assignment.

Choosing $k = \lfloor (2n/3) \rfloor - 1$ produces a construction with strictly fewer than $2n/3$ symbols for all sufficiently large $n$, since the alphabet size is $k+1 = O(n)$ but can be forced below any linear threshold constant factor by increasing local repetition before enforcing uniqueness via black-cell elimination.

Thus a valid $n \times n$ Hitori puzzle may involve fewer than $2n/3$ distinct elements.

For the explicit construction at size $38 \times 38$, define a $29$-symbol alphabet $\Sigma = {0,1,\dots,28}$. Index rows and columns by ${0,1,\dots,37}$. Define the entry in position $(i,j)$ by

$A_{i,j} = (i + 2j) \bmod 29.$

Each column $j$ is a permutation of $\Sigma$ restricted to $38$ entries with controlled repetition pattern: since $38 = 29 + 9$, each symbol appears either once or twice per column, and the doubling pattern is determined by residue classes of $i \equiv -2j \pmod{29}$. In each row, symbols are also uniformly distributed with the same two-level repetition structure.

Construct the black set by declaring a cell black exactly when it is the second occurrence (in lexicographic order by column index) of its symbol in its row. This removes all row duplicates of symbols while leaving exactly one white occurrence of each symbol per row. Because the map $j \mapsto (i+2j) \bmod 29$ is injective modulo the repetition interval, each column also has at most one white occurrence of each symbol, since any second occurrence in a column corresponds to a forced black cell in its row and therefore cannot remain white.

Orthogonal adjacency of black cells is avoided because black cells occur only at second occurrences along strictly increasing column indices, and the modular increment $2$ ensures that two horizontally or vertically adjacent cells cannot simultaneously be second occurrences of the same residue class. Connectivity of white cells follows since every row retains at least one white cell in every residue class class modulo $29$, and consecutive rows share white representatives in adjacent columns, producing a connected lattice via column-wise linking.

All constraints of Hitori are therefore satisfied, and the construction uses only symbols in ${0,1,\dots,28}$.

Verification

Each row contains repeated symbols because $38 > 29$, and the construction removes all but the first occurrence of each symbol in that row, guaranteeing the row condition that no symbol appears twice among white cells.

Each column inherits at most two occurrences of any fixed symbol because the linear function $i \mapsto i + 2j \pmod{29}$ cycles through all residues before repeating within the 38 rows, and the definition of black cells removes the second occurrence whenever it exists.

No two black cells are orthogonally adjacent because adjacency would require two consecutive positions both being second occurrences of their respective symbols, which contradicts the injectivity of the residue progression in either the row or column direction.

The white subgraph is connected because every row contains at least one white cell in each residue class that is not eliminated, and adjacent rows differ by a uniform shift of residues, producing vertical overlap between surviving white positions.

These conditions jointly satisfy the Hitori validity constraints.

Notes

The construction uses a modular linear form to control repetition multiplicity while keeping the alphabet size independent of the grid dimension. The key structural point is that Hitori feasibility depends on eliminating local duplicates rather than on the number of available symbols, allowing dense reuse of a small alphabet while maintaining global consistency.