15-Puzzle

The 15 - puzzle, even 14 -15 puzzle, sliding puzzle, or no -puzzle -industry -no- price game called, is a game of patience. It was invented in 1870-1880 in the United States by the postal workers Noyes Palmer Chapman. The game consists of 15 tiles, numbered from 1 to 15, which are mounted on the 16 fields in a four- by-four square. A field ( the "hole" ) thus remains free. A (vertical or horizontal) neighboring tile can be pushed into the open field, respectively. The task now is to arrange in ascending order by moving the tiles the numbers from 1 to 15.

Depending on the starting position there are different variations of the game, especially the 14-15 puzzle in the in the initial position, only the numbers 14 and 15 are reversed which the puzzle is unsolvable. Today's editions of the game are usually delivered in the desired configuration; The player moves ( " mixed " ) the tiles first and then tried to put the puzzle back into the orderly starting position. In this variant of the game is thus guaranteed that the task is solvable.

• 3.1 Permutations and invariants
• 3.2 Example
• 3.3 General case

History

The game was invented by Noyes Palmer Chapman postal workers, who showed his friends in 1874, a similar puzzle. In this it was to bring 16 numbered blocks in the form of a magic square. The first copies of the 15 - puzzle came to Syracuse in upstate New York to Frank Chapman, the son of Noyes. From there, the game spread further to Watch Hill and finally to Hartford in Connecticut, where students of the American School for the hearing impaired made ​​the puzzle in large editions and sold in December 1879 as Christmas gifts in Boston, Massachusetts. Matthias Rice, the owner of a shop for fancy wooden articles, discovered one of these puzzles and began to produce them immediately by yourself and bring a " Gem Puzzle" on the market.

The 15 tiles or tiles were doing loose in a small box and the game instructions read: " Place the blocks in the box irregularly, then move until in regular order " ( to German as: "Set the pieces in any arrangement in the box, then move them until they are in order ").

Towards the end of January 1880 put the dentist Charles Pevey of a prize for solving the 15 - puzzle. The first trend for the game was seen in the U.S. in February, in Canada in March and in Europe in April 1880. The trend was in July of that year, but again in the fall. Only nine years later, the game was introduced to Japan.

Chapman wanted the 15 - puzzle as "Block Solitaire Puzzle" apply for a patent on 21 February 1880 met with the patent office but rejected because his game is not enough of the other members on August 20, 1878 patent for the Ernest U. Kinsey developed game seemed to distinguish " puzzle blocks".

The mystery specialist Samuel Loyd claimed from 1891 until his death in 1911, that he was the inventor of this puzzle, but this could never prove. According to recent studies it has even been exposed as a liar.

Tasks

Original 15 - Puzzle

The " Gem Puzzle", the Matthias Rice 1879 produced and sold, the player took to start out the blocks and put them anywhere in the box. For this puzzle, there are 16! = 20922789888000 ≈ 2.1 ⋅ 1013 possible starting configurations ( permutations of the numbers 1 to 16), where the empty 16 -th field is not necessarily located at the bottom right. By shifting the tiles can be placed in ascending order with the empty box at the bottom right exactly half of all possible starting configurations. The other starting configurations can only get so close that only two of the fifteen blocks are in the wrong positions of the target array.

14-15 puzzle

In the initial position of the 14-15 puzzle the stones and tiles with the exception of the stones 14 and 15 are already sorted in ascending order. The last field at the bottom right remains free. In this initial position is the task of bringing the numbers by moving the stones in the right order, with the last field is free again, not removable. The task is to solve when the leaves free the first instead of the last field or the numbers in columns from right to left directs.

This line by line arrangement can not be reached

A line by line arrangement with the free box at the top is reached

A spal -th -wei se to - properly v. r. nl, ( 90 ° rotation ) is also within

Modern 15 - Puzzle

Many of the games that are available today are already sorted properly on delivery. The objective of the game is therefore, a mixed puzzle to put back in the original condition, that is, the task is similar to that of the Rubik's Cube.

In the market there are many forms of this game. They are manufactured, for example as a key fob made ​​of plastic or wood.

There are also games that no longer have the goal to sort numbers, but consist of a picture that is only complete to see if all the squares are sorted in the correct order.

There are versions with letters instead of numbers. Here is the solution to stand for a certain text. This sliding puzzle game often have a pair ( or even more ) of the same tiles ( ie with the same letter ). Is it relevant to a situation in which the last two tiles are only reversed, so you have to exchange a pair of identical letters to solve the task. If, for example, in which the figure "text version " illustrated game in the bottom line " Prsei " instead of " price ", so you have either the two "e ", the two "n" or (!) The two " ei" exchange ( compare also " God's number, algorithms and complexity ").

15 - puzzle as a keychain

Further objects

Another task for the 15 - puzzle with numbers is the usual starting arrangement ( with the empty box at the bottom right) to convert it into a magic square, where the empty box for the number 0. The magic sum (ie, the row, column and diagonal sum ) is then 30 Considering rotations or reflections of the square, there are 880 8 = 7040 magic squares on a 4x4 field. Of these, exactly half, ie 3520 to reach from the usual start- arrangement (see section " God's number, algorithms and complexity "). Kociemba specific for each of these magic squares, the minimum number of moves that is starting from the start prescription required. Requires at least 35 features, in order to obtain a magic square, and there is only a single magic square can be achieved in the coatings 35.

