Starpath

Starpath · History

The history of Starpath

Starpath is a number path puzzle: one trail that starts on star 1, passes the other stars in order and covers every tile of the sky exactly once. Mathematicians call a route like that a Hamiltonian path. The idea is more than a thousand years older than the name. It began on the chessboard, spent the 1850s on a wooden board full of pegs, and reached newspapers and phones only in this century.

The knight’s tour: every square once

The oldest known puzzle of this kind is the knight’s tour: move a chess knight so that it lands on every square of the board exactly once. Two tours survive from the ninth century. One is credited to al-Adli, a chess master who was active in Baghdad around 840. His book on the game is lost, and the tour comes down to us in a manuscript copied about 1350.

The other is in the Kavyalankara, a work on poetry by the Kashmiri writer Rudrata, usually placed in the reign of a king who ruled from 884 to 903. Rudrata’s tour covers half a board. It is hidden in a verse: write the syllables across the squares, read them again in the order the knight visits them, and the verse still makes sense.

Which of the two is older isn’t settled. The chess historian H. J. R. Murray first gave the place to Rudrata and later changed his mind in favor of al-Adli. Both dates rest on later copies and commentaries. What the record does show is that people in Baghdad and Kashmir were working on the same question at about the same time.

Euler takes the problem seriously, 1759

In 1759 Leonhard Euler presented a paper on the knight’s tour to the Berlin Academy of Sciences. Its title calls the tour a curious question that did not seem open to any analysis. The paper was printed in the Academy’s memoirs in 1766, and the Euler Archive describes it as the first mathematical paper on the subject. Euler didn’t stop at showing a tour. He gave a method for building them.

Euler had already studied a different route problem. His paper on the bridges of Königsberg, written in 1735 and published in 1741, asked for a walk that crosses every bridge exactly once. That question is about using every connection once. The knight’s tour, like Starpath, is about visiting every place once. The two sound alike, and the second has turned out to be much the harder one.

The knight’s tour has never run out of material. A count reported by Plus magazine at the University of Cambridge puts the number of tours on an 8×8 board that end a knight’s move from where they began at 13,267,364,410,532.

Kirkman, Hamilton and the Icosian Game

On August 6, 1855, the Royal Society received a paper on polyhedra from Thomas Kirkman, an English clergyman and mathematician. In it Kirkman considered a closed route along the edges of a solid that passes through every corner once. He also saw that some solids have no such route, and he described one, cut from the shape of a bee’s cell, on which the circuit cannot be drawn. The paper was read that December and printed in the Philosophical Transactions.

In 1856 William Rowan Hamilton, the Astronomer Royal of Ireland, invented what he called the Icosian Calculus, an algebra for describing routes around the twenty corners of a dodecahedron. He turned it into a game and showed it at the British Association meeting in Dublin in 1857. The board was a flat drawing of the solid with a hole at each corner for an ivory peg. Hamilton meant one player to pose a problem and the other to solve it by completing the trip through every corner.

Hamilton sold the rights to the London game maker Jaques for £25. The Puzzle Museum, which holds examples, describes two versions: the flat Icosian Game and a handheld one sold as The Travellers Dodecahedron, or A Voyage Around the World. Kirkman had asked the more general question, and asked it first. The name went to Hamilton all the same. A route that visits every point once is a Hamiltonian path, and one that returns to its start is a Hamiltonian circuit.

Number path puzzles reach the newspaper

The pencil-and-paper version puts the route in numbers. A number path puzzle prints a grid with a few numbers filled in, and you add the rest so that 1, 2, 3 and so on form one unbroken chain through every cell. The best known is the puzzle known as Hidato, invented by Gyora Benedek, an Israeli computer scientist. His syndicate, Andrews McMeel, says the idea came to him while scuba diving, watching fish swim in patterns. Hidato’s chain may step diagonally as well as straight. The sources we could check don’t give the year it first appeared in print.

The puzzle known as Numbrix, created by Marilyn vos Savant for Parade magazine, keeps the same idea and removes the diagonals. Its numbers run from 1 to 81 on a 9×9 grid, and each must sit beside the next horizontally or vertically. Most accounts date it to 2008, though we found no statement of that date from Parade itself. With orthogonal steps only, a finished grid is a Hamiltonian path drawn in digits.

Nikoli, the Japanese puzzle publisher, has a relative that is easy to confuse with these. In Numberlink you join each pair of matching numbers with its own line, and the lines may not cross or share a cell. That makes many short paths between pairs. A number path puzzle has one long path with its numbers in order.

A proof that it is hard, 1982

In November 1982 the SIAM Journal on Computing published Hamilton Paths in Grid Graphs, by Alon Itai, Christos Papadimitriou and Jayme Luiz Szwarcfiter. A grid graph is any set of squares on graph paper, joined where they touch along a side. The paper has two results. For a plain rectangle, it gives exact conditions under which a path can run from one chosen square to another through all the rest. For grids of any shape, holes included, it proves the question NP-complete.

NP-complete means, roughly, that nobody knows a method that stays fast as the board grows, and most computer scientists doubt one exists. The puzzle versions inherit this. In 2014 a team including Erik Demaine proved the same of Numberlink when every cell must be covered. In 2021 Viet-Ha Nguyen and Kévin Perrot did it for Rikudo, a number path puzzle on hexagons.

The rectangle result starts from parity. Color the grid like a chessboard and every step changes color. On a board with an even number of squares, such as 8×8, a path through all of them must begin and end on opposite colors. The authors show that this test is necessary and still not always enough. None of it makes a daily puzzle hopeless. A 64-tile board with clues is small, and the solving tips show how far forced moves will carry you.

Waypoints instead of a full count

A printed number path puzzle asks you to write a number in every cell. On a touchscreen it is more natural to drag a line, and the puzzle changes to suit. The grid shows only a handful of numbered waypoints. You draw the path with a finger, and it has to pass them in order while filling the board. Walls on some edges narrow the choices.

A prominent recent example is the puzzle known as Zip, which LinkedIn launched on March 18, 2025. Thomas Snyder of Grandmaster Puzzles, whose team helped design and edit the puzzles, set out the rules that day: draw a path through every cell, moving horizontally or vertically, starting at 1, taking the numbers in ascending order, ending on the highest, and never crossing a wall. Trade coverage described a new puzzle each day.

The mathematics underneath is old. A path through every cell is a Hamiltonian path, and numbered checkpoints are a number path puzzle with most of its numbers left out. What changed was the setting: a short puzzle, the same for everyone, with a new one tomorrow.

How LarkSpark plays it

Starpath is LarkSpark’s own number path puzzle, hosted by Rigel. The board is an 8×8 sky of 64 tiles with twelve numbered stars. Your trail starts on star 1 and moves up, down, left or right. It must reach stars 2 to 12 in order and use every tile exactly once. Dark barriers sit on some of the edges between tiles, and the trail can’t cross them. Each day’s sky is built so that star 12 is where the trail comes to rest.

Everyone gets the same sky each day. You can trim the trail back to an earlier tile, undo a single step or reset. A hint extends the correct route and counts toward your daily result. The rules cover the details, and the glossary explains the words used here. The task is one al-Adli and Hamilton would recognize: find a route that leaves nothing out.

Sources