The Maths Behind One-Line Puzzles: Hamiltonian Paths

A Hamiltonian path is a route through a network that visits every point exactly once. One-line puzzles like Trail, Zip and Numbrix all ask for one: each square is a point, and squares that share a side are linked. The idea is named after William Rowan Hamilton, whose Icosian game of 1856 asked players to tour the corners of a dodecahedron. In general, finding such a path is one of the classic hard problems of computer science. On a small numbered grid, though, simple local rules find it.

This article is for curious players. You do not need any maths beyond counting to follow it, and each section ends with what it means at the puzzle board.

What a Hamiltonian path is

A Hamiltonian path is a path in a graph that visits each vertex exactly once, and a Hamiltonian cycle is one that also returns to where it started (Wikipedia: Hamiltonian path). In maths a "graph" is not a chart. It is a set of dots (vertices) joined by links (edges). A road map is a graph: towns are dots, roads are links.

A puzzle grid is a graph too. Every square is a dot, and two squares are linked when they share a side. In a puzzle with diagonal moves, like Hidato, diagonal neighbours are linked as well. Walls remove links: in Trail a thick wall between two squares means there is no edge between those two dots.

A Hamiltonian path on a 3x3 grid. Here the numbers are the order of the squares along the path: it starts in the top-left corner, spirals round the edge and ends in the centre.

Solving a Trail puzzle is finding one particular Hamiltonian path: the one that starts on 1, passes the other numbers in order, ends on the highest number and never uses a link that a wall has removed. The rules about never crossing and visiting every square are simply what "Hamiltonian path" means.

Hamilton's Icosian game

The Icosian game was invented in 1856 by the Irish mathematician William Rowan Hamilton and shown at the 1857 Dublin meeting of the British Association for the Advancement of Science (Wikipedia: Icosian game). The puzzle was to find a route along the edges of a regular dodecahedron, the twelve-faced solid, passing exactly once through each of its 20 corners and closing up into a round trip.

Hamilton sold the rights to Jaques and Son, the London games maker, for £25, and the company marketed the game from 1859. One version was sold as "The Travellers Dodecahedron, or a voyage around the world". It did not sell well, and the usual verdict is that it was simply too easy to be a commercial success.

Hamilton was not the only one asking the question. The British mathematician Thomas Kirkman was studying such cycles on polyhedra around the same time, and Hamilton visited him in 1861 and gave him a copy of the game. Earlier still, as a later section shows, knight's tours on a chessboard had been studied for centuries. Hamilton's name stuck to the idea anyway.

At the puzzle board, the Icosian game is a reminder that a network can be "friendly". When every point has enough links and the network is small, a route is easy to stumble on. Puzzles become interesting when the links are scarce, which is exactly what numbers and walls do.

Euler's bridges: the easy cousin

Euler's Königsberg problem asks for every link once, where Hamilton asks for every point once, and that small change makes it far easier. The city of Königsberg (now Kaliningrad) had four land masses joined by seven bridges over the river Pregel. The question was whether you could walk a route that crossed each bridge exactly once.

Leonhard Euler presented his answer to the St Petersburg Academy on 26 August 1735, and it was published in 1741 as Solutio problematis ad geometriam situs pertinentis (Wikipedia: Seven Bridges of Königsberg). The answer was no. Every land mass was touched by an odd number of bridges, and a walk that uses every link once can have at most two points with an odd number of links: the start and the finish. A route like that is now called an Eulerian path. Carl Hierholzer completed the proof in 1873, and an Eulerian path can be found in time that grows only in step with the number of links (Wikipedia: Eulerian path).

	Eulerian path	Hamiltonian path
Visits	Every link (edge) once	Every point (vertex) once
Named after	Leonhard Euler (bridges, 1735)	William Rowan Hamilton (Icosian game, 1856)
Simple test for whether one exists	Yes: count the odd-degree points (zero or two)	No simple test is known
Finding one by computer	Fast, even for huge networks	Hard in general (NP-complete)
Puzzle that uses it	Draw-a-shape-without-lifting-your-pen puzzles	Trail, Zip, Numbrix, Hidato

