Nine dots puzzle

In 1867, in the French chess journal Le Sphinx, an intellectual precursor to the nine dots puzzle appeared credited to Sam Loyd.{{cite journal |last1=Journoud |first1=Paul |author-link=Paul Journoud |journal=Le Sphinx: Journal des échecs |volume=2 |issue=14 |title=Questions Du Sphinx |date=1867 |page=[https://www.digitale-sammlungen.de/en/view/bsb10431927?page=168,169 216] |language=French |url=https://www.digitale-sammlungen.de/en/view/bsb10431927?page=168,169 |quote=Placer la Dame ot l’on voudra, lui faire parcourir par des marches suivies et régulières toutes les cases de I’échiquier, et la ramener au quatorzième coup à son point de départ. Place the queen wherever you want, make her go through all the squares of the chessboard by regular steps, and bring her back to her starting point at the fourteenth move.}}{{R|singmaster}} 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.{{efn|As it turned out later, the added constraint can be dropped, that is, moving the pen only akin to the queen in chess (i.e., vertically, horizontally, or diagonally) and only staying within the square lattice. Even without this constraint, the optimal solution is still 14 moves.{{r|gs1970}}}}

File:TheStrandMagazine1907bColombusEgg.jpg, 1907]]

In 1907, the nine dots puzzle appears in an interview with Sam Loyd in The Strand Magazine:{{cite magazine |last1=Bain |first1=George Grantham |author-link=George Grantham Bain |title=The Prince of Puzzle-Makers. An Interview with Sam Loyd. |magazine=The Strand Magazine |date=1907 |page=[https://archive.org/details/TheStrandMagazineVolume34/page/775 775] |url=https://archive.org/details/TheStrandMagazineVolume34/page/775}}{{R|singmaster}}

: "[...] 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.{{cite book |last1=Pearson |first1=A. Cyril Pearson |title=The Twentieth Century Standard Puzzle Book |year=1907 |url=https://www.gutenberg.org/files/63884/63884-h/63884-h.htm#PageI36 |page=36}}{{R|singmaster}}

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.{{cite news |title=Advertising for Elgin Creamery Co |page=6 |location=Washington, D.C. |url=https://chroniclingamerica.loc.gov/lccn/sn83045462/1908-03-02/ed-1/seq-6/ |work=Evening star |date=1908-03-02}} From at least 1910, Pearson's "nine dots"-version appeared in puzzle sections.{{cite news |title=Three Puzzles Are Amusing |location=North Platte, Nebraska |url=https://chroniclingamerica.loc.gov/lccn/2010270504/1910-05-20/ed-1/seq-7/ |work=The North Platte semi-weekly tribune. |date=1910-05-20 |page=7}}{{cite news |work=Audubon County journal |location=Exira, Iowa |page=2 |title=Three Puzzles are Amusing |url=https://chroniclingamerica.loc.gov/lccn/sn87057934/1910-07-14/ed-1/seq-2/ |date=1910-07-14}}{{cite news |work=The Richmond palladium and sun-telegram |location=Richmond, Indiana |page=6 |title=After Dinner Tricks |url=https://chroniclingamerica.loc.gov/lccn/sn86058226/1922-06-22/ed-1/seq-6/ |date=1922-06-22}}

File:Eggpuzzle.jpg's Cyclopedia of Puzzles, 1914]]

In 1914, Sam Loyd's Cyclopedia of Puzzles is published posthumously by his son (also named Sam Loyd).{{cite book |last1=Gardner |first1=Martin |author-link=Martin Gardner |title=Mathematical puzzles & diversions |date=1959 |location=New York, N.Y. |publisher=Simon and Schuster |chapter=Chapter 9: Sam Loyd: America's Greatest Puzzlist |pages=[https://archive.org/details/mathematicalpuzz00gard/page/84 84],[https://archive.org/details/mathematicalpuzz00gard/page/89 89] |url-access=registration |url=https://archive.org/details/mathematicalpuzz00gard}} The puzzle is therein explained as follows:Sam Loyd, [http://www.mathpuzzle.com/loyd/cop300-301.html Cyclopedia of Puzzles]. (The Lamb Publishing Company, 1914){{R|singmaster}}

: 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.[http://www.mathpuzzle.com/loyd/cop300-301.html Facsimile from Cyclopedia of Puzzles - Columbus's Egg Puzzle is on right-hand page]

File:Ninedots.svg

It is possible to mark off the nine dots in four lines.{{cite web |title=Sam Loyd's Cyclopedia of 5000 Puzzles, Tricks, and Conundrums With Answers |url=https://archive.org/details/CyclopediaOfPuzzlesLoyd/page/n191 |date=1914 |page=[https://archive.org/details/CyclopediaOfPuzzlesLoyd/page/n191 380]}} 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.Daniel Kies, [http://papyr.com/hypertextbooks/comp2/9dots.htm "English Composition 2: Assumptions: Puzzle of the Nine Dots"], retr. Jun. 28, 2009.

The inherent difficulty of the puzzle has been studied in experimental psychology.{{cite journal|last1=Maier|first1=Norman R. F.|last2=Casselman|first2=Gertrude G. |title=Locating the Difficulty in Insight Problems: Individual and Sex Differences|journal=Psychological Reports|date=1 February 1970|volume=26|issue=1|pages=103–117|doi=10.2466/pr0.1970.26.1.103|pmid=5452584|s2cid=43334975}}{{cite journal|last=Lung|first=Ching-tung|author2=Dominowski, Roger L. |title=Effects of strategy instructions and practice on nine-dot problem solving.|journal=Journal of Experimental Psychology: Learning, Memory, and Cognition|date=1 January 1985|volume=11|issue=4|pages=804–811|doi=10.1037/0278-7393.11.1-4.804}}

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.

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.W. Neville Holmes, [http://eprints.utas.edu.au/2000 Fashioning a Foundation for the Computing Profession], July 2000 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 (see fold-and-cut theorem).{{cite book|first=Alice M.|last=Tybout|year=1995|contribution=Presidential Address: The Value of Theory in Consumer Research|title=Advances in Consumer Research, Volume 22|editor1-first=Frank R.|editor1-last=Kardes|editor2-first=Mita|editor2-last=Sujan|location=Provo, Utah|publisher=Association for Consumer Research|pages=1–8|contribution-url=https://www.acrwebsite.org/volumes/7659/volumes/v22/NA-22/full}}

{{multiple image

|image1=nine_dots_puzzle_thick.svg|caption1=Three lines connect thick dots

|image2=nine_dots_puzzle_roll.svg|caption2=One-line rolled cylinder

|total_width=400

|align=none}}

File:sixteen_dots_puzzle_solution.svg

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

Various such extensions were stated as puzzles by Dudeney and Loyd with different added constraints.{{cite web |last2=Gardner |first2=Martin |author-link2=Martin Gardner |last1=Dudeney |first1=Henry |author-link1=Henry Dudeney |date=1967 |title=536 Puzzles And Curious Problems |page=376 |url=https://archive.org/details/536PuzzlesAndCuriousProblems/page/n375}}

In 1955, Murray S. Klamkin showed that if {{math|n > 2}}, then {{math|2n − 2}} line segments are sufficient and conjectured that it is necessary too.{{cite journal |last1=Klamkin |first1=M. S. |author-link=Murray S. Klamkin |title=Polygonal Path Covering a Square Lattice (E1123) |journal=The American Mathematical Monthly |date=1955-02-01 |volume=62 |issue=2 |page=124 |doi=10.2307/2308156|jstor=2308156 }}{{R|gardner}} In 1956, the conjecture was proven by John Selfridge.{{cite journal |last1=Selfridge |first1=John |title=Polygonal Path Covering a Square Lattice (E1123, Addentum) |journal=The American Mathematical Monthly |date=June 1955 |volume=62 |issue=6 |page=443 |doi=10.2307/2307008|jstor=2307008 }}{{R|gardner}}{{cite web |last1=Singmaster |first1=David |author-link=David Singmaster |title=Sources In Recreational Mathematics, An Annotated Bibliography (8th preliminary edition): 6.AK. Polygonal Path Covering N X N Lattice Of Points, Queen's Tours, etc. |url=https://www.puzzlemuseum.com/singma/singma6/SOURCES/singma-sources-edn8-2004-03-19.htm#_Toc69534017 |website=www.puzzlemuseum.com |date=2004-03-19}}

In 1970, Solomon W. Golomb and John Selfridge showed that the unicursal polygonal path of {{math|2n − 2}} segments exists on the {{math|n × n}} array for all {{math|n > 3}} with the further constraint that the path be closed, i.e., it starts and ends at the same point.{{R|gardner}} Moreover, the further constraint that the closed path remain within the convex hull of the array of dots can be satisfied for all {{math|n > 5}}. Finally, various results for the {{math|a × b}} array of dots are proven.{{cite journal |last1=Golomb |first1=Solomon W. |author-link1=Solomon W. Golomb |last2=Selfridge |first2=John L. |author-link2=John Selfridge |title=Unicursal Polygonal Paths And Other Graphs On Point Lattices |journal=Pi Mu Epsilon Journal |date=1970 |volume=5 |issue=3 |pages=107–117 |jstor=24344915 |url=https://www.jstor.org/stable/24344915 |issn=0031-952X}}

The Nine Dots Prize, named after the puzzle,{{cite web |title=The Nine Dots Prize Identity |url=https://ruddstudio.com/project/the-nine-dots-prize-identity/ |website=Rudd Studio |access-date=19 November 2018}} is a competition-based prize for "creative thinking that tackles contemporary societal issues."{{cite web |title=Home |url=https://ninedotsprize.org/ |website=The Nine Dots Prize |publisher=Kadas Prize Foundation |access-date=19 November 2018}} 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.{{cite web |title=Nine Dots Prize |url=http://www.crassh.cam.ac.uk/programmes/nine-dots-prize |website=CRASSH |publisher=The University of Cambridge |access-date=19 November 2018}}

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

{{notelist}}

{{reflist}}

Category:Mathematical puzzles