15 puzzle

The aim is to arrange the numbers from 1 to 15 in ascending order

The 15 puzzle , also Fifteen game , 14-15 puzzle , sliding puzzle , sliding puzzle , Schiebefax or Without-industry-no-price game called, is a game of patience . It was invented in the United States between 1870 and 1880 by postal worker Noyes Palmer Chapman. The game consists of 15 tiles, numbered 1 to 15, which are placed on the 16 fields of a four-by-four square . One field (the “hole”) remains free. An adjacent tile (vertically or horizontally) can be pushed into the free field. The task now is to arrange the numbers from 1 to 15 in ascending order by moving the tiles.

Depending on the starting position, there are different variants of the game, especially the 14-15 puzzle, in which only the numbers 14 and 15 are swapped in the starting position, making the puzzle unsolvable. Today's editions of the game are usually delivered in the desired order; The player first moves (“shuffles”) the tiles and then tries to bring the puzzle back to its original position. With this variant of the game, it is guaranteed that the task can be solved.

history

Illustration from the Cyclopedia of 5000 Puzzles (1914) by Samuel Loyd

The game was invented by postal worker Noyes Palmer Chapman, who showed his friends a similar puzzle in 1874. This was about bringing 16 numbered blocks into the shape of a magic square . The first copies of the 15 puzzles came to Syracuse in the state of New York to Frank Chapman, son of Noyes. From there the game spread to Watch Hill and eventually to Hartford , Connecticut , where students from the American School for the Hearing Impaired made the puzzle in large quantities and sold it as Christmas presents in Boston , Massachusetts in December 1879 . Matthias Rice, the owner of a shop for unusual wooden objects, discovered one of these puzzles and immediately began to manufacture it himself and bring it to the market as a "Gem Puzzle".

