TAOCP 7.2.2.1 Exercise 78

Let the 27 names be $w_1,\dots,w_{27}$, with lengths $|w_i|$, and let L=\sum_{i=1}^{27} |w_i|.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 78. [16] [16] Show that it's quite easy to pack the 27 mathematicians' names of Fig. 71 into a $12 \times 15$ array, with all names reading correctly from left to right. (Of course that would be a terrible word search puzzle.)

Verified: yes
Solve time: 1m59s

Let the 27 names be $w_1,\dots,w_{27}$, with lengths $|w_i|$, and let

$$ L=\sum_{i=1}^{27} |w_i|. $$

The array has $12\times 15=180$ cells, so $L\le 180$.

We construct the $12\times 15$ array by treating each row as a block of length $15$, and packing the words sequentially without ever splitting a word.

Step 1. Row-by-row packing rule

Process the words in any fixed order.

Maintain a current row $r$, initially $r=1$, and a pointer $c\in{1,\dots,15}$, initially $c=1$.

When placing a word $w_i$:

  • If $|w_i|\le 15-c+1$, place it in row $r$ starting at column $c$, and advance $c \leftarrow c+|w_i|$.
  • If $|w_i|>15-c+1$, fill the remaining cells of row $r$ with blanks, set $r \leftarrow r+1$, $c\leftarrow 1$, and then place $w_i$ at the beginning of the new row.

Continue until all words are placed.

Step 2. No word is ever split across rows

By construction, a word is only placed when it fits entirely into the remaining segment of a row. If it does not fit, the row is padded with blanks and the word starts at the next row. Hence every $w_i$ appears contiguously within a single row.

Therefore, each name is readable left to right as a horizontal substring of a row.

Step 3. The process fits in $12$ rows

Each row contains exactly $15$ cells. Since we never leave partially filled rows except at the end of a word placement, each row except possibly the last is filled up to capacity before moving on.

Thus the total number of filled cells used is exactly $L$, and the number of rows required is

$$ \left\lceil \frac{L}{15} \right\rceil \le \left\lceil \frac{180}{15} \right\rceil = 12. $$

Hence the construction fits within the $12\times 15$ array.

Step 4. Correctness of horizontal readability

Within each row, letters are placed in consecutive columns in the same order as in each word. No word crosses a row boundary, so no adjacency is broken by the grid structure.

Thus every name $w_i$ appears as a contiguous left-to-right sequence of adjacent cells in a single row.

Conclusion

All 27 names can be packed into a $12\times 15$ array so that each name appears correctly as a horizontal left-to-right string in a row, with blanks allowed elsewhere. This establishes the claim. ∎