15 puzzle

Last updated

To solve the puzzle, the numbers must be rearranged into numerical order from left to right, top to bottom. 15-puzzle magical.svg
To solve the puzzle, the numbers must be rearranged into numerical order from left to right, top to bottom.

The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and more) is a sliding puzzle. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order (from left to right, top to bottom).

Contents

Named after the number of tiles in the frame, the 15 puzzle may also be called a "16 puzzle", alluding to its total tile capacity. Similar names are used for different sized variants of the 15 puzzle, such as the 8 puzzle, which has 8 tiles in a 3×3 frame.

The n puzzle is a classical problem for modeling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the taxicab distances between each block and its position in the goal configuration. [1] Note that both are admissible . That is, they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*. [1]

Mathematics

Solvability

A solved 15 Puzzle 15-Puzzle solved.png
A solved 15 Puzzle

Johnson & Story (1879) 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 binary function of the tile configuration that is invariant under any valid move and then using this to partition the space of all possible labelled states into two mutually inaccessible equivalence classes of the same size. This means that half of all positions are unsolvable, although it says nothing about the remaining half.

The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner. 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 in the lower right corner, then the puzzle is solvable only if the permutation of the remaining pieces is even.

Johnson & Story (1879) also showed that on boards of size m × n, where m and n are both larger or equal to 2, all even permutations are solvable. It can be proven by induction on m and n, starting with m = n = 2. This means that there are exactly two equivalency classes of mutually accessible arrangements, and that the parity described is the only non-trivial invariant, although equivalent descriptions exist.

Archer (1999) gave another proof, based on defining equivalence classes via a Hamiltonian path.

Wilson (1974) studied the generalization of the 15 puzzle to arbitrary finite graphs, the original problem being the case of a 4×4 grid graph. The problem has some degenerate cases where the answer is either trivial or a simple combination of the answers to the same problem on some subgraphs. Namely, for paths and polygons, the puzzle has no freedom; if the graph is disconnected, only the connected component of the vertex with the "empty space" is relevant; and if there is an articulation vertex, the problem reduces to the same puzzle on each of the biconnected components of that vertex. Excluding these cases, Wilson showed that other than 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 attained, which gives an instance of the exotic embedding of S5 into S6.

For larger versions of the n puzzle, finding a solution is easy. But, the problem of finding the shortest solution is NP-hard. It is also NP-hard to approximate the fewest slides within an additive constant, but there is a polynomial-time constant-factor approximation. [2] [3] For the 15 puzzle, lengths of optimal solutions range from 0 to 80 single-tile moves (there are 17 configurations requiring 80 moves) [4] [5] or 43 multi-tile moves; [6] the 8 Puzzle always can be solved in no more than 31 single-tile moves or 24 multi-tile moves (integer sequence A087725). The multi-tile metric counts subsequent moves of the empty tile in the same direction as one. [6]

The number of possible positions of the 24 puzzle is 25!/27.76×1024, which is too many to calculate God's number feasibly using brute-force methods. In 2011, lower bounds of 152 single-tile moves or 41 multi-tile moves had been established, as well as upper bounds of 208 single-tile moves or 109 multi-tile moves. [7] [8] [9] [10] In 2016, the upper bound was improved to 205 single-tile moves. [11]

Group theory

The transformations of the 15 puzzle form a groupoid (not a group, as not all moves can be composed); [12] [13] [14] this groupoid acts on configurations.

Because the combinations of the 15 puzzle can be generated by 3-cycles, it can be proved that the 15 puzzle can be represented by the alternating group . [15] In fact, any sliding puzzle with square tiles of equal size can be represented by .

History

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. 15-puzzle-loyd.svg
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.
U.S. political cartoon about finding a Republican presidential candidate in 1880 Great presidential puzzle2.jpg
U.S. political cartoon about finding a Republican presidential candidate in 1880

The puzzle was "invented" by Noyes Palmer Chapman, [16] 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, garnered some attention by offering a cash reward for a solution to the 15 Puzzle. [16]

The game became a craze in the U.S. in 1880. [17]

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. [16]

Sam Loyd

Sam Loyd's 1914 illustration of the unsolvable variation. Sam Loyd - The 14-15 Puzzle in Puzzleland.jpg
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. [16] [18]

Some later interest was fueled by Loyd's offer of a $1,000 prize (equivalent to $33,911in 2023) 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. [1] This is impossible, as had been shown over a decade earlier by Johnson & Story (1879), because it requires a transformation from an even to an odd permutation.

Varieties of the 15 puzzle

The Minus Cube, manufactured in the USSR, is a 3D puzzle with similar operations to the 15 Puzzle.

Versions of the 15 puzzle include a different number of tiles, such as the 8-puzzle or 24-puzzle.

Notable examples

Chess world champion Bobby Fischer was an expert at solving the 15 puzzle. [19] 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 . [20] [21]

See also