The 15 game pieces or tiles lay loosely in a small box and the instructions were: "Place the blocks in the box irregularly, then move until in regular order" (in German, for example: "Put the pieces in any order in the box, then move them until they are in order ”).

Towards the end of January 1880, the dentist Charles Pevey offered prize money for solving the 15 puzzle. The first trend for the game was seen in the US in February, Canada in March, and Europe in April 1880. The trend was already in decline in July of the same year. It wasn't until nine years later that the game was introduced in Japan .

Chapman wanted to apply for a patent for the 15 puzzle on February 21, 1880 as "Block Solitaire Puzzle", but was rejected by the patent office because his game was not sufficiently different from the patent granted on August 20, 1878 for that of Ernest U. Kinsey developed game "Puzzle Blocks" seemed to distinguish.

The puzzle specialist Samuel Loyd claimed from 1891 until his death in 1911 that he was the inventor of this puzzle, but could never prove it. According to recent research, he has even been exposed as a liar. During the First World War , the 15-piece puzzle was produced as a “patience game for the trenches”.

Tasks

Original puzzle

In the “Gem Puzzle”, which Matthias Rice produced and sold in 1879, the player took out the stones at the beginning and placed them in the box as desired. Then the task was to arrange the numbers in ascending order by moving the stones. The following mathematical relationships result:

• There are 16! = 20922789888000 ≈ 2.1 ⋅ 10 ¹³ possible start arrangements ( permutations of the numbers 1 to 16) in which the empty 16th field is not necessarily at the bottom right.
• By moving the stones, exactly half of all starting arrangements can be brought into an ascending order (sequence) with the empty field at the bottom right.
• By moving the stones, the other half of all starting arrangements can be brought into a sequence with the empty space in the top left.
• With a starting arrangement with which a sequence with the empty field at the top left can be reached, a sequence with the empty field at the bottom right can only be brought so close that only two of the fifteen blocks are in the wrong positions.

The following facts can be determined for other target arrangements:

If a certain arrangement can be achieved, then is

1. the horizontally or vertically mirrored arrangement cannot be achieved.
2. the arrangement rotated 90 ° to the right or left cannot be achieved.
3. the arrangement rotated by 180 ° can also be achieved.
4. the diagonally mirrored arrangement can be achieved.
5. an arrangement in which only two adjacent stones are exchanged can not be achieved.

• 

  Half (H1) of all starting positions can be brought into this arrangement.

• 

  The other half (H2) of the starting positions can be brought into this arrangement.

• 

  Every second starting position (H1) can only be brought into this arrangement.

• 

  The other half (H2) can only be brought into this arrangement.

15-14 puzzle

In the starting position of the 15-14 puzzle, the stones are sorted in ascending order with the exception of stones 14 and 15. The last field at the bottom right remains free. In this starting position, the task of getting the numbers into the correct order by moving the stones, whereby the last field remains free again, cannot be solved. The task becomes solvable if you leave the first instead of the last field free (see above)

14-15 puzzle

Another possibility is to achieve certain other arrangements from the ordered sequence with the gap at the bottom right, e.g. B:

• 

  Starting position

• 

  Accessible:
  vertical arrangement

• 

  Accessible:
  a spiral

• 

  Accessible:
  This zigzag arrangement.

• 

  Accessible:
  This jump path

• 

  Not achievable:
  a 90 ° rotation.

Modern 15 puzzle

Many of the games that are available today are already correctly sorted in the delivery condition and their stones are so interlocked that you can move them but not remove them. The aim of the game is therefore to restore a mixed puzzle to its original state.

Many forms of this game can be found in stores. They are available, for example, as key rings made of plastic or wood.

There are also games that no longer have the goal of sorting numbers, but instead consist of an image that can only be fully seen when all the squares are sorted in a correct order.

There are versions with letters or groups of letters instead of numbers. As a solution, either the alphabetical order should be achieved or a specific text should appear. The latter often have a pair (or even several) of the same tiles (i.e. with the same letters). If a situation arises in which only the last two tiles are swapped, you have to swap a pair of the same letters in order to solve the problem. If, for example, in the game shown in the figure “text version” there is “Prsei” instead of “Price” in the bottom line, you either have to swap the two “e”, the two “n” or (!) The two “ei”.

When displaying using Roman numerals, the degree of difficulty increases due to the usually poorer exercise in the sequence of numbers.

• 

  Version with letters

• 

  Version with text

• 

  Version with picture

• 

  Version with Roman numerals

• 

  15 puzzle as a keyring

Further tasks

Magic squares

A magic square as the solution to the 14-15 puzzle

Another task for the 15-number puzzle is to convert the usual starting order (with the empty field at the bottom right) into a magic square , with the empty field representing the number 0. The magic sum (i.e. the row, column and diagonal sum) is then 30. If one takes into account rotations or reflections of the square, there are 880 8 = 7040 magic squares on a 4x4 field. Exactly half of these, i.e. 3520, can be reached from the usual start arrangement. For each of these magic squares, Kociemba determined the minimum number of moves required based on the starting arrangement. You need at least 35 moves to get a magic square, and there is only one magic square that can be reached in 35 moves. ${\displaystyle \cdot }$

Other sizes

There are also versions in other sizes, E.g. the 8-puzzle in a three-by-three-square and the 31-puzzle in a four-by-eight rectangle.

Math background

Permutations and invariants

Each position of the game is either solvable or unsolvable , that is, it can be transferred to the end position or not. The so-called parity of each position is considered as proof . It is always retained on a move. The parity results from the number of unordered pairs of numbers. Here is the number of pairs of numbers that are in the wrong order and the number of the row in which the empty field is located. The total is either even or odd . This parity is retained for all permitted moves, i.e. an even playing position can never be converted into an odd one and vice versa. Since the original task is odd , it can never lead to the even end state. ${\displaystyle N_{1}}$ ${\displaystyle N_{2}}$ ${\displaystyle N=N_{1}+N_{2}}$

Another idea of ​​proof uses the sign of the position viewed as a permutation , i.e. as an exchange, which changes the sign with every move .

example

In order to check whether a constellation of stones can be transferred into another by means of permitted moves, a distinction must be made between frame sizes with an even number of columns (like the one here) and those with an odd number of columns. The basic requirement is that the squares are numbered as shown or, in the case of puzzles whose solution is to create a picture, are numbered for verification. In the case of puzzles that allow several solutions , such as symbols that are to be arranged according to certain rules, it must be proven that none of the solution variants can be reached by permitted moves.

To determine the disorder parameter N _1, one counts all pairs of numbers in which a smaller number follows a larger one, regardless of how many stones are in between; the absolute size of the respective numbers is irrelevant, numbers can appear in several pairs. The stones are compared as if they were all listed in a horizontal row. For example, with a constellation of 1, 4, 2, 6, 7, 8, 3, 5 there are the following pairs (2 | 4), (3 | 8), (3 | 7), (3 | 6), ( 3 | 4), (5 | 8), (5 | 7), (5 | 6). You iterate from left to right and compare a number with all the numbers on the left. As soon as a number on the left is larger, a messy pair has been found.

If a stone is shifted in the horizontal direction, neither the disorder parameter N ₁ nor the row parameter N _{2 change} , since this movement can be understood as an exchange of the moving stone by the free field, which is not taken into account in the calculation of the disorder parameter.

If a stone is shifted in the vertical direction, the row parameter N _{2 changes} by +/- 1. The vertical shift always affects exactly three pairs of numbers, because there can only be changes in the order between the shifted stone and the three enclosed fields. The disorder parameter has increased or decreased by 1 for each enclosed stone, since the stone to be moved has changed its place, all pairs that were formed with the moving stone have now changed their order. Messy couples are now neat and vice versa.

• 

  In this constellation, N ₁ = 3; the messy couples are . ${\displaystyle (11|12),(11|13),(11|14)}$

• 

  The 7 changes vertically to the empty field, whereby N ₁ is increased by three and N ₂ is decreased by one.

N was straight from the start (N = 4). Since the row parameter N ₂ experiences an odd change with every vertical step (+1, −1) and the order parameter N ₁ then also only experiences an odd change (+3, +1, −1, −3), N can only experience an even change (+4, +2, 0, −2, −4). It is therefore not possible to move from the original task (15 exchanged with 14) to a sorted order, since the original order (N = 5) has an odd parity and cannot be converted into an even parity by moving pieces .

General case

In an a × a puzzle with an odd number of columns a, the number of stones included is a² − 1, that is, an even number; the disorder parameter does not change at all with a horizontal move and with a vertical move by an even number. The parity of the disorder parameter N _{1 is} retained with every move.

In an a × a puzzle with an even number of columns a (like this one) the number of stones included is a² − 1, i.e. an odd number, the disorder parameter N ₁ changes by an odd number with a vertical move. The row parameter N ₂ increases or decreases by 1 with each vertical move; N ₁ + N ₂ is therefore the sum of two odd numbers and therefore even. The parity of (N ₁ + N ₂ ) is retained with every move.

Since the parity of N _{1 is} always retained with an odd number of columns or (N ₁ + N ₂ ) with an even number of columns, you can check by simply counting whether a random constellation K _{1 can be converted} into another specific constellation K ₂ using permitted moves. This is not possible with the classic task of the 15-puzzle, because with an even number of columns a = 4 the sum (N ₁ + N ₂ ) = (1 + 4) = 5 in (N ₁ + N ₂ ) = (0 + 4 ) = 4 would have to be transferred.

Furthermore, these considerations show that at most half of all conceivable constellations can be achieved from the basic constellation, because only arrangements can be converted from even to even or odd to odd parities. As Story 1879 showed, exactly this half of the basic constellation can always be reached, but this cannot be proven by the proof presented here, since parity is only a necessary, but not a sufficient condition for general solvability. Archer gave an elegant modern proof that all constellations with even parity can actually be converted into one another and that all constellations with odd parity can also be converted into one another. The algorithms for the 15 puzzle discussed in the following chapter also prove this fact.

Algorithms and Complexity

Sliding puzzles such as the 8-puzzle or the 15-puzzle have long been used as test problems for search algorithms in artificial intelligence . As Brüngger et al. 1999 using an Intel Paragon parallel computer with 64 nodes showed that solving the 15 puzzle requires a maximum of 80 steps for all start-up arrangements. In 2005, Korf and Schultze determined the minimum number of steps required for the solution for each of the 16! / 2 = 10,461,394,944,000 solvable starting arrangements by means of a breadth first search and using a parallel computer. In particular, they determined for the first time all 17 starting arrangements that can be solved in 80 steps (and no fewer). A randomly selected, releasable initial configuration can be solved in an average of 52.6 moves. To avoid memory errors - after all, 8 10 ¹⁴ bits ≈ 100 terabytes had to be written and read - Korf and Schultze used a RAID system. ${\displaystyle \cdot }$

Ratner and Warmuth proved in 1990 that the generalized problem of finding the minimum number of moves for a solvable starting arrangement in an nxn game is NP-hard .

literature

• LE Hordes: Sliding Piece Puzzles . Oxford University Press, 1986, ISBN 0-19-853204-0 .
• Jerry Slocum, Dic Sonneveld: The 15 Puzzle . Slocum Puzzle Foundation, 2006, ISBN 1-890980-15-3 .

Similar games

• Rush hour
• Quo Vadis (Klotski)

See also

• Jeu de taquin

Web links

Commons : 15-Puzzle  - Collection of pictures, videos and audio files

• The 14-15-Puzzle  - English language page that illustrates the proof of the unsolvability of the original 15-puzzle with interactive examples.
• 15-Puzzle Optimal Solver with Download (by Herbert Kociemba)

Individual evidence

1. ↑ ^{a b} Jerry Slocum: Sam Loyd's Most Successful Hoax . (PDF; 672 kB). Presentation at Seventh Gathering for Gardner, March 2006, The Convention of the Association of Game and Puzzle Collectors. Published in: E. Pegg, AH Schoen, T. Rodgers: Homage to a Pied Puzzler. AK Peters, Wellesley / Massachusetts 2009, pp. 3–21. (here: p. 4)
2. ↑ ^{a b c} Jerry Slocum, Dic Sonneveld: The 15 Puzzle . Slocum Puzzle Foundation, 2006, ISBN 1-890980-15-3 .
3. ↑ Sam Loyd's Fifteen English-language page with Java applet and proof of the unsolvable problem. Retrieved November 16, 2007.
4. ↑ Woolsey Johnson: Notes on the "15" Puzzle. I . In: Amer. J. Math. 2, 1879, pp. 397 to 399.
5. ^ ^{A b} William E. Story: Notes on the "15" Puzzle. II . In: Amer. J. Math. 2, 1879, pp. 399 to 404.
6. ↑ Sam Loyd, Martin Gardner: Mathematical puzzles of Sam Loyd . Dover Pubs., New York 1959, pp. 19 and 20 . , Google Books
7. ↑ Herbert Kociemba: 15-Puzzle Optimal Solver 2013.
8. ^ Aaron F. Archer: A Modern Treatment of the 15 Puzzle . In: The American Mathematical Monthly. 106, no. 9, 1999, pp. 793 to 799.
9. ^ Richard E. Korf, Larry A. Taylor: Finding Optimal Solutions to the Twenty-Four Puzzle . (PDF; 1.1 MB). In: Proceedings of the 11th National Conference on Artificial Intelligence. 1993, pp. 756 to 761.
10. ^ ^{A b} Adrian Brüngger, Ambros Marzetta, Komei Fukuda, Jurg Nievergelt: The parallel search bench ZRAM and its applications. (PDF; 192 kB). In: Annals of Operations Research. 90, 1999, pp. 45 to 63.
11. ^ Richard E. Korf, Peter Schultze: Large-Scale Parallel Breadth-First Search . (PDF; 104 kB). In: AAAI Conference On Artificial Intelligence. Proceedings of the 20th national conference on Artificial Intelligence. 3, 2005, pp. 1380 to 1385, here pp. 1384 to 1385 (Fifteen Puzzle), Table 2 (States as a Function of Depth for Fifteen Puzzle).
12. ↑ D. Ratner, M. Warmuth: Finding a shortest solution for the (NXN) extension of the 15-puzzle is intractable. In: Journal of Symbolic Computation. 10, 1990, pp. 111-137.

This version was added to the list of articles worth reading on October 12, 2008 .