Hidato (also known as Hidoku) is a logic puzzle game invented by Dr. Gyora Benedek, an Israeli mathematician. The rules are simple: given a grid with $n$ cells some of which are already filled with a number between $1$ and $n$ (the first and the last number are circled), the player must completely fill the board with consecutive numbers that connect horizontally, vertically, or diagonally.
Figure 1: An Hidato game (that fits on a $8 \times 8$ grid) and its solution on the right.
We prove that the corresponding decision problem $\sf{HIDATO}$ : “Given a Hidato game that fits in a $m \times n$ grid, does a valid solution exist?” is $\sf{NP}$-complete.