Hamiltonian Tours

Visit every point once

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• A Hamiltonian cycle visits every vertex exactly once and returns to the start.
• Unlike Euler paths, there is no known quick test: the problem is NP-complete.
• Parity (chessboard colouring) can sometimes prove that no cycle exists.
• Quick rules like nearest neighbour give good tours, but not always the best.

Steps

1. The Icosian game
2. Euler versus Hamilton
3. A 3 × 3 grid
4. One digit at a time
5. Delivery round
6. Nearest neighbour