What factors affect the difficulty of Hamiltonian puzzles?

Question

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.

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