Take the 2-minute tour ×
Puzzling Stack Exchange is a question and answer site for those who study the creation and solving of puzzles. It's 100% free, no registration required.

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! –  Grantwalzer Jul 29 at 11:13

1 Answer 1

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

 
discard

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.