1
$\begingroup$

I'm looking for straightforward puzzle types where it is difficult to determine ahead of time whether or not there will be an solution to the puzzle (and therefore one must either try to solve it, or develop a deep intuition through practice.)

To clarify: I am not looking for NP complete problems. In fact, I need to be able to compute, for any given puzzle example, whether or not a puzzle is tractable ahead of time. I will then be tracking the amount of time it takes for a player to either solve the puzzle, or decide that it's unsolvable.

One example is Euler path puzzles (e.g. 'don't lift the pencil') where most varieties of the puzzle are straightforwardly solvable, and others are impossible. If you don't know graph theory, you actually have to work it out before deciding whether it's solvable or unsolvable.

I was wondering what other puzzles have this characteristic -- simple ruleset, engaging, but difficult to know ahead of time whether it is solvable.

Other examples include:

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ The path puzzleeample isn't difficult to know whether it is solvable. If any point has an odd number of vertices (apart from start and finish) it is does not have a solution. Graph theory is not necessary to see that. $\endgroup$ – Weather Vane Oct 22 '18 at 18:42
  • 2
    $\begingroup$ I'm going to go out on a limb and guess that the overwhelming majority of the public (or puzzle solving community, for that matter) is not going to effortlessly intuit that a Euler puzzle is not solvable if "any point has an odd number of vertices (apart from start and finish)." $\endgroup$ – Parseltongue Oct 22 '18 at 18:48
  • $\begingroup$ @Parseltongue: Given that I and Weather Vane at least consider the Euler path to be easy to work out if it solvable without solving it perhaps you could give an example of something you consider to be in this catgegory? I can't help but think that for most puzzles people that don't do puzzles (or are just not familiar with that type of puzzle) probably wouldn't be able to determine if there is a solution without having to solve it. $\endgroup$ – Chris Oct 22 '18 at 22:03
  • 1
    $\begingroup$ Most people can't look at a Euler diagram and determine that it is solvable without knowing the vertex trick beforehand. That's the whole reason they're interesting at all! Those puzzles have been used in social science research since the 1960s precisely for the property described above. Another example might be the 8-puzzle (or it's variants): geeksforgeeks.org/check-instance-8-puzzle-solvable $\endgroup$ – Parseltongue Oct 22 '18 at 22:08
  • 3
    $\begingroup$ I somehow remember when I read when (and how) Euler path puzzles can be solved or not; I was about nine years old. I was quite baffled that it was so simple. People don't have to know graph theory to solve such a puzzle, but the chance that they discover the solution (instead of reading and remembering it) is minimal. After all, it took a while for the Königsberg bridges puzzle to be solved, by the top mathematician at that time. $\endgroup$ – Glorfindel Oct 23 '18 at 6:24
2
$\begingroup$

It's not a generic answer with a genre or anything, but I was immediately reminded of Pentomino puzzles. Especially when constraints are added to make the solution be 3x20 or 4x15 or something of the sort.

Arthur C. Clarke even made it a facet of the book Imperial Earth.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Pentomino puzzles are also hard to solve programmatically, at least when the board size is large. I still have to examine the Dancing Links algorithm... $\endgroup$ – Glorfindel Oct 23 '18 at 6:27
1
$\begingroup$

Here is a list of genres of problems where some instances of them are hard to solve, given their size. Are any of them the sort of thing you're looking for?

| improve this answer | |
$\endgroup$
  • $\begingroup$ What I'm looking for is different from NP complete problems. Like in the Euler puzzle examples, it's computationally trivial to know whether or not the solution is tractable... it's just that it's not easy for humans to instantly know without actually trying to solve the game. I'm looking for puzzles where humans would have to struggle a bit before deciding whether it's not solvable $\endgroup$ – Parseltongue Oct 22 '18 at 17:29
  • $\begingroup$ @Parseltongue the question invites opinions as to what is easily seen. This is a good answer. I would add Rubik's cube where a single piece might have been removed and replaced in a different orientation. $\endgroup$ – Weather Vane Oct 22 '18 at 18:35
  • $\begingroup$ I'm sorry, but this doesn't answer my question. I'm looking for puzzles where it is computationally feasible, for any given puzzle example, to determine whether or not it is solvable, but for which humans (on average) would struggle to decide without first trying the puzzle. Obviously there will be variability in how much any given person will struggle to come to that conclusion (but who cares? I'm talking about averages). $\endgroup$ – Parseltongue Oct 22 '18 at 18:52
  • $\begingroup$ Can "computationally feasible" just include a computer solving it or does it have to determine solvability without actually generating a valid solution? $\endgroup$ – Chris Oct 22 '18 at 22:07
  • $\begingroup$ It can just include a computer solving it. $\endgroup$ – Parseltongue Oct 22 '18 at 22:14
1
$\begingroup$ 
    S E N D
+   M O R E
-----------
  M O N E Y

Alphametic Puzzle is a simple puzzle which requires people to hands on it, but computationally feasible by a program (in just $O(10!)$).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Very good example. $\endgroup$ – Parseltongue Oct 23 '18 at 2:01

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.