Hamiltonian paths: the math behind number path puzzles
A number path puzzle asks for one line that visits every cell of the board exactly once. Mathematicians have a name for a line like that: a Hamiltonian path. It is named after an Irish mathematician who turned the idea into a parlour game, and it is one of the classic hard problems of computer science. This guide explains the idea, where it came from, and a coloring trick that helps on every board of Pebble Path.
Paths, cycles and graphs
Mathematicians describe these puzzles with graphs: dots joined by lines. Each cell is a dot, and two dots are joined when their cells share a side with no wall between them. A Hamiltonian path visits every dot exactly once; a Hamiltonian cycle also returns to its start. A Pebble Path solution is a Hamiltonian path that starts on 1, ends on the last number and meets the numbers in order.
Hamilton's icosian game
William Rowan Hamilton worked out the mathematics in 1856, in an algebra he called the icosian calculus. At the 1857 meeting of the British Association in Dublin he showed it through what the meeting's report called "an amusing game, which he called the Icosian". The board was a flat drawing of a dodecahedron, the solid with 12 faces and 20 corners, with holes for numbered pegs. The task was to travel along the edges, visit every corner once and come home: a Hamiltonian cycle. The dodecahedron has 30 such round trips.
Hamilton sold the rights to the London game makers Jaques and Son for £25, and from 1859 they sold it under titles that included The Travellers Dodecahedron, or a voyage around the world. It was too easy to catch on and was not a commercial success. Hamilton was not alone, either: at about the same time Thomas Kirkman in England was studying the same kind of cycle on other solids. The name stuck to Hamilton anyway.
The knight's tour
The most famous Hamiltonian path is far older than Hamilton. A knight's tour moves a chess knight so that it lands on 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. Leonhard Euler studied tours in 1759, and in 1823 H. C. von Warnsdorff described a simple rule of thumb for finding one: always jump to the square with the fewest onward moves.
The numbers are enormous. An 8 by 8 board has 26,534,728,821,064 closed tours, which end a knight's move from the start, counting each direction separately. A knight always jumps from a light square to a dark one or back, so a closed tour alternates colors all the way round. That is impossible on a board with an odd number of squares, which is why a 5 by 5 board has no closed tour. Keep that coloring idea in mind; it comes back below.
Why paths are hard, and puzzles are not
Finding a Hamiltonian path in an arbitrary network is one of the classic hard problems. In 1972 Richard Karp included the Hamiltonian circuit problem in his famous list of 21 NP-complete problems. NP-complete means that a proposed answer is quick to check, but nobody knows a method that finds answers quickly on every large network, and finding one would settle a famous open question in computer science.
Grids are no escape. In 1982 Alon Itai, Christos Papadimitriou and Jayme Szwarcfiter proved that the problem stays NP-complete on grids with holes in them. On a plain rectangle the problem becomes easy: the same paper gave exact conditions for when a path between two chosen cells exists. Walls take a board out of that easy case, because each one removes a link between two cells.
A puzzle board is small, and it is built to have one answer. A 7 by 7 board, the size of the Pebble Path daily, has 27,070,560 ways to number its cells along a path, counting each direction, and the numbers and walls must rule out all of them but one. Nobody solving a board lists them. Local facts do the work: a corner cell has only two neighbours, so unless the line starts or ends there, it must use both, and a cell walled in on two sides behaves the same way. Then there is color.
The checkerboard trick
Color the board like a chessboard. Every step of the line goes to a side neighbour, and side neighbours always have different colors. So the line alternates, dark, light, dark, light, all the way to the end. That simple fact limits where a path can start and finish.
Take a 5 by 5 board with dark corners. It has 13 dark cells and 12 light ones. Number the cells along any path through all 25: cells 1, 3, 5 and so on up to 25 share one color, and cells 2, 4 and so on up to 24 share the other. There are 13 odd positions but only 12 light cells, so the odd positions must be the dark cells. The path starts on a dark cell and ends on one.
A 4 by 4 board has 8 cells of each color, and a full path's end cells sit in positions 1 and 16, one odd and one even, so it starts and ends on different colors. Our brute-force check of all 552 numberings of the 4 by 4 board, and all 8,648 of the 5 by 5, agrees. In general:
- Odd number of cells, as on 5 by 5, 7 by 7 and 9 by 9: both ends are on the corner color. On 3 by 3 that means a corner or the centre, never one of the four edge cells.
- Even number of cells, as on 4 by 4, 6 by 6 and 8 by 8: the ends are on opposite colors.
- Any stretch of the line that starts and ends on the same color holds one more cell of that color than of the other. A stretch that starts and ends on different colors holds equal numbers.
The last rule is the one that helps mid-puzzle. Suppose part of the board is cut off, by walls or by cells your line has already used, so that only two of its cells lead out. If the line neither starts nor ends inside, it must come in through one of those two cells, cover the whole part in one stretch and leave through the other. Count the part's colors and note the colors of the two doorway cells. If they cannot fit the pattern above, the line must start or end inside. So if the part holds neither 1 nor the last number and the count does not fit, the line drawn so far has gone wrong somewhere.
How numbers pick one path
Numbers do more than mark the ends, but they work through their order. A single number between the start and the end tells you nothing new, because a line through every cell passes every cell somewhere between its two ends. A second number does help: now the line has to meet the two in the right order.
On this 3 by 3 board, exactly two paths run from the top left corner to the bottom right one: a snake along the rows and a snake down the columns. A 2 anywhere in between would fit both. Place a 2 and a 3 so that one snake meets them in order and the other does not, and one path remains. Every Pebble Path board, from 4 by 4 up to 9 by 9, has exactly one line that fits its numbers and walls, so you never have to guess a turn. For solving advice, see our number path puzzle tips, and for how a computer proves a board has one answer, read why good logic puzzles have exactly one solution.