Sprouts (1967) — A Two-Player Game of Dots and Lines on Paper That Resists Solving

Introduction — A Game of Dots and Lines That Must End

This is a pencil-and-paper game born in 1967. It is called Sprouts. It was devised by two Cambridge mathematicians, John Conway and Michael Paterson.

First, mark a few dots on a sheet. Two players take turns joining two dots with a curve, then placing a new dot on that curve. The player who cannot move loses.

No tools are needed. There is no board and there are no pieces, only new sprouts appearing on the page. Yet every move reshapes the position, and the depth of reading is surprising.

Dots and curves spreading across a sheet (illustration, AI-generated)

Context — Cambridge in 1967 and Gardner's Column

In 1967 home computers and puzzle software were not yet part of everyday life. Games travelled on paper and pencil. A mathematician's idea reached the public through a magazine article.

That role fell to Martin Gardner. His Scientific American column 'Mathematical Games' for July 1967 carried an installment titled 'Of sprouts and Brussels sprouts, games with a topological flavor'. That column was one occasion on which the game reached a wide audience.

Sources disagree on when it was devised. Lemoine and Viennot write that it was invented at Cambridge in 1967. English Wikipedia says the early 1960s. This article rests on the 1967 column, which is well attested.

We could not confirm any first-hand account of the invention by Conway or Paterson. The details of how it came about are therefore left unwritten.

An era when paper and pencil were the only tools (illustration, AI-generated)

Mechanics — The Three-Line Limit That Forces an End

The rules are short. Begin with n dots. On a move, draw a curve from one dot to another, or from a dot back to itself, and place one new dot on that curve.

Two constraints apply. A curve may not cross any other curve or itself. And no dot may have more than three lines at it; a curve returning to its own dot counts as two.

The three-line limit is what makes the game end. It lasts at most 3n−1 moves and at least 2n. In the usual form, the player who cannot move loses.

Lines are drawn in the plane, so they cannot cross. That is why Gardner's column title calls it a game 'with a topological flavor'.

One move: join two dots and place a new dot on the line (illustration, AI-generated)

Legacy — From Hand Analysis to Computers, and a Conjecture That Remains

Sprouts spread as a pastime and also became a subject of research. For each number of starting dots, who wins, the first player or the second? People have worked at that question for half a century.

According to Lemoine and Viennot, hand-checked proofs reached only 7 dots. In 1991 Applegate, Jacobson and Sleator settled up to 11 dots by computer and proposed a conjecture: the first player wins exactly when the number of dots leaves a remainder of 3, 4 or 5 on division by 6.

Lemoine and Viennot pushed the analysis to 32 dots. The 33-dot game is unresolved, and the largest computed value is the 47-dot game. Every value obtained agrees with the conjecture. Later work is reported to reach 44 dots.

The analysis uses nimbers, numbers that grew out of the theory of Nim (1901): study independent sub-positions separately, then combine them. Mathematics from the age in which Nim was solved thus serves the analysis of a paper game.

Many modern loop puzzles also forbid crossing lines; Slitherlink is one example. We found no testimony, however, that Sprouts influenced them. It is more reasonable to say that the appeal of similar constraints grew up separately.

From hand-drawn positions to computer search (illustration, AI-generated)

References

Sources consulted (the text of Gardner's column and the original Applegate et al. report were not checked; bibliographic details and figures follow the papers and Wikipedia entries below):

・Wikipedia: Sprouts (game)

・Wikipedia: John Horton Conway (states that Gardner discussed Sprouts in July 1967)

・Lemoine & Viennot: Computer analysis of Sprouts with nimbers (arXiv:1008.2320)

・Lemoine & Viennot: Computer analysis of Sprouts with nimbers (Games of No Chance 4)

・Lemoine & Viennot: A further computer analysis of Sprouts (2007)

・Sprouts game on compact surfaces (arXiv:0812.0081) (bibliography of Gardner's column and the Applegate et al. report)

・Scientific American: Mathematical Games (July 1967) (listing page; text not checked)

Closing — What This Game Showed in History

What this game showed in history is that richness does not depend on the amount of equipment. Dots, curves and one line, 'three at most', were enough to produce deep play.

It also showed that a game that seems solvable yet resists solving can anchor research. Half a century on, the conjecture is still a conjecture.

Next time you pick up a pencil, start with three dots. A first-player win quietly takes shape on the paper.

Sprouts growing across a quiet sheet (illustration, AI-generated)