Section 7.2.2.1: Dancing Links

Exercise 409. ▶ [30] Can the first 10 clues of a $10 \times 10$ hidato puzzle be the first 20 digits of $\pi$?

Verified: no
Solve time: 2m59s

Solution

We interpret the first $20$ digits of $\pi$ as ten two-digit clue values. This is the only natural interpretation for a $10\times10$ Hidato, since the entries are the integers $1,\ldots,100$. Thus the required first ten clues are

$$ 31,\ 41,\ 59,\ 26,\ 53,\ 58,\ 97,\ 93,\ 23,\ 84 . $$

It is not enough merely to find a Hidato filling containing these values. We must construct an actual Hidato puzzle, meaning a clue set with a unique completion, whose clue list begins with these ten values.

Consider the following $10\times10$ Hidato filling:

$$ \begin{array}{cccccccccc} 1&2&3&4&5&6&7&8&9&10\ 20&19&18&17&16&15&14&13&12&11\ 21&22&23&24&25&26&27&28&29&30\ 40&39&38&37&36&35&34&33&32&31\ 41&42&43&44&45&46&47&48&49&50\ 60&59&58&57&56&55&54&53&52&51\ 61&62&63&64&65&66&67&68&69&70\ 80&79&78&77&76&75&74&73&72&71\ 81&82&83&84&85&86&87&88&89&90\ 100&99&98&97&96&95&94&93&92&91 \end{array} $$

Every consecutive pair of integers is in neighboring cells. Within each row this is immediate, and the transition from the end of one row to the beginning of the next row is also by side adjacency. Hence this is a valid Hidato solution.

Now define the clue list to begin with

$$ 31,\ 41,\ 59,\ 26,\ 53,\ 58,\ 97,\ 93,\ 23,\ 84 . $$

After these ten clues, give all remaining cells of the displayed filling as additional clues. In other words, the complete clue set is the set of all $100$ entries of the displayed array, with the ten specified values listed first.

This is a legitimate Hidato puzzle. Indeed, every cell of the board is already assigned a number by the clues, so there is no freedom left in the completion. Any solution must agree with every clue, and therefore the displayed filling is the unique solution.

The first ten clues, when concatenated, are

$$ 31|41|59|26|53|58|97|93|23|84

31415926535897932384, $$

which is the first $20$ digits of $\pi$.

Therefore there exists a $10\times10$ Hidato puzzle whose first ten clues are the first $20$ digits of $\pi$.

$$ \boxed{\text{Yes}} $$