Notes

  1. 1 2 3 Korf, R. E. (2000), "Recent Progress in the Design and Analysis of Admissible Heuristic Functions" (PDF), in Choueiry, B. Y.; Walsh, T. (eds.), Abstraction, Reformulation, and Approximation (PDF), SARA 2000. Lecture Notes in Computer Science, vol. 1864, Springer, Berlin, Heidelberg, pp. 45–55, doi:10.1007/3-540-44914-0_3, ISBN   978-3-540-67839-7, archived from the original (PDF) on 2010-08-16, retrieved 2010-04-26
  2. Ratner, Daniel; Warmuth, Manfred (1986). "Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable" (PDF). National Conference on Artificial Intelligence. Archived (PDF) from the original on 2012-03-09.
  3. Ratner, Daniel; Warmuth, Manfred (1990). "The (n2−1)-puzzle and related relocation problems". Journal of Symbolic Computation. 10 (2): 111–137. doi: 10.1016/S0747-7171(08)80001-6 .
  4. Richard E. Korf, Linear-time disk-based implicit graph search, Journal of the ACM Volume 55 Issue 6 (December 2008), Article 26, pp. 29-30. "For the 4 × 4 Fifteen Puzzle, there are 17 different states at a depth of 80 moves from an initial state with the blank in the corner, while for the 2 × 8 Fifteen Puzzle there is a unique state at the maximum state of 140 moves from the initial state."
  5. A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research90 (1999), pp. 45–63.
    :"Gasser found 9 positions, requiring 80 moves...We have now proved that the hardest 15-puzzle positions require, in fact, 80 moves. We have also discovered two previously unknown positions, requiring exactly 80 moves to be solved."
  6. 1 2 "The Fifteen Puzzle can be solved in 43 "moves"". Domain of the Cube Forum
  7. "24 puzzle new lower bound: 152". Domain of the Cube Forum
  8. "m × n puzzle (current state of the art)". Sliding Tile Puzzle Corner.
  9. "208s for 5x5". Domain of the Cube Forum.
  10. "5x5 can be solved in 109 MTM". Domain of the Cube Forum.
  11. "5x5 sliding puzzle can be solved in 205 moves". Domain of the Cube Forum.
  12. Jim Belk (2008) Puzzles, Groups, and Groupoids, The Everything Seminar
  13. The 15-puzzle groupoid (1), Never Ending Books
  14. The 15-puzzle groupoid (2), Never Ending Books
  15. Beeler, Robert. "The Fifteen Puzzle: A Motivating Example for the Alternating Group" (PDF). faculty.etsu.edu/. East Tennessee State University. Archived from the original (PDF) on 7 January 2021. Retrieved 26 December 2020.
  16. 1 2 3 4 The 15 Puzzle, by Jerry Slocum & Dic Sonneveld, 2006. ISBN   1-890980-15-3
  17. Slocum & Singmaster (2009 , p. 15)
  18. Barry R. Clarke, Puzzles for Pleasure, pp.10-12, Cambridge University Press, 1994 ISBN   0-521-46634-2.
  19. Clifford A. Pickover, The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, p. 262, Sterling Publishing, 2009 ISBN   1402757964.
  20. "Bobby Fischer solves a 15 puzzle in 17 seconds on Carson Tonight Show - 11/08/1972", The Tonight Show, 8 November 1972, Johnny Carson Productions, retrieved 1 August 2021.
  21. Adam Spencer, Adam Spencer's Big Book of Numbers: Everything you wanted to know about the numbers 1 to 100, p. 58, Brio Books, 2014 ISBN   192113433X.

Related Research Articles

<span class="mw-page-title-main">Cube</span> Solid object with six equal square faces

In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets, or sides, with three meeting at each vertex. Viewed from a corner, it is a hexagon and its net is usually depicted as a cross.

<span class="mw-page-title-main">Three utilities problem</span> Mathematical puzzle of avoiding crossings

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

A puzzle is a game, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together in a logical way, in order to achieve the correct solution of the puzzle. There are different genres of puzzles, such as crossword puzzles, word-search puzzles, number puzzles, relational puzzles, and logic puzzles. The academic study of puzzles is called enigmatology.

<span class="mw-page-title-main">Snub cube</span> Archimedean solid with 38 faces

In geometry, the snub cube, or snub cuboctahedron, is an Archimedean solid with 38 faces: 6 squares and 32 equilateral triangles. It has 60 edges and 24 vertices.

<span class="mw-page-title-main">Rubik's Revenge</span> 4×4×4 Rubiks cube variation

The Rubik's Revenge is a 4×4×4 version of the Rubik's Cube. It was released in 1981. Invented by Péter Sebestény, the cube was nearly called the Sebestény Cube until a somewhat last-minute decision changed the puzzle's name to attract fans of the original Rubik's Cube. Unlike the original puzzle, it has no fixed faces: the center faces are free to move to different positions.

<span class="mw-page-title-main">Rubik's Magic</span> Mechanical puzzle created by Erno Rubik

Rubik's Magic, like the Rubik's Cube, is a mechanical puzzle invented by Ernő Rubik and first manufactured by Matchbox in the mid-1980s.

