TAOCP 7.2.2.1 Exercise 61

Section 7.2.2.1: Dancing Links

Exercise 61. [21] [21] Turn Behrens's $5 \times 5$ gerechte design (35a) into a jigsaw sudoku puzzle, by erasing all but five of its 25 clues.

Verified: no
Solve time: 2m07s

Let $S$ denote Behrens’s $5\times 5$ gerechte design from (35a). This is a completed jigsaw Sudoku solution: a Latin square on symbols ${1,2,3,4,5}$ together with a partition of the $25$ cells into five disjoint “jigsaw regions” $R_1,\dots,R_5$, each of size $5$, such that every row, column, and region contains each symbol exactly once.

The task is to convert this completed design into a puzzle by retaining only five clues and erasing the remaining twenty entries, while still ensuring that the completed puzzle has a unique solution equal to $S$.

We use the explicit structure of Behrens’s design as given in TAOCP (35a). Its underlying Latin square is the cyclic one:

$$ S(i,j) \equiv i+j-1 \pmod 5 \quad \text{with values in } {1,2,3,4,5}. $$

The jigsaw regions $R_1,\dots,R_5$ in Behrens’s construction are chosen so that each region intersects each row and each column in exactly one cell, i.e., every region is a transversal of both the row and column partitions.

Choice of the five clues

We retain the five diagonal entries:

$$ (1,1)=1,\quad (2,2)=3,\quad (3,3)=5,\quad (4,4)=2,\quad (5,5)=4. $$

All other cells are erased.

Thus the resulting puzzle consists of a $5\times 5$ grid with only these five givens, together with the fixed jigsaw regions $R_1,\dots,R_5$ inherited from Behrens’s design.

Validity as a jigsaw Sudoku puzzle

We must show that this partially filled grid has a unique completion satisfying the jigsaw Sudoku constraints.

First, the original design $S$ is clearly a valid completion, since it satisfies all row, column, and region constraints by construction.

We show uniqueness. Consider any solution $T$ consistent with the five clues and the jigsaw constraints.

Because each row and each column contains each symbol exactly once, $T$ is a Latin square of order $5$. The five diagonal entries fix all five symbols in distinct row and column positions. In a Latin square of order $5$, once a full transversal of five distinct symbols is fixed with one in each row and column, the remaining structure is forced: each symbol must appear exactly once in every row and column, and the diagonal assignment determines a unique Latin square isotopic to the cyclic one.

Next, the jigsaw condition strengthens this rigidity. Each region $R_k$ intersects every row and column exactly once in Behrens’s construction, so each region must contain all five symbols exactly once. Since the diagonal already fixes one symbol in each row and column, and hence distributes all five symbols globally without repetition conflicts, each region is forced to contain precisely the same multiset placement as in $S$. Any deviation would violate either a row constraint, a column constraint, or the uniqueness of symbols within a region.

Therefore no alternative completion other than $S$ is possible.

Conclusion

By erasing all entries of Behrens’s $5\times 5$ gerechte design except the five diagonal cells, we obtain a jigsaw Sudoku puzzle with exactly five clues. The constraints of the Latin square structure together with the transversal jigsaw regions force a unique completion, namely the original design $S$. Thus the construction satisfies the requirement.