Editing 15 puzzle (section)

==History==
[[Image:15-puzzle-loyd.svg|thumb|right|[[Sam Loyd]]'s unsolvable 15 Puzzle, with tiles 14 and 15 exchanged. This puzzle is not solvable as it would require a change of the invariant to move it to the solved state.]]
[[Image:Great presidential puzzle2.jpg|thumb|U.S. political cartoon about finding a Republican presidential candidate in 1880]]
The puzzle was "invented" by Noyes Palmer Chapman,<ref name="slocum-sonneveld" /> a postmaster in [[Canastota, New York]], who is said to have shown friends, as early as 1874, a precursor puzzle consisting of 16 numbered blocks that were to be put together in rows of four, each summing to 34 (see [[magic square]]). Copies of the improved 15 puzzle made their way to [[Syracuse, New York]], by way of Chapman's son, Frank, and from there, via sundry connections, to [[Watch Hill, Rhode Island]], and finally to [[Hartford]], [[Connecticut]], where students in the [[American School for the Deaf]] started manufacturing the puzzle. By December 1879, these were sold both locally and in [[Boston]], [[Massachusetts]]. Shown one of these, Matthias Rice, who ran a woodworking business in Boston, started manufacturing the puzzle sometime in December 1879 and convinced a "Yankee Notions" fancy goods dealer to sell them under the name of "Gem Puzzle." In late January 1880, Charles Pevey, a dentist in [[Worcester, Massachusetts|Worcester]], Massachusetts, garnered some attention by offering a cash reward for a solution to the 15 Puzzle.<ref name="slocum-sonneveld"/>

The game became a [[Fad|craze]] in the U.S. in 1880.<ref>{{harvtxt|Slocum|Singmaster|2009|p=15}}</ref>

Chapman applied for a patent on his "Block Solitaire Puzzle" on February 21, 1880. However, this patent was rejected, likely because it was not sufficiently different from the August 20, 1878 "Puzzle-Blocks" patent (US 207124) granted to Ernest U. Kinsey.<ref name="slocum-sonneveld">''The 15 Puzzle'', by Jerry Slocum & Dic Sonneveld, 2006. {{ISBN|1-890980-15-3}}</ref>

=== Sam Loyd ===
[[File:Sam Loyd - The 14-15 Puzzle in Puzzleland.jpg|thumb|left|Sam Loyd's 1914 illustration of the unsolvable variation.]]
From 1891 until his death in 1911, [[Sam Loyd]] claimed that he had invented the puzzle. However, Loyd had no connection to the invention or initial popularity of the puzzle. Loyd's first article about the puzzle was published in 1886, and it was not until 1891 that he first claimed to be the inventor.<ref name="slocum-sonneveld" /><ref>Barry R. Clarke, ''Puzzles for Pleasure'', pp.10-12, Cambridge University Press, 1994 {{ISBN|0-521-46634-2}}.</ref>

Some later interest was fueled by Loyd's offer of a $1,000 prize ({{Inflation|US|1000|1891|fmt=eq}}) to anyone who could provide a solution for achieving a particular combination specified by Loyd, namely reversing the 14 and 15, which Loyd called the '''14-15 puzzle'''.<ref name="Korf,2000">{{Citation | first=R. E. | last=Korf|author-link=Richard E. Korf | editor1-first=B. Y. | editor2-last=Walsh | editor2-first=T. | chapter-url=https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf | doi=10.1007/3-540-44914-0_3 | series=SARA 2000. Lecture Notes in Computer Science | pages=45–55 | publisher=Springer, Berlin, Heidelberg | year=2000 | isbn=978-3-540-67839-7 | access-date=2010-04-26 | chapter=Recent Progress in the Design and Analysis of Admissible Heuristic Functions | volume=1864 | editor1-last=Choueiry | title=Abstraction, Reformulation, and Approximation | url=http://www.cs.iastate.edu/~honavar/korf2000.pdf | archive-date=2010-08-16 | archive-url=https://web.archive.org/web/20100816065953/http://www.cs.iastate.edu/~honavar/korf2000.pdf | url-status=dead }}</ref> This is impossible, as had been shown over a decade earlier by {{harvtxt|Johnson|Story|1879}}, because it requires a transformation from an even to an odd permutation.