If you have ever drawn a house shape without lifting your pen, you have solved an Euler puzzle. A one-line grid puzzle is the other kind, and the difference in the table is why the two feel so different to solve.

Why Hamilton's question is hard

There is no known quick test that says whether a network has a Hamiltonian path. Euler's rule looks at each point's number of links and is done. For Hamilton's question, mathematicians have only partial tests. Dirac's theorem of 1952 says a network with n points (at least three) has a Hamiltonian cycle if every point has at least n/2 links, and Ore's theorem of 1960 relaxes that to pairs of unlinked points whose link counts add up to at least n (Wikipedia: Hamiltonian path). Both say "yes" for crowded networks and nothing at all for sparse ones. A grid is sparse, since no square has more than four neighbours.

In 1972 Richard Karp showed that the Hamiltonian cycle problem, for both one-way and two-way links, is NP-complete, in his paper on 21 combinatorial problems (Wikipedia: Karp's 21 NP-complete problems). NP-complete means two things together. A proposed answer is easy to check: walk along it and tick off the points. But no one knows a method that always finds an answer quickly as networks grow, and a fast method for any one NP-complete problem would give fast methods for all of them. The Clay Mathematics Institute puts the open question this way: if it is easy to check that a solution is correct, is it also easy to solve the problem? (Clay Mathematics Institute: P vs NP)

At the puzzle board, this explains a feeling you may know. Checking a finished Trail line takes seconds. Finding it can take minutes, and the work goes into ruling routes out.

Grids: colours and holes

Square grids have a special structure that makes them friendlier than general networks: they can be coloured like a chessboard so that linked squares always have different colours. Mathematicians call a graph like that bipartite. Every step of a path changes colour, so a path through all the squares alternates colours from start to finish.

A 3x3 grid coloured like a chessboard. The five dark squares (#) are the corners and the centre; the four light squares are the middles of the edges.

On the 3x3 grid there are five dark squares and four light ones, so a path through all nine must start and end on dark squares: dark, light, dark, and so on, nine times. That is why the spiral above starts in a corner and ends in the centre, and why no full path can start on the middle of an edge.

For full rectangles this colour rule is most of the story. Itai, Papadimitriou and Szwarcfiter showed in 1982 that deciding whether a general grid graph, one that may have holes, has a Hamiltonian path is NP-complete, and they gave exact conditions for when a path between two given squares exists in a rectangular grid (arXiv: Hamiltonian Paths in Two Classes of Grid Graphs). The holes are what make the general case hard. A plain rectangle with no holes is well understood.

At the puzzle board, the colour rule gives you a free check. On an odd-sized board such as 5x5 or 7x7, the start and end of the line are both on the corner colour. A pocket of empty squares with two more of one colour than the other cannot be covered in one pass. Path puzzle strategies shows how to use this.

Counting paths: why puzzles need numbers

An empty grid has far too many Hamiltonian paths to be a puzzle, and the counts grow very fast. The On-Line Encyclopedia of Integer Sequences lists the number of ways to number the squares of an n by n grid from 1 to n² so that each number is next to the one after it, which is the same as counting Hamiltonian paths with a start and a direction (OEIS: A096969).

Grid	Squares	Numbered paths
3x3	9	40
4x4	16	552
5x5	25	8,648
6x6	36	458,696
7x7	49	27,070,560
8x8	64	6,046,626,568

Those are Trail's four board sizes from 5x5 up: Easy is 5x5, Medium 6x6, Hard 7x7 and Expert 8x8. An empty 8x8 board allows over six billion numbered paths. Every number and every wall in a puzzle cuts that down, and a good puzzle keeps going until exactly one path is left. Puzzle Picnic makes each puzzle from a seed and has a solver check that it has exactly one solution, so the line you are looking for is always the only one.

That is also why harder Trail levels can show fewer numbers. On Hard and Expert, walls rule out routes that numbers would otherwise have to rule out, so those levels keep only the numbers they need.

Knight's tours and the fewest-exits rule

The oldest Hamiltonian path puzzle is the knight's tour: move a chess knight so it visits every square of the board exactly once. The earliest known reference is in Rudrata's Kavyalankara, a Sanskrit work on poetics from the 9th century, and Euler later studied the problem too (Wikipedia: Knight's tour). In graph terms, each square is a point and two squares are linked when a knight can jump between them.

In 1823 H. C. von Warnsdorff described a rule of thumb for finding tours: always move the knight to the square from which it will have the fewest onward moves. It works well in practice, and the idea behind it is exactly the one path puzzlers use. Squares with few exits are the ones that go wrong if you leave them for later, so deal with them first.

In a grid puzzle the fewest-exits squares are the corners, squares beside walls and squares hemmed in by the line. A corner that is not an end must use both of its two neighbours. A square left with one free neighbour can only be the last square. That is Warnsdorff's rule turned into certainty: on a puzzle with one solution you do not have to hope, you can see that the link is forced.

Why a small puzzle grid is friendly

A computer's difficulty with Hamiltonian paths is about growth: how the work explodes as networks get very large. A Trail board is not large. Even an 8x8 Expert board has 64 squares, and the numbers and walls leave one route. What matters to a human is whether that route can be found by steps that are each certain, and a well-made puzzle makes sure it can.

Three things keep a small grid friendly:

Local rules carry most of the weight. Corners, two-exit squares, numbers that cannot be joined because they are not consecutive, and links that would close a loop can all be checked by looking at a few squares.
The colour rule never fails. Because a grid is bipartite, parity checks catch impossible pockets without any search.
One solution, found by reasoning. A well-made puzzle has exactly one solution, so every square's links are fixed, and each one can be found with a reason rather than a guess.

Seen this way, a one-line puzzle is a small, friendly piece of one of mathematics' hardest problems. The numbers and walls are there to take away routes until the one that is left can be found by reasoning. Walls in Trail shows how walls do that job.

Frequently asked questions

What is the difference between a Hamiltonian path and an Eulerian path?

A Hamiltonian path visits every point of a network exactly once. An Eulerian path uses every link exactly once. Euler showed in 1735 that a simple count of each point's links can rule an Eulerian path out, and Carl Hierholzer later proved that the same count settles the question. No such simple test is known for Hamiltonian paths.

Is solving a path puzzle NP-complete?

The general problem of finding a Hamiltonian path is NP-complete, and so is the version on grid graphs with holes. A single puzzle on a fixed small board is a different matter: it is finite, and a puzzle designed to be solved by logic can be finished with local rules. NP-completeness is about how the difficulty grows as boards get very large.

Who invented the Icosian game?

William Rowan Hamilton invented it in 1856 and showed it in Dublin in 1857. He sold the rights to Jaques and Son of London for £25, and it was marketed from 1859. The puzzle asked for a round trip through all 20 corners of a dodecahedron.

Does every grid have a Hamiltonian path?

Every full rectangle does: snake back and forth along the rows. Not every pair of start and end squares works, though. On a 3x3 grid a full path must start and end on the corner colour, so it can never start on the middle of an edge.

Why does Trail need numbers if the rules already say "every square"?

An empty grid has many full paths. A 5x5 board alone has 8,648 numbered ones. The numbers, and the walls on harder levels, remove routes until exactly one is left, which is what makes the puzzle fair.

Where to go next

If you would like to put the maths to work, start with how to play Trail, then the corner, dead-end and parity techniques in path puzzle strategies. For the history of the number-path puzzles, read Hidato, Numbrix and Trail compared. And for why a fair puzzle never needs a guess, what logic-only really means explains how a solver checks for one solution. A Trail puzzle to try is on the Trail page.