There are also versions available in other sizes, such as the 8-puzzle in a three - by-three square and the 31- puzzle in a four - by-eight square.

Mathematical Background

Permutations and invariants

Each position of the game is either detachably or permanently, which means that they can be converted into the end position or not. To prove the so-called parity is considered any position. You will always get in a train. The parity is derived from the number of unordered pairs of numbers. This is the number of pairs of numbers that are in the wrong order and the number of the row in which there is the empty field. The sum is either even or odd. In all these coatings permitted parity is maintained, that is, a straight play position can never be transferred to an odd, and vice versa. Since the original task is odd, it can never lead in the final straight.

Another idea of ​​the proof uses the sign of the permutation considered to be, so as exchange position, which changes sign with each train.

Example

To check whether a constellation of stones by means of allowed trains can be transferred to another, is to distinguish between frame sizes with an even (like the present ) and those with an odd number of columns. The basic requirement is that the squares in the manner shown are numbered or puzzle whose solution is the creation of an image are numbered for detection. In puzzles that allow multiple solutions, such symbols should be arranged according to certain rules, is to prove that none of the possible solutions can be achieved by allowing trains.

To determine the disorder parameter N1, one counts all pairs of numbers in which a smaller number followed by a larger, equal to how many stones are there between; the absolute magnitude of the respective numbers is irrelevant numbers may exist in plurality of pairs. The stones are compared as were all listed in a horizontal row. In such a configuration, for example, 1, 4, 2, 6, 7, 8, 3, 5, so there is the following pairs of ( 2 | 4), ( 3 | 8), ( 3 | 7), ( 3 | 6), ( 3 | 4 ), ( 5 | 8), ( 5 | 7), ( 5 | 6). It iterates from left to right and compares a number with all left-wing figures. Once a left- number is then greater, a messy pair was found.

If a stone moves in the horizontal direction, change neither the disorder parameter N1 nor the number of parameters N2, since one can interpret this movement as an exchange of the moved stone by the free field that is not included in the calculation of the disorder parameter.

If a stone moves in the vertical direction, the number of parameters N2 varies by / - 1 The vertical displacement always affects exactly three pairs of numbers, because there can only be changes in the order between the displaced stone and the three enclosed fields. Here, the disorder parameter increases or decreases because of the stone to be moved has changed its place by 1 for each enclosed stone, now have all the pairs which were formed with the shifting Stone, changed their order. Messy couples are now ordinary and vice versa.

The 7 changes vertically on the empty field, thereby N1 and N2 increased by three to one.

N from the beginning was just (N = 4). Since the parameter set N2 undergoes an odd change in each vertical step ( 1, -1) and the order parameter N1 then likewise undergoes only an odd change ( 3, 1, -1, -3 ), N, only one each straight change experienced ( 4, 2, 0, -2, -4). It is therefore not possible from the original task (15 of 14 exchanged ) to get into a sorted order because the original order (N = 5) has an odd parity and can not be transferred to the moving of stones in an even parity.

General case

In an a × b great puzzle with an odd number of columns, a is the number of trapped stones a-1, ie an even number; the disorder parameter does not change with a horizontal and a vertical train train to an even number. The parity of the disorder parameter N1 is maintained with each train.

In an a × b great puzzle with an even number of columns a ( like the present ) the number of trapped stones is a-1, A in this case is an odd number, the disorder parameter N1 changes with a vertical train to an odd number. The row parameter N2 increases or decreases with each vertical train by 1; N1 N2 is the sum of two odd numbers and so straight. The parity of ( N1 N2) remains with each train.

Since the parity of N1 at odd or (N1 N2) at the even number of columns is always maintained, can be checked by simply counting whether a random constellation K1 can be transferred to another particular constellation K2 allowed by traits. In the classic tasks of 15 puzzles that is not possible, since with the even number of columns, a = 4, the sum ( N1 N2 ) = (1 4) = 5 in the (N1 N2 ) = ( 0 4) = 4 transferred would have to be.

Furthermore, these considerations show that more than half of all possible constellations can be obtained from the basic constellation out because only arrays of straight in straight or odd in odd parities can be converted. What story was in 1879, is always accessible from the basic constellation exactly this half, but can not be detected by the presented evidence, because parity is only a necessary, but not a sufficient condition for the solvability of general. An elegant modern proof that all configurations of even parity actually into each other can be converted and all the constellations with odd parity can be converted into each other, Archer was 1999. Also addressed in the following chapter algorithms for the 15 - puzzle prove this fact.

Algorithms and Complexity

Puzzle like the 8-puzzle or 15 - puzzle are used for a long time as a test problem for search algorithms in Artificial Intelligence. How Brüngger et al. 1999 showed using an Intel Paragon parallel computer with 64 nodes, requires the solution of the 15 - puzzle for all starting configurations up to 80 steps, see also God's number. Korf and Schultze given 2005 by a breadth-first search and by using a parallel computer for each of the 16! / 2 = 10.461.394.944.000 detachable starting arrangements, the minimum number of steps needed to solve. In particular, they first given every 17 start- assemblies which can be dissolved in 80 steps (not less). A randomly selected, detachable output configuration can be solved in an average of 52.6 trains. To avoid memory errors - after all, were 8 bit 1014 to write ≈ 100 terabytes and read - Korf and Schultze used a RAID system.

Ratner and Warmuth proved in 1990 that the generalized problem to find the minimum number of moves to a detachable starting arrangement in an nxn game is NP -complete.