0
$\begingroup$

It seems like people have discussed this reduction here:

Is Hidoku NP complete?

But it looks like the solution that was given only tells you if the Hidoku problem has a solution or not (if an hamilton path/cycle exists), what about extracting the solution itself from this reduction?

Can someone see how it is possible?

Best regards, Tal

$\endgroup$
  • 1
    $\begingroup$ The reduction is from (restricted) Hamiltonian path to Hidoku, not the other way around. $\endgroup$ – Yuval Filmus Mar 31 '17 at 18:57
  • $\begingroup$ Thanks! I probably got confused. So the other way around - I can't really do anything special except construct a grid graph based on the Hidato puzzle as the input? $\endgroup$ – Tal Yitzhak Apr 1 '17 at 0:50
  • $\begingroup$ You can always use the reduction in the answer. Given a feasibility oracle, it allows you to find a solution. $\endgroup$ – Yuval Filmus Apr 1 '17 at 5:02
2
$\begingroup$

For any NP-complete problem where the question is, "Can you complete this partial solution?" 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 "self-reducibility": 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.

$\endgroup$
  • $\begingroup$ Thanks for the answer! I'm trying to think about the efficiency check you suggested: again, if I need to give a certain cell a new value (before I run the hamilton path algorithm), assuming I can fetch all it's exisiting neighbors values - how can I minimize the range of numbers to random? $\endgroup$ – Tal Yitzhak Mar 31 '17 at 23:49
  • $\begingroup$ The solution has a track through the grid that goes from $1$ to $2$ to $3$ to $4$ to... to $n^2$. So, if you just wrote $8$ in some square, then you know that two of its neighbours must be $7$ and $9$. If you've not already filled those in, you should try $7$ in each empty neighbour until you find its position, then try $9$ in each remaining empty neighbour. And note that nothing in this algorithm is random. $\endgroup$ – David Richerby Apr 1 '17 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.