Hamiltonian Path Challenge Generator
Visiting every edge exactly once is decidable by counting odd degrees, and Euler settled it in 1736. Visiting every node exactly once looks like the same kind of question and is not: there is no simple condition, and the only general method is to search. That gap between two nearly identical-sounding problems is one of the cleanest illustrations of what makes a problem hard, and this counts every path by brute force so the answer is exact.
What this generator does
Builds a graph, optionally laying a path through a shuffled order first so one is certain to exist, then searches every ordering to count how many Hamiltonian paths there are. Each path is counted once rather than twice for its two directions.
How to use this tool
- Choose the node count and the edge density.
- Decide whether a path should be guaranteed to exist.
- Try to trace a route through every node without repeating one.
- Compare with the path shown and the total count.
Understanding the controls
- How many nodes
- Between 4 and 9. Every ordering is searched, which is factorial work — nine is already 362,880 starting points before pruning.
- Extra edge density (%)
- More edges make paths far more common. A sparse graph often has none at all.
- Guarantee one exists
- On, a path is laid through a shuffled order before the extra edges are added. Off, whether one exists is genuinely open until the search runs.
- Seed
- Reproduces the same graph exactly, so a challenge can be set and solved later.
Common use cases
- Puzzle instances where a route must visit everything once
- Showing the gap between Euler and Hamiltonian problems
- Test cases for a path-finding implementation
- Teaching what NP-complete means with a concrete example
- Reproducing the same graph from a seed
How this generator works
The search walks every extension of every partial path, backtracking when it gets stuck. The check re-runs that search independently, confirms the reported path uses only real edges and visits every node exactly once, and requires the count to match.
Randomness and fairness
The graph is random; whether it has a Hamiltonian path is decided by exhaustive search rather than assumed. Seeded graphs reproduce and are therefore explicitly not cryptographically secure. Unseeded, the browser's cryptographically secure generator builds them.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Nine nodes is the ceiling, because the exhaustive count is factorial — the whole point is that no shortcut is known.
- Undirected graphs only; the directed version is a different problem.
- Hamiltonian cycles, which must also return to the start, are not distinguished from paths.
- No hint system: the path is shown or it is not.
- Graphs are not stored between visits.
Privacy and your data
The graph and the search run entirely in your browser. Nothing about the puzzle or your seed is transmitted.
Related generators
- Euler Path GeneratorTrails that use every edge exactly once, with the odd-degree count that decides whether one can exist at all.
- Travelling Salesman Problem GeneratorTour instances on random coordinates, solved exactly by Held-Karp, with the nearest-neighbour tour shown for comparison.
- Graph Traversal GeneratorThe same graph visited breadth-first and depth-first side by side, with the hop count each node sits at.
- Random Graph GeneratorRandom graphs at a density you choose, drawn and exported as an edge list or DOT, with connectivity measured rather than assumed.