Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There is a type of puzzle which can be modelled as finding a Hamiltonian path through a graph. One example is the Icosian game. What factors affect the difficulty of such puzzles, to be solved by humans? Let's assume the solver is unfamiliar with graph theory and Hamiltonian paths in particular, but can see the entire graph.

I'm partly motivated by the Making Difficult Mazes page by Walter D. Pullen, which lists numerous factors affecting how difficult regular mazes are, such as solution length, the number of curves and loops. Do similar factors affect Hamiltonian puzzles? Different ones?

Full Disclosure: I recently made a puzzle game for a jam, whose mechanics could be modelled as a Hamiltonian path puzzle. Whilst making it, I realised I did not have a good idea of what made a puzzle easier or harder, and was wondering if there were studies or other examples of such puzzles.

share|improve this question
Oh my god, that game is so cute! – 355durch113 Jul 29 '14 at 11:13

The critical factor is the connectivity of the graph. The Hamiltonian path problem is known to be NP-complete. Years ago I saw charts from a talk called "Where are all the hard problems?" (seems no longer available) The point was that although Hamiltonian path is NP-complete, specific instances are easy. Either (for high connectivity) you find a path quickly or (for low connectivity) you find there isn't one because you find where you get stuck. There is a transition region, akin to a phase transition, where long-range correlations become important, and that is where the hard problems are. A more recent paper is here

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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