The "nine dots" puzzle. The puzzle asks to link all nine dots using four straight lines or fewer, without lifting the pen.

The nine dots puzzle is a mathematical puzzle whose task is to connect nine squarely arranged points with a pen by four (or fewer) straight lines without lifting the pen.

The puzzle has appeared under various other names over the years.

History

In 1867, in the French chess journal Le Sphinx, an intellectual precursor to the nine dots puzzle appeared credited to Sam Loyd.^[1][2] Said chess puzzle corresponds to a "64 dots puzzle", i.e., marking all dots of an 8-by-8 square lattice, with an added constraint.^{[lower-alpha 1]}

The Columbus Egg Puzzle from The Strand Magazine, 1907

In 1907, the nine dots puzzle appears in an interview with Sam Loyd in The Strand Magazine:^[4][2]

"[...] Suddenly a puzzle came into my mind and I sketched it for him. Here it is. [...] The problem is to draw straight lines to connect these eggs in the smallest possible number of strokes. The lines may pass through one egg twice and may cross. I called it the Columbus Egg Puzzle."

In the same year, the puzzle also appeared in A. Cyril Pearson's puzzle book. It was there named a charming puzzle and involved nine dots.^[5][2]

Both versions of the puzzle thereafter appeared in newspapers. From at least 1908, Loyd's egg-version ran as advertising for Elgin Creamery Co in Washington, DC., renamed to The Elgin Creamery Egg Puzzle.^[6] From at least 1910, Pearson's "nine dots"-version appeared in puzzle sections.^[7][8][9]

Christopher Columbus' Egg Puzzle in Sam Loyd's Cyclopedia of Puzzles, 1914

In 1914, Sam Loyd's Cyclopedia of Puzzles is published posthumously by his son (also named Sam Loyd).^[10] The puzzle is therein explained as follows:^[11][2]

The funny old King is now trying to work out a second puzzle, which is to draw a continuous line through the center of all of the eggs so as to mark them off in the fewest number of strokes. King Puzzlepate performs the feat in six strokes, but from Tommy's expression we take it to be a very stupid answer, so we expect our clever puzzlists to do better; [...]

Sam Loyd's naming of the puzzle is an allusion to the story of Egg of Columbus.^[12]

In the 1941 compilation The Puzzle-Mine: Puzzles Collected from the Works of the Late Henry Ernest Dudeney, the puzzle is attributed to Dudeney himself and not Loyd.^[13]

Solution

One solution of the nine dots puzzle.

It is possible to mark off the nine dots in four lines.^[14] To do so, one goes outside the confines of the square area defined by the nine dots themselves. The phrase thinking outside the box, used by management consultants in the 1970s and 1980s, is a restatement of the solution strategy. According to Daniel Kies, the puzzle seems hard because we commonly imagine a boundary around the edge of the dot array.^[15]

The inherent difficulty of the puzzle has been studied in experimental psychology.^[16][17]

Changing the rules

Various published solutions break the implicit rules of the puzzle in order to achieve a solution with even fewer than four lines. For instance, if the dots are assumed to have some finite size, rather than to be infinitesimally-small mathematical grid points, then it is possible to connect them with only three slightly-slanted lines. Or, if the line is allowed to be arbitrarily thick, then one line can cover all of the points.^[18]

Another way to use only a single line involves rolling the paper into a three-dimensional cylinder, so that the dots align along a single helix (which, as a geodesic of the cylinder, could be considered to be in some sense a straight line). Thus a single line can be drawn connecting all nine dots—which would appear as three lines in parallel on the paper, when flattened out.^[19] It is also possible to fold the paper flat, or to cut the paper into pieces and rearrange it, in such a way that the nine dots lie on a single line in the plane.^[18]

Three lines connect thick dots

One-line rolled cylinder

Planar generalization

Cyclic solutions for the 4-by-4 version ^[20]

Instead of the 3-by-3 square lattice, generalizations have been proposed in the form of the least amount of lines needed on an n-by-n square lattice. Or, in mathematical terminology, the minimum-segment unicursal polygonal path covering an n × n array of dots.

Various such extensions were stated as puzzles by Dudeney and Loyd with different added constraints.^[21]

In 1955, Murray S. Klamkin showed that if n > 2, then 2n − 2 line segments are sufficient and conjectured that it is necessary too.^[22][21] In 1956, the conjecture was proven by John Selfridge.^[23][21][2]

In 1970, Solomon W. Golomb and John Selfridge showed that the unicursal polygonal path of 2n − 2 segments exists on the n × n array for all n > 3 with the further constraint that the path be closed, i.e., it starts and ends at the same point.^[21] Moreover, the further constraint that the closed path remain within the convex hull of the array of dots can be satisfied for all n > 5. Finally, various results for the a × b array of dots are proven.^[3]

Generalization to higher dimensions

The nine dots puzzle can be generalized to higher dimensions, by simply defining the grid ${\displaystyle G_{3}^{k}:=\{\{0,1,2\}\times \{0,1,2\}\times \cdots \times \{0,1,2\}\}\subset \mathbb {R} ^{k}}$ and asking to find (one of) the shortest polygonal chain(s) (i.e., the polygonal chain with the fewest edges) that visits all those ${\displaystyle 3^{k}}$ points.

In 2020, it has been proven^[24] that the optimal solution for the above-mentioned problem has exactly ${\displaystyle {\frac {3^{k}-1}{2}}}$ links, for every positive integer ${\displaystyle k}$. The given constructive solution is a straight generalization of the well-known covering trail that solves the ${\displaystyle k=2}$ case.

Moreover, it is even possible to further extend the given optimization problem to any arbitrary grid ${\displaystyle G_{n}^{k}:=\{\{0,1,\ldots ,n-1\}\times \{0,1,\ldots ,n-1\}\times \cdots \times \{0,1,\ldots ,n-1\}\}\subset \mathbb {R} ^{k}}$, but only the easiest cases have been solved at present (e.g., in 2022 Rinaldi and Ripà showed that the solution for the ${\displaystyle n=2}$ case is a trail/cycle of length ${\displaystyle 3\cdot 2^{k-2}}$ for every ${\displaystyle k\in \mathbb {N} -\{0,1\}}$, while it is known that the optimal solution for the ${\displaystyle (n=4,k=3)}$ case has ${\displaystyle 21}$, or ${\displaystyle 22}$, or ${\displaystyle 23}$ links).

The Nine Dots Prize

The Nine Dots Prize, named after the puzzle,^[25] is a competition-based prize for "creative thinking that tackles contemporary societal issues."^[26] It is sponsored by the Kadas Prize Foundation and supported by the Cambridge University Press and the Centre for Research in the Arts, Social Sciences and Humanities at the University of Cambridge.^[27]

See also

• Einstellung effect
• Eureka effect
• Functional fixedness
• Gordian Knot
• Kobayashi Maru
• Lateral thinking

Notes

References