6
$\begingroup$

The puzzle below features each week in a TV guide. It's called "Number Workout" there but I've done a bit of research and it seems to be called "Hexanum" elsewhere. It bears some resemblance to Sudoku, in that it's a logic puzzle with a single solution.

Hexanum

Transcription: "Fit the numbers 1-6 once in every hexagon so that where the hexagons touch, the numbers are the same."

I've done lots of these and I have been able to solve them using simple techniques. In terms of the Sudoku ratings listed here, it would be "Level 1" techniques: choosing a number and seeing where it can fit in each hexagon. (Several times I have got stuck, but when I finally found a new number it was still by simple deduction.)

So my question is: Is it possible to construct one of these puzzles, with a unique solution, that requires more advanced techniques to solve? Note it doesn't need to be the same size as the one below - a smaller or larger puzzle may be required to prove it.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Hmm... what do you mean by "advanced techniques?" $\endgroup$ – Aza May 31 '14 at 19:51
  • $\begingroup$ The image seems to have some hexagons that are marked with thicker borders. Is it just these hexagons that have to have unique numbers in them or is it any hexagon that you can make up by six triangles? $\endgroup$ – Chris Jun 12 '14 at 19:19
  • $\begingroup$ @Chris it's only the hexagons specified by the thick borders. For example where you have the 1 and 3 in the middle, you can fill in the triangle opposite the thick line with the same number. $\endgroup$ – DisgruntledGoat Jun 13 '14 at 15:46
  • $\begingroup$ Actually I've just realised given the other requirement that the touching hexagons have the same number then it was a very stupid question. :) In terms of complexity I would be inclined to think that it would be possible to have more complex puzzles but I'm not experienced enough to give an example of one or how to make them... $\endgroup$ – Chris Jun 13 '14 at 20:06
  • $\begingroup$ I've put this on hold as "unclear what you're asking," as, without knowing any specific details of what you mean by "advanced techniques," I'm not sure this question can be satisfactorily answered. Would it be possible for you to edit in something more specific? $\endgroup$ – Aza Jan 5 '15 at 7:44
-1
$\begingroup$

There is a standard reduction to/from 3SAT, so this problem is NP-complete. So the answer to your question is "Yes, arbitrarily complex puzzles are possible."

|improve this answer
$\endgroup$
  • $\begingroup$ If someone wants to provide the details of the reduction, be my guest. I thought I'd go ahead and give this answer, since this question has gone unanswered for a month. $\endgroup$ – Lopsy Jul 3 '14 at 21:59
  • 7
    $\begingroup$ The problem with this answer is that although it's technically correct, it doesn't provide much useful information. Even given that the problem is NP complete, it would be nice to give an example of a complex problem and a complex solving method. $\endgroup$ – Joe Z. Jul 4 '14 at 5:40
  • 1
    $\begingroup$ @Lopsy: Really? How do conclude that because you can convert to 3SAT that it is possible to generate "interesting" satisfiability problems in this world? Maybe they are all trivial so you never need OP's "advanced techniques", whatever that means. $\endgroup$ – ThePopMachine Jul 7 '14 at 23:19
  • 1
    $\begingroup$ @ThePopMachine Abstractly, if you can reduce an arbitrary 3SAT instance to this problem, then either there are 'hard' instances of this sort of puzzle (though you also need uniqueness, but that usually comes cheap with reductions) or there's a simple (linear- or quadratic-time) algorithm for solving SAT. Since the latter is rather unlikely... $\endgroup$ – Steven Stadnicki Jul 12 '14 at 0:20
  • $\begingroup$ That said, I'd really like to see how to implement arbitrary 3SAT instances here too, since it's not at all obvious to me. $\endgroup$ – Steven Stadnicki Jul 12 '14 at 0:22

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