| Search | Nodes | Result |
|---|---|---|
| Plain backtracking | – | – |
| Warnsdorff order | – | – |
| Dead-end and connectivity checks | – | – |
| All three | – | – |
Hamiltonian path explorer
In 1857 William Rowan Hamilton invented a puzzle: travel along the edges of a dodecahedron so that you pass through each of its 20 corners exactly once and end where you started. Such a route is now called a Hamiltonian cycle. It is easy to check and, in general, hard to find. Trace one yourself on Hamilton's dodecahedron, a chessboard or a graph you draw, or watch a backtracking search hunt for one, count the dead ends it runs into, and see how much a few simple checks cut the search. Pick a graph and a goal: a cycle that comes back to its start, or a path. Trace: click a vertex to start, then a neighbour each time; dashed rings show where you can go next. Click the last vertex, Back or Undo to take a step back, and Hint for a next step that can still be finished. Search: Run or Step through a backtracking search, which adds vertices until it gets stuck and then backs up; red dashes show where it turned back, and the bars count the nodes at each path length. Before it starts, click a vertex to choose where it begins. The checkboxes switch the pruning on and off, Compare runs the same search with and without it, and Count all counts every cycle or path of a small graph. Edit: click to add a vertex, click two vertices to join or separate them, drag to move one, and Delete removes the selected vertex.
How it works
- Pick a graph, such as Hamilton's dodecahedron, the Petersen graph or a knight's tour, or draw your own in Edit, and choose a cycle or a path as the goal.
- In Trace, click a vertex to start and then one neighbour after another. Back and Undo take a step back, and Hint shows a next step that can still be finished.
- In Search, press Run or Step to watch backtracking look for a route, switch the pruning on and off, and press Compare to see how many nodes each version needs.
Hamiltonian versus Euler
An Euler path uses every edge once; a Hamiltonian path visits every vertex once. They sound alike but behave very differently. Whether a connected graph has an Euler path is settled by counting the vertices of odd degree, as Euler showed in 1736: it has one when there are none or two. For Hamiltonian paths no such rule is known. Deciding whether a graph has a Hamiltonian cycle is NP-complete, one of the 21 problems on Richard Karp's list of 1972, so a fast method for it would give fast methods for thousands of other hard problems. What exists are conditions that settle some graphs. Dirac's theorem of 1952 guarantees a Hamiltonian cycle when every vertex has degree at least n/2, and Ore's of 1960 when any two vertices that are not joined have degrees adding up to at least n; a vertex of degree 1, a cut vertex or two colour classes of different sizes rule one out.
How the search works
Backtracking builds the path one vertex at a time and, when it gets stuck, takes back the last step and tries the next neighbour. It always finds a Hamiltonian cycle if there is one, but the number of partial paths can grow exponentially. On the 5 × 5 grid, which has no Hamiltonian cycle, plain backtracking explores 153,745 nodes before it is sure. Two checks stop hopeless paths early: an unvisited vertex with fewer than two free neighbours can no longer be fitted into a cycle, and when the unvisited vertices fall apart into separate pieces, no single path can cover them. With both, the same proof takes 1,761 nodes. Warnsdorff's rule of 1823, which tries the neighbour with the fewest onward moves first, finds an 8 × 8 knight's tour from a corner in 64 moves without a single dead end.
Frequently asked questions
What is the difference between a Hamiltonian path and a Hamiltonian cycle?
A Hamiltonian path visits every vertex of a graph exactly once. A Hamiltonian cycle does the same and then returns along one more edge to where it started, so it can begin at any of its vertices. Every graph with a Hamiltonian cycle has a Hamiltonian path (leave out one edge of the cycle), but not the other way round: the Petersen graph has Hamiltonian paths and no Hamiltonian cycle.
Does the dodecahedron have a Hamiltonian cycle?
Yes, 30 of them, counting each cycle once whatever its start and direction. Hamilton turned the question into the Icosian game in 1857, a board with the 20 corners of a flattened dodecahedron marked with consonants, and sold the rights for £25 to the London toy maker John Jaques and Son. Count all in the app finds the 30 cycles in about 1,400 nodes.
Why does a 5 × 5 grid have no Hamiltonian cycle?
Colour the 25 points like a chessboard: 13 get one colour and 12 the other, and every step goes to the other colour. A cycle alternates colours all the way round, so it needs as many of one colour as of the other, which 13 and 12 cannot give. The same argument works for every grid with an odd number of points, for a knight on a 5 × 5 or 7 × 7 board (a knight always changes square colour) and for the Herschel graph, whose two classes have 6 and 5 vertices. A Hamiltonian path is still possible: it starts and ends on the larger colour.
How does Warnsdorff's rule find a knight's tour?
H. C. von Warnsdorff suggested in 1823 always moving the knight to the square from which it will have the fewest onward moves. Squares near the edges and corners, which are easy to cut off, are then visited early, while the knight still has a way in. The rule is a rule of thumb, not a guarantee, and ties have to be broken somehow, but on an 8 × 8 board it usually completes a tour without going back. Combined with backtracking, as in the app, it finds open tours from 5 × 5 up and closed tours on the 6 × 6 and 8 × 8 boards.
How many Hamiltonian cycles does a complete graph have?
(n − 1)!/2 for n ≥ 3. Fix the starting vertex; the other n − 1 can follow in any order, and each cycle is counted twice, once in each direction. K₆ has 5!/2 = 60 and K₁₀ has 181,440. These are the round trips a traveling salesman has to choose from, which is why trying them all stops being possible so quickly.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor