It has been suggested that this article or section be merged into Sliding puzzle. (Discuss)

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. 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. Image File history File links Merge-arrow. ... Sliding puzzles or sliding block puzzles challenge a player to slide usually flat pieces along certain routes (usually on a board) to establish a certain end-configuration. ... Image File history File links 15-puzzle. ... Image File history File links 15-puzzle. ... Sliding puzzles or sliding block puzzles challenge a player to slide usually flat pieces along certain routes (usually on a board) to establish a certain end-configuration. ...

The n-puzzle is a classical problem for modelling algorithms 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, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*. In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ... Taxicab geometry, considered by Hermann Minkowski in the 19th century, is a form of geometry in which the usual metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the (absolute) differences of their coordinates. ... The A* search algorithm (pronounced A star) is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ...

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. 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 (see example below). In mathematics, any integer (whole number) is either even or odd. ... Invariant may have meanings invariant (computer science), such as a combination of variables not altered in a loop invariant (mathematics), something unaltered by a transformation invariant (music) invariant (physics) conserved by system symmetry This is a disambiguation page — a navigational aid which lists other pages that might otherwise share... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out...

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, is a game in which 15 of the 16 squares of a 4×4 frame are filled with numbered sliding pieces, leaving one space in which to slide one piece at a time. The object is to slide the 15 pieces into numerical order with the empty space after the 15 block. In the initial configuration, pieces 14 and 15 are exchanged. Image File history File links 15-puzzle-loyd. ... Image File history File links 15-puzzle-loyd. ...

Solution

This puzzle is not solvable. The proof involves noting that there are two distinct sets of positions which can be assembled from the pieces with different parity, and there is no way of moving between them using the allowed moves, as they preserve parity. The parity in this context (the invariant) is the parity (odd or even) of the number of pairs of pieces in reverse order plus the row number of the empty square. For the order of the 15 pieces consider line 2 after line 1, etc., like words on a page. In mathematics, any integer (whole number) is either even or odd. ...

Thus 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.

History

Sam Loyd claimed from 1891 until his death in 1911 that he invented the puzzle. 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. 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). 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. 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. Apparently the puzzle was not introduced to Japan 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 granted to Ernest U. Kinsey.^[1] Samuel Loyd (January 31, 1841 - April 10, 1911) was an American puzzle author and recreational mathematician. ... Canastota is a village located inside the Town of Lenox in Madison County, New York, USA. The population was 4,425 at the 2000 census. ... In recreational mathematics, a magic square of order n is an arrangement of n² 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. ... Nickname: Location of Syracuse within the state of New York Coordinates: , City Government  - Mayor Matthew Driscoll (D) Area  - City 66. ... Watch Hill is a small coastal fire district in the southwestern Washington County, Rhode Island. ... When used by itself in a sentence, the term Hartford can refer to one of several places in the United States. ... The American School for the Deaf (ASD) was the first institution for the education of the deaf in America. ... Nickname: City on the Hill, Beantown, The Hub (of the Universe)1, Athens of America, The Cradle of Revolution, Puritan City, Americas Walking City Location in Massachusetts, USA Counties Suffolk County Mayor Thomas M. Menino(D) Area    - City 232. ... Nickname: Location in Massachusetts Coordinates: Country United States State Massachusetts County Worcester County Settled 1673 Incorporated 1684 Government  - Type Council-manager also known as Plan E  - City Manager Michael V. OBrien  - Mayor Konstantina B. Lukes  - City Council Dennis L. Irish Michael C. Perotto Joseph M. Petty Gary Rosen Kathleen... Motto: (Out Of Many, One) (traditional) In God We Trust (1956 to date) Anthem: The Star-Spangled Banner Capital Washington D.C. Largest city New York City None at federal level (English de facto) Government Federal constitutional republic  - President George Walker Bush (R)  - Vice President Dick Cheney (R) Independence from... For other uses, see Europe (disambiguation). ... is the 52nd day of the year in the Gregorian calendar. ... Year 1880 (MDCCCLXXX) was a leap year starting on Thursday (link will display the full calendar) of the Gregorian calendar (or a leap year starting on Tuesday of the 12-day slower Julian calendar). ... is the 232nd day of the year (233rd in leap years) in the Gregorian calendar. ... 1878 (MDCCCLXXVIII) was a common year starting on Tuesday (see link for calendar). ...

For larger versions of the n-puzzle, finding a solution is easy, but the problem of finding the shortest solution is NP-hard.^[2] In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing...

In the USSR the Minus Cube was manufactured, a 3D variant of the 15-puzzle. The Minus Cube puzzle A small cube of the Minus Cube in the disassembled state The Minus Cube (Russian: ) is a Soviet mechanical puzzle, that is a 3D variant of the 15-puzzle. ... The space we live in is three-dimensional space. ...

Bobby Fischer is an expert at solving the 15-Puzzle, provided that it is in a configuration that can be solved, and he has been timed to be able to solve it every time within 25 seconds. Fischer demonstrated this on November 8, 1972 on The Tonight Show Starring Johnny Carson. Robert James Bobby Fischer (born March 9, 1943) is a United States-born chess Grandmaster who in 1972 became the only US-born chessplayer to become the official World Chess Champion. ... is the 312th day of the year (313th in leap years) in the Gregorian calendar. ... Year 1972 (MCMLXXII) was a leap year starting on Saturday (link will display full calendar) of the Gregorian calendar. ... This article does not cite any references or sources. ...

External links

• Web-based free Fifteen puzzle – Puzzles by Triado (JavaScript)

See also

• Rubik's Cube
• Minus Cube
• Sliding puzzle

Variations of Rubiks Cubes (from left to right: Rubiks Revenge, Rubiks Cube, Professors Cube, & Pocket Cube). ... The Minus Cube puzzle A small cube of the Minus Cube in the disassembled state The Minus Cube (Russian: ) is a Soviet mechanical puzzle, that is a 3D variant of the 15-puzzle. ... Sliding puzzles or sliding block puzzles challenge a player to slide usually flat pieces along certain routes (usually on a board) to establish a certain end-configuration. ...

References

1. ^ ^{a b} The 15 Puzzle, by Jerry Slocum & Dic Sonneveld. ISBN 1-890980-15-3
2. ^ Daniel Ratner, Manfred K. Warmuth. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable. National Conference on Artificial Intelligence, 1986.