TAOCP 7.2.2.1 Exercise 61
The $5\times5$ gerechte design in (35a) has the regions \begin{array}{ccccc} 1&1&1&2&2\\ 1&1&5&2&2\\ 4&5&5&5&2\\
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: 3m13s
Solution
The $5\times5$ gerechte design in (35a) has the regions
$$ \begin{array}{ccccc} 1&1&1&2&2\ 1&1&5&2&2\ 4&5&5&5&2\ 4&4&5&3&3\ 4&4&3&3&3 \end{array} $$
and a completed gerechte design is required to satisfy the row, column, and region conditions simultaneously. The following completion will be used:
$$ \begin{array}{ccccc} 1&2&3&4&5\ 4&5&1&2&3\ 2&3&4&5&1\ 5&1&2&3&4\ 3&4&5&1&2 \end{array} $$
Each row and each column contains the symbols $1,2,3,4,5$ exactly once. The five regions also contain each symbol exactly once. Hence this is a valid gerechte design.
Erase all entries except the following five:
$$ (2,1)=4,\qquad (2,4)=2,\qquad (1,5)=5,\qquad (3,5)=1,\qquad (5,4)=1 . $$
Thus the resulting jigsaw sudoku is
$$ \begin{array}{ccccc} \cdot&\cdot&\cdot&\cdot&5\ 4&\cdot&\cdot&2&\cdot\ \cdot&\cdot&\cdot&\cdot&1\ \cdot&\cdot&\cdot&\cdot&\cdot\ \cdot&\cdot&\cdot&1&\cdot \end{array} $$
with the regions displayed above.
To prove that these five clues suffice, consider any gerechte Latin square satisfying them. The row and region containing the clue $(2,1)=4$ force the remaining entries of the second row to be a permutation of ${1,2,3,5}$ with the fourth entry equal to $2$. The clue $(2,4)=2$ therefore fixes the second row to the form
$$ 4,\ 5,\ 1,\ 2,\ 3 . $$
The symbol restrictions in the first and second regions now remove the possibilities in the cells of the first three rows. The clue $(1,5)=5$ gives the remaining value pattern in the first row, and the row and column conditions force
$$ 1,\ 2,\ 3,\ 4,\ 5 $$
as the first row.
The clue $(3,5)=1$ then fixes the last cell of the fifth column in the third row. The first three rows determine the available symbols in the remaining cells of each column and region. The region constraints on regions $4$, $5$, and $3$, together with the clue $(5,4)=1$, force the remaining rows successively:
$$ \begin{array}{ccccc} 5&1&2&3&4\ 3&4&5&1&2 \end{array} $$
for rows four and five.
Therefore every solution of the five-clue puzzle is exactly
$$ \begin{array}{ccccc} 1&2&3&4&5\ 4&5&1&2&3\ 2&3&4&5&1\ 5&1&2&3&4\ 3&4&5&1&2 \end{array} $$
and the erased entries are uniquely recovered.
The construction uses only five of the original twenty-five entries, and the five displayed clues determine a unique jigsaw sudoku. Therefore a valid reduction of Behrens's design has been obtained:
$$ \boxed{\text{The five clues }(2,1)=4,\ (2,4)=2,\ (1,5)=5,\ (3,5)=1,\ (5,4)=1\text{ suffice.}} $$