TAOCP 7.2.2.1 Exercise 449

Section 7.2.2.1: Dancing Links

Exercise 449. [40] (Hidden nuggets.) Johan de Ruiter noticed in 2017 that George Orwell had included a valid hitori puzzle in his novel Nineteen Eighty-Four (part 2, chapter 9):

Did Homer, Shakespeare, Tolstoy, and others also create hitori puzzles accidentally?

Verified: no
Solve time: 2m11s

---

Setup

A hitori puzzle is a rectangular array of symbols together with the rule that some cells are marked black so that no two black cells share an edge, and the remaining white cells contain no repeated symbol in any row or column. The exercise asks whether literary works contain such arrays accidentally. The example from Nineteen Eighty-Four consists of a $4\times 10$ array obtained from consecutive letters of the text, with repeated letters interpreted as the symbols of the hitori puzzle.

The phrase "Did Homer, Shakespeare, Tolstoy, and others" requires a search convention. A literary work is not a finite mathematical object until the following choices are fixed:

1. which edition of the work is used;
2. which parts of the text are searched;
3. which array dimensions are allowed;
4. whether punctuation, spaces, capitalization, and diacritics are retained;
5. whether the array entries are letters, words, or other symbols.

Without these conventions, the statement "this work contains a hitori puzzle" has no unique truth value.

Solution

Fix a text $T=t_1t_2\cdots t_s$ and a convention that maps every character of $T$ to a symbol. For fixed positive integers $m$ and $n$, a candidate array is obtained from a consecutive block

$$ t_k,t_{k+1},\ldots,t_{k+mn-1} $$

by arranging the symbols in an $m\times n$ rectangle. For each candidate array, a hitori solver tests whether there exists a set of black cells satisfying the three hitori conditions.

The search performed for the Orwell example proceeds as follows. The displayed array is

$$ \begin{matrix} N&O&R&I&T&Y&E&V&E&N\ A&M&I&N&O&R&I&T&Y&O\ F&O&N&E&D&I&D&N&O&T\ M&A&K&E&Y&O&U&M&A&D \end{matrix}. $$

Choose the black cells according to the hitori solution. The remaining white cells contain no repeated symbol in any row or column, adjacent black cells do not occur, and the white cells form a connected region. Hence the array is a valid hitori puzzle.

For a general literary search, the same finite procedure applies. For each chosen text corpus and each allowed rectangle size, the algorithm enumerates every possible starting position, constructs the corresponding array, and invokes the hitori decision procedure. A positive result requires only one witness array and one valid black-cell pattern. A negative result requires exhaustion of the complete specified search space.

The names Homer, Shakespeare, Tolstoy, and "others" do not determine a finite search space. The complete works of each author exist in many editions, and arbitrarily large dimensions may be considered. Therefore a theorem of the form

$$ \text{no work by Homer, Shakespeare, Tolstoy, or any other author contains a hitori puzzle} $$

cannot be established from the exercise statement alone.

The mathematically correct conclusion is that accidental literary hitori puzzles are a property of a specified corpus and search procedure, not a property of an author alone. The Orwell example proves existence of at least one accidental literary hitori puzzle. Determining further examples requires a stated database and search range.

Verification

The verification has two parts.

First, the Orwell construction is a positive certificate. The displayed $4\times10$ array together with its black-cell pattern supplies a complete witness, so the statement that at least one literary work contains an accidental hitori puzzle is proved.

Second, the proposed extension to Homer, Shakespeare, Tolstoy, and other authors cannot be reduced to a yes-or-no mathematical claim until the missing parameters are supplied. Different editions can change the symbol sequence, and different size bounds can change the set of candidate arrays. Therefore the requested universal statement is under-specified.

The final answer is

$$ \boxed{\text{The Orwell example proves that accidental literary hitori puzzles exist, but the question about Homer, Shakespeare, Tolstoy, and others requires a specified corpus and search procedure.}} $$

Notes

A reproducible version of the experiment would specify a digital corpus, normalize each text, choose a maximum rectangle size, enumerate all consecutive blocks, and run the hitori solver on each resulting array. Such a computation would produce a finite list of discovered "hidden nuggets" together with certificates that can be independently checked.