Solving Hidoku problem using reduction to Hamilton path
For any NP-complete problem where the question is, &quot;Can you complete this partial solution?&quot; you can extract a solution from the decision problem just by filling in components of the solution one at a time and asking if there's still a solution.
Is there a solution with $1$ in the top-left corner? No. With $2$ in the top-left? No. With $3$? Yes. OK, let's fix the top-left to be $3$: we know this can be extended to a solution. Is there a solution with $3$ in the top-left corner and $1$ in the square next to it? And so on.  (In fact, you can be a bit more efficient by using the fact that two of the neighbours of the square labeled $i$ must be $i-1$ and $i+1$.)
This is a specific case of the concept of &quot;self-reducibility&quot;: a problem is self-reducible if you can find the answer given an oracle for smaller instances of the decision problem. (In the case of Hidoku, the instances the oracle is called on are smaller in the sense that they have fewer blank squares.)  Some other examples of self-reducible problems are:

SAT. Suppose you want to know whether a formula in variables $X_1, \dots, X_n$ is satisfiable. If it's satisfiable, then either there's a satisfying assignment with $X_n=t$, or there's one with $X_n=f$, or both. So replace $X_n$ with $t$ and ask if the resulting formula in $n-1$ variables is satisfiable.  If so, recurse; if not, set $X_n=f$ and recurse.

$3$-colourability. Suppose you want to know whether a graph $G$ is $3$-colourable. If it is $3$-colourable and it has more than three vertices, then two of the vertices must receive the same colour. So, pick two non-adjacent vertices $x$ and $y$ and merge them (delete $y$ and make every vertex that was adjacent to it be adjacent to $x$). If the resulting graph is $3$-colourable, then $G$ has a $3$-colouring in which $x$ and $y$ have the same colour, so recurse. If they don't, then any $3$-colouring must assign different colours to $x$ and $y$, so we can add an edge between them and try a different pair of non-adjacent vertices.
If this process ever gives a graph that contains a $4$-clique –which we can test in polynomial time – then $G$ is not $3$-colourable. Otherwise, we eventually reduce the graph down to a $3$-clique, which is $3$-colourable. We can recover the $3$-colouring by tracking which vertices got merged into the different vertices of the $3$-clique.

Independent set. Suppose we wish to know if a graph $G$ has an independent set of size at least $k$. Pick a vertex $v$ and ask if $G-v$ contains a $k$-independent set. If so, $G$ has a $k$-independent set that doesn't include $v$, so recurse on $G-v$ to find out what it does contain. Otherwise, any $k$-independent set must contain $v$, so it can't contain any of $v$'s neighbours. So ask if $G-v-\Gamma(v)$ contains a $(k-1)$-independent set. If it does, recurse. If it doesn't, $G$ has no $k$-independent set.