N-puzzle
Encyclopedia
Sliding puzzle
A sliding puzzle, sliding block puzzle, or sliding tile puzzle is a puzzle that challenges a player to slide usually flat pieces along certain routes to establish a certain end-configuration....
that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle. If the size is 3×3 tiles, the puzzle is called the 8-puzzle or 9-puzzle, and if 4×4 tiles, the puzzle is called the 15-puzzle or 16-puzzle named, respectively, for the number of tiles and the number of spaces. The object of the puzzle is to place the tiles in order (see diagram) by making sliding moves that use the empty space.
The n-puzzle is a classical problem for modelling algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible
Admissible heuristic
In computer science, specifically in algorithms related to Pathfinding, a heuristic function is said to be admissible if it is no more than the lowest-cost path to the goal. In other words, a heuristic is admissible if it never overestimates the cost of reaching the goal...
, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*.
Solvability
used a parity argument to show that half of the starting positions for the n-puzzle are impossible to resolve, no matter how many moves are made. This is done by considering a function of the tile configuration that is invariantInvariant (mathematics)
In mathematics, an invariant is a property of a class of mathematical objects that remains unchanged when transformations of a certain type are applied to the objects. The particular class of objects and type of transformations are usually indicated by the context in which the term is used...
under any valid move, and then using this to partition the space of all possible labeled states into two equivalence classes of reachable and unreachable states.
The invariant is the parity of the permutation of all 16 squares (15 pieces plus empty square) plus the parity of the taxicab distance moved by the empty square. This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance. In particular if the empty square is not moved the permutation of the remaining pieces must be even.
also showed that the converse holds on boards of size m×n provided m and n are both at least 2: all even permutations are solvable. This is straightforward but a little messy to prove by induction on m and n starting with m=n=2. gave another proof, based on defining equivalence classes via a hamiltonian path
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
.
studied the analogue of the 15 puzzle on arbitrary finite connected and non-separable graphs. (A graph is called separable if removing a vertex increases the number of components.) He showed that, except for polygons, and one exceptional graph on 7 vertices, it is possible to obtain all permutations unless the graph is bipartite, in which case exactly the even permutations can be obtained. The exceptional graph is a regular hexagon with one diagonal and a vertex at the center added; only 1/6 of its permutations can be obtained.
For larger versions of the n-puzzle, finding a solution is easy, but the problem of finding the shortest solution is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
. For the 15-puzzle, lengths of optimal solutions range from 0 to 80 moves; the 8-puzzle can be solved in 31 moves or fewer (integer sequence A087725).
The symmetries of the fifteen puzzle form a groupoid
Groupoid
In mathematics, especially in category theory and homotopy theory, a groupoid generalises the notion of group in several equivalent ways. A groupoid can be seen as a:...
(not a group, as not all moves can be composed); this groupoid acts on configurations.
History
Canastota, New York
Canastota is a village located inside the Town of Lenox in Madison County, New York, United States. The population was 4,425 at the 2000 census.The Village of Canastota is in the south part of the Town of Lenox.- History :...
, 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
Magic square
In recreational mathematics, a magic square of order n is an arrangement of n2 numbers, usually distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant. A normal magic square contains the integers from 1 to n2...
. Copies of the improved Fifteen Puzzle made their way to Syracuse, New York
Syracuse, New York
Syracuse is a city in and the county seat of Onondaga County, New York, United States, the largest U.S. city with the name "Syracuse", and the fifth most populous city in the state. At the 2010 census, the city population was 145,170, and its metropolitan area had a population of 742,603...
by way of Noyes' son, Frank, and from there, via sundry connections, to Watch Hill, RI, and finally to Hartford (Connecticut), where students in the American School for the Deaf
American School for the Deaf
The American School for the Deaf is the oldest permanent school for the deaf in the United States. It was founded April 15, 1817 in Hartford, Connecticut by Thomas Hopkins Gallaudet and Laurent Clerc and became a state-supported school in 1817.-History:...
started manufacturing the puzzle and, by December 1879, selling them both locally and in Boston
Boston
Boston is the capital of and largest city in Massachusetts, and is one of the oldest cities in the United States. The largest city in New England, Boston is regarded as the unofficial "Capital of New England" for its economic and cultural impact on the entire New England region. The city proper had...
(Massachusetts). Shown one of these, Matthias Rice, who ran a fancy 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, Dr. Charles Pevey, a dentist in Worcester, Massachusetts
Worcester, Massachusetts
Worcester is a city and the county seat of Worcester County, Massachusetts, United States. Named after Worcester, England, as of the 2010 Census the city's population is 181,045, making it the second largest city in New England after Boston....
, garnered some attention by offering a cash reward for a solution to the Fifteen Puzzle.
The game became a craze in the U.S.
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
in February 1880, Canada
Canada
Canada is a North American country consisting of ten provinces and three territories. Located in the northern part of the continent, it extends from the Atlantic Ocean in the east to the Pacific Ocean in the west, and northward into the Arctic Ocean...
in March, Europe
Europe
Europe is, by convention, one of the world's seven continents. Comprising the westernmost peninsula of Eurasia, Europe is generally 'divided' from Asia to its east by the watershed divides of the Ural and Caucasus Mountains, the Ural River, the Caspian and Black Seas, and the waterways connecting...
in April, but that craze had pretty much dissipated by July. Apparently the puzzle was not introduced to Japan
Japan
Japan is an island nation in East Asia. Located in the Pacific Ocean, it lies to the east of the Sea of Japan, China, North Korea, South Korea and Russia, stretching from the Sea of Okhotsk in the north to the East China Sea and Taiwan in the south...
until 1889.
Noyes Chapman had applied for a patent on his "Block Solitaire Puzzle" on February 21, 1880. However, that 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.
Sam Loyd
Sam LoydSam Loyd
Samuel Loyd , born in Philadelphia and raised in New York, was an American chess player, chess composer, puzzle author, and recreational mathematician....
claimed from 1891 until his death in 1911 that he invented the puzzle, for example writing in the Cyclopedia of Puzzles (published 1914): "The older inhabitants of Puzzleland will remember how in the early seventies I drove the entire world crazy over a little box of movable pieces which became known as the "14-15 Puzzle". However, Loyd had nothing to do with the invention or initial popularity of the puzzle, and in any case the craze was in 1880, not the early 1870s. Lloyd's first article about the puzzle was published in 1896 and it wasn't until 1891 that he first claimed to have been the inventor.
Some later interest was fuelled by Loyd offering a $1,000 prize for anyone who could provide a solution for achieving a particular combination specified by Loyd, namely reversing the 14 and 15. This was impossible, as had been shown over a decade earlier by , as it required a transformation from an even to an odd combination.
Miscellaneous
The Minus CubeMinus Cube
The Minus Cube is a 3D mechanical variant of the n-puzzle which was manufactured in the Soviet Union. It consists of a bonded transparent plastic box containing seven small cubes, each glued together from two U-shape parts: one white and one coloured. The length of one side of the interior of the...
, manufactured in the USSR
Soviet Union
The Soviet Union , officially the Union of Soviet Socialist Republics , was a constitutionally socialist state that existed in Eurasia between 1922 and 1991....
, is a 3D
Three-dimensional space
Three-dimensional space is a geometric 3-parameters model of the physical universe in which we live. These three dimensions are commonly called length, width, and depth , although any three directions can be chosen, provided that they do not lie in the same plane.In physics and mathematics, a...
puzzle with similar operations to the 15-puzzle.
Bobby Fischer
Bobby Fischer
Robert James "Bobby" Fischer was an American chess Grandmaster and the 11th World Chess Champion. He is widely considered one of the greatest chess players of all time. Fischer was also a best-selling chess author...
was an expert at solving the 15-Puzzle. He had been timed to be able to solve it within 25 seconds; Fischer demonstrated this on November 8, 1972 on The Tonight Show Starring Johnny Carson
The Tonight Show Starring Johnny Carson
The Tonight Show Starring Johnny Carson is a talk show hosted by Johnny Carson under the Tonight Show franchise from 1962 to 1992. It originally aired during late-night....
.
See also
- Rubik's CubeRubik's CubeRubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...
- Minus CubeMinus CubeThe Minus Cube is a 3D mechanical variant of the n-puzzle which was manufactured in the Soviet Union. It consists of a bonded transparent plastic box containing seven small cubes, each glued together from two U-shape parts: one white and one coloured. The length of one side of the interior of the...
- Sliding puzzleSliding puzzleA sliding puzzle, sliding block puzzle, or sliding tile puzzle is a puzzle that challenges a player to slide usually flat pieces along certain routes to establish a certain end-configuration....
- Combination puzzlesCombination puzzlesA combination puzzle, also known as a sequential move puzzle, is a puzzle which consists of a set of pieces which can be manipulated into different combinations by a group of operations. The puzzle is solved by achieving a particular combination starting from a random combination...
- Mechanical puzzles
- Jeu de taquinJeu de taquinIn the mathematical field of combinatorics, jeu de taquin is a construction due to which defines an equivalence relation on the set of skew standard Young tableaux. A jeu de taquin slide is a transformation where the numbers in a tableau are moved around in a way similar to how the pieces in the...
, an operation on skew Young tableaux similar to moves of the 15 puzzle. - Pebble motion problemsPebble Motion ProblemsThe pebble motion problems, or pebble motion on graphs, are a set of related problems in graph theory dealing with the movement of multiple objects from vertex to vertex in a graph with a constraint on the number of pebbles that can occupy a vertex at any time...