The history of Links

Joining pairs without crossing is one of the oldest ideas in puzzles. Long before it filled a grid, it was a map, a pencil and a question: can everyone get where they're going without getting in each other's way?

Pencil puzzles in the newspapers

An early form of the puzzle ran in 1897 in the Brooklyn Daily Eagle, in a column by the American puzzle maker Sam Loyd.

Twenty years later the English puzzle writer Henry Ernest Dudeney put a version in his book Amusements in Mathematics (1917), as "A Puzzle for Motorists". Eight drivers set out to church one morning, each from his own house to his own church, along a network of country roads. Afterwards it turned out that no driver had ever crossed the track of another car. "Take your pencil," Dudeney wrote, "and try to trace out their various routes."

That is the puzzle you play here, give or take the churches: pairs to join, and lines that never cross. What Dudeney's version didn't ask for was that the routes cover every road.

A grid, and every cell used

The puzzle took its modern shape in Japan, popularised by Nikoli, the Tokyo publisher that also gave Sudoku its name. Nikoli ran it in two forms on a square grid: one with pairs of letters, and one with pairs of numbers.

The grid changed the puzzle. Lines now run from cell to cell instead of along roads, and the best puzzles of the kind use every cell, so no space is wasted and no line can take a lazy shortcut. That rule is what turns a tracing exercise into a chain of small deductions, and it's the rule used on this site.

From paper to phones

In the 2010s the puzzle found a new audience on touchscreens. Drawing a line with a finger is about as natural as a game gets, and the join-the-pairs puzzle became one of the most played puzzles on phones.

Hard for computers

The same problem turns up in electronics. Joining pairs of points on a circuit board with wires that never cross is the job of routing software, and computer scientists showed in the 1970s and 1980s that, in general, the problem is NP-complete: as boards grow, no known method can solve every case quickly. Later work showed the same for the puzzle itself, including the version that has to fill every cell.

A 10×10 grid is no trouble for a computer. The craft is in making puzzles that a person can solve with pleasure, one certain step at a time.