TAOCP 7.2.2.1 Exercise 406

Exercise 406. [16] Show that the following hidato puzzle isn't as hard as it might look at first:

$$\begin{array}{|c|c|c|c|c|c|} \hline 19 & 52 & 53 & 54 & 4 & 62 & 63 & 64 \ \hline 20 & & & & & & & 1 \ \hline 21 & & & & & & & 60 \ \hline 41 & & & & & & & 59 \ \hline 31 & & & & & & & 58 \ \hline 32 & & & & & & & 11 \ \hline 33 & & & & & & & 10 \ \hline 35 & 34 & 37 & 28 & 27 & 26 & 11 & 12 \ \hline \end{array}$$

Verified: no
Solve time: 4m53s

Solution

The first step is to notice that the statement as printed cannot be correct. The number $11$ occurs twice:

$$ (6,8)=11,\qquad (8,7)=11 . $$

A Hidato solution must be a permutation of ${1,\ldots,64}$, so the two clues cannot both be present. The typo is resolved by changing the clue at $(6,8)$ from $11$ to $9$. With this correction, the puzzle has the following completion:

$$ \boxed{ \begin{array}{|c|c|c|c|c|c|c|c|} \hline 19&52&53&54&4&62&63&64\ \hline 20&18&51&5&55&3&61&1\ \hline 21&42&17&50&6&56&2&60\ \hline 41&22&43&16&49&7&57&59\ \hline 31&40&23&44&15&48&8&58\ \hline 32&30&39&24&45&14&47&9\ \hline 33&36&29&38&25&46&13&10\ \hline 35&34&37&28&27&26&11&12\ \hline \end{array}} $$

It remains to verify that this is a Hidato solution.

Every integer from $1$ through $64$ occurs exactly once, so the array is a permutation of the required set. The fixed clues are all preserved, except for the necessary correction of the duplicated $11$ clue.

Now follow the numbers in order. The path begins

$$ 1\to2\to3\to4, $$

with positions

$$ (2,8)\to(3,7)\to(2,6)\to(1,5), $$

and each step is a legal king move. Continuing gives

$$ 4\to5\to6\to7\to8\to9\to10\to11\to12\to13\to14\to15\to16\to17\to18\to19, $$

where each consecutive pair occupies adjacent cells. The same direct check applies to the remaining portions:

$$ 19\to20\to21\to22\to23\to24\to25\to26\to27\to28\to29\to30\to31\to32\to33\to34\to35, $$

$$ 35\to36\to37\to38\to39\to40\to41\to42\to43\to44\to45\to46\to47\to48\to49\to50\to51, $$

and

$$ 51\to52\to53\to54\to55\to56\to57\to58\to59\to60\to61\to62\to63\to64. $$

Thus every transition $k\to k+1$ is horizontal, vertical, or diagonal, as required by the Hidato rules.

The puzzle only appears difficult because many of the clues are arranged so that the path winds through the board in a misleading way. Once the duplicated clue is corrected, the structure of the path is exposed and the completion above gives a direct verification. Therefore the corrected puzzle is not hard.