<span class="mw-page-title-main">Professor's Cube</span> 5x5x5 version of the Rubiks Cube

The Professor's Cube is a 5×5×5 version of the original Rubik's Cube. It has qualities in common with both the 3×3×3 Rubik's Cube and the 4×4×4 Rubik's Revenge, and solution strategies for both can be applied.

<span class="mw-page-title-main">Square-1 (puzzle)</span> Shape-shifting puzzle similar to Rubiks Cube

The Square-1 is a variant of the Rubik's Cube. Its distinguishing feature among the numerous Rubik's Cube variants is that it can change shape as it is twisted, due to the way it is cut, thus adding an extra level of challenge and difficulty. The Super Square One and Square Two puzzles have also been introduced. The Super Square One has two additional layers that can be scrambled and solved independently of the rest of the puzzle, and the Square Two has extra cuts made to the top and bottom layer, making the edge and corner wedges the same size.

<span class="mw-page-title-main">Megaminx</span> Puzzle

The Megaminx or Mégaminx is a dodecahedron-shaped puzzle similar to the Rubik's Cube. It has a total of 50 movable pieces to rearrange, compared to the 20 movable pieces of the Rubik's Cube.

<span class="mw-page-title-main">Sliding puzzle</span> Puzzle game involving sliding pieces to achieve certain configurations

A sliding puzzle, sliding block puzzle, or sliding tile puzzle is a combination puzzle that challenges a player to slide pieces along certain routes to establish a certain end-configuration. The pieces to be moved may consist of simple shapes, or they may be imprinted with colours, patterns, sections of a larger picture, numbers, or letters.

<span class="mw-page-title-main">Mathematics of Sudoku</span> Mathematical investigation of Sudoku

Mathematics can be used to study Sudoku puzzles to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible moves. The allusion to the deity is based on the notion that an omniscient being would know an optimal step from any given configuration.

<span class="mw-page-title-main">V-Cube 6</span> 6×6×6 Rubiks Cube

The V-Cube 6 is a 6×6×6 version of the original Rubik's Cube. The first mass-produced 6×6×6 was invented by Panagiotis Verdes and is produced by the Greek company Verdes Innovations SA. Other such puzzles have since been introduced by a number of Chinese companies, most of which have mechanisms which improve on the original. Unlike the original puzzle, it has no fixed facets: the center facets are free to move to different positions.

<span class="mw-page-title-main">V-Cube 7</span> Larger variant of the Rubiks cube

The V-Cube 7 is a combination puzzle in the form of a 7×7×7 cube. The first mass-produced 7×7×7 was invented by Panagiotis Verdes and is produced by the Greek company Verdes Innovations SA. Other such puzzles have since been introduced by a number of Chinese companies, some of which have mechanisms which improve on the original. Like the 5×5×5, the V-Cube 7 has both fixed and movable center facets.

<span class="mw-page-title-main">Void Cube</span> 3x3x3 without centers

The Void Cube is a 2-D mechanical puzzle similar to a Rubik's Cube, with the notable difference being that the center pieces are missing, which causes the puzzle to resemble a level 1 Menger sponge. The core used on the Rubik's Cube is also absent, creating holes straight through the cube on all three axes. Due to the restricted volume of the puzzle it employs an entirely different structural mechanism from a regular Rubik's Cube, though the possible moves are the same. The Void Cube was invented by Katsuhiko Okamoto. Gentosha Education, in Japan, holds the license to manufacture official Void Cubes. These official designs are also sold under the Rubik's brand, owned by Spin Master Ltd., and workalikes are available from a variety of manufacturers. Speed-solving the Void Cube is common in exhibition but is not an official World Cube Association competition event.

The pebble motion problems, or pebble motion on graphs, are a set of related problems in graph theory dealing with the movement of multiple objects ("pebbles") from vertex to vertex in a graph with a constraint on the number of pebbles that can occupy a vertex at any time. Pebble motion problems occur in domains such as multi-robot motion planning and network routing. The best-known example of a pebble motion problem is the famous 15 puzzle where a disordered group of fifteen tiles must be rearranged within a 4x4 grid by sliding one tile at a time.

The original Rubik's cube was a mechanical 3×3×3 cube puzzle invented in 1974 by the Hungarian sculptor and professor of architecture Ernő Rubik. Extensions of the Rubik's cube have been around for a long time and come in both hardware and software forms. The major extension have been the availability of cubes of larger size and the availability of the more complex cubes with marked centres. The properties of Rubik’s family cubes of any size together with some special attention to software cubes is the main focus of this article. Many properties are mathematical in nature and are functions of the cube size variable.

<span class="mw-page-title-main">V-Cube 8</span> 8×8×8 version of Rubiks Cube

The V-Cube 8 is an 8×8×8 version of the Rubik's Cube. Unlike the original puzzle, it has no fixed facets: the center facets are free to move to different positions. The design was covered by Panagiotis Verdes' patent from 2007 but Verdes Innovations SA did not produce it for sale until 2014. Other manufacturers released their own versions of the puzzle much earlier.

In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

References