A solved 15-puzzle

The n-puzzle is known in various versions, including the 8 puzzle, the 15 puzzle, and with various names. It is a sliding puzzle that consists of a grid of numbered squares with one square missing, and the labels on the squares jumbled up. A sliding puzzle, sliding block puzzle, or sliding tile puzzle challenges a player to slide usually flat pieces along certain routes (usually on a board to establish If the grid is 3×3, the puzzle is called the 8-puzzle or 9-puzzle. If the grid is 4×4, the puzzle is called the 15-puzzle or 16-puzzle. The goal of the puzzle is to unjumble the squares by only making moves which slide squares into the empty space, in turn revealing another empty space in the position of the moved piece.

The n-puzzle is a classical problem for modelling algorithms involving heuristics. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation In Computer science, a heuristic algorithm or simply a Heuristic is an Algorithm that ignores whether the solution to the problem can be proven 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. Taxicab geometry, considered by Hermann Minkowski in the 19th century is a form of Geometry in which the usual metric of Euclidean geometry Note that both are admissible, i. e. , they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*. In Computer science, A* (pronounced "A star" is a best-first, Graph search algorithm that finds the least-cost path from a given initial

Solvability

A simple parity argument shows that half of the starting positions for the n-puzzle are impossible to resolve, no matter how many moves are made. In Mathematics, the parity of an object states whether it is even or odd This is done by considering a function of the tile configuration that is invariant 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. In Mathematics, an invariant is something that does not change under a set of transformations The property of being an invariant is invariance. In Mathematics, given a set X and an Equivalence relation ~ on X, the equivalence class of an element a in X

In the case of a rectangular game of p rows and q columns:

• if q is odd the invariant is the parity (odd or even) of the number of pairs of pieces in reverse order (the parity of the permutation). In Mathematics, the Permutations of a Finite set (ie the bijective mappings from the set to itself fall into two classes of equal size the even For the order of the 15 pieces consider line 2 after line 1, etc. , like words on a page.
• if q is even the invariant is the parity of the number of pairs of pieces in reverse order plus the row number of the empty square.

Thus, for the 15-puzzle, an even permutation of the order of the 15 pieces can only be obtained if the empty square is not moved or moved two rows, and an odd permutation of the order of the 15 pieces can only be obtained if the empty square is moved one or three rows.

By contrast, note that considering the parity of permutations of all 16 squares (15 pieces plus empty square) is not meaningful here, because it changes with every move.

If playing a solvable version of the 15 puzzle you can take the shortcut of solving the squares 1,2,3,4,5,9 and 13 , you then only have a 3x3 grid to solve. This speeds the process up quite considerably.

Noyes Chapman's Fifteen Puzzle

Noyes Chapman's unsolvable 15-puzzle, with tiles 14 and 15 exchanged

In its most famous version, the Fifteen Puzzle, initially known as the Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square, and many others, has a 4×4 grid, where in the initial configuration the pieces are in ascending order, except that pieces 14 and 15 are in reverse order. This puzzle is not solvable because it would require a change of the invariant.

History

Sam Loyd claimed from 1891 until his death in 1911 that he invented the puzzle. For people with a similar name see Sam Lloyd. Samuel Loyd ( January 31, 1841 &ndash April 10, 1911 But he had nothing to do with the invention or popularity of the puzzle. ^[1] The puzzle was "invented" by Noyes Palmer Chapman, 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. Canastota is a Village located inside the Town of Lenox in Madison County New York, United States. In Recreational mathematics, a magic square of order n is an arrangement of n ² numbers usually distinct Integers in a square, such Copies of the improved Fifteen Puzzle made their way to Syracuse, New York 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 started manufacturing the puzzle and, by December 1879, selling them both locally and in Boston (Massachusetts). Syracuse (locally ˈsɛrəkjuːs sometimes ˈsɪrəkjuːs or /ˈsɪərəkjuːs/ by non-natives is a city in Central New York, USA. See Watch Hill (Lake District for fells in the English Lake District called Watch Hill The American School for the Deaf (ASD was the first institution for the education of the Deaf in America. 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, garnered some attention by offering a cash reward for a solution to the Fifteen Puzzle. Worcester (ˈwʊstɚ is a City in the state of Massachusetts in the United States of America. The game became a craze in the U.S. in February 1880, Canada in March, Europe in April, but that craze had pretty much dissipated by July. The United States of America —commonly referred to as the Country to "Dominion of Canada" or "Canadian Federation" or anything else please read the Talk Page Apparently the puzzle was not introduced to Japan until 1889. For a topic outline on this subject see List of basic Japan topics. Noyes Chapman had applied for a patent on his "Block Solitaire Puzzle" on February 21, 1880. Events 362 - Athanasius returns to Alexandria. 1245 - Thomas, the first known Bishop of Finland Year 1880 ( MDCCCLXXX) was a Leap year starting on Thursday (link will display the full calendar of the Gregorian calendar (or a Leap year However, that patent was rejected, likely because it was not sufficiently different from the August 20, 1878 "Puzzle-Blocks" patent granted to Ernest U. Events 636 - Battle of Yarmouk: Arab forces led by Khalid ibn al-Walid take control of Syria and Palestine Year 1878 ( MDCCCLXXVIII) was a Common year starting on Tuesday (link will display the full calendar of the Gregorian calendar (or a Common Kinsey. ^[1]

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 (nondeterministic Polynomial-time hard in Computational complexity theory, is a class of problems informally "at least as hard as the hardest problems ^[2]

In the USSR the Minus Cube was manufactured, a 3D variant of the 15-puzzle. The Union of Soviet Socialist Republics (USSR was a constitutionally Socialist state that existed in Eurasia from 1922 to 1991 The Minus Cube («Минус-кубик» is a 3D mechanical variant of the N-puzzle which was manufactured in the Soviet Union. Three-dimensional space is a geometric model of the physical Universe in which we live

Bobby Fischer was an expert at solving the 15-Puzzle, provided that it was in a configuration that could be solved. Robert James "Bobby" Fischer ( March 9 1943 – January 17 2008) was an American -born Chess Grandmaster 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. Events 1519 - Hernán Cortés enters Tenochtitlán and Aztec ruler Moctezuma welcomes him with great a Celebration Year 1972 ( MCMLXXII) was a Leap year starting on Saturday (link will display full calendar of the Gregorian calendar. The Tonight Show Starring Johnny Carson was a late-night talk show hosted by Johnny Carson under the ''Tonight Show'' franchise from 1962

See also

• Rubik's Cube
• Minus Cube
• Sliding puzzle
• Combination puzzles
• Mechanical puzzles

References

External links

• Play 14-15 puzzle on line