The standard sliding piece puzzle is often called the 15-puzzle. It consists of a square tray containing 15 square tiles and one open space in a 4x4 arrangement. The tiles are usually numbered 1 to 15, or have some kind of picture on them. Any tile lying next to the space can slide into it, and so the tiles can be mixed up. The aim is to get them back in order; either so that the picture is restored, or so that the numbers are in numerical order from left to right, top to bottom, with the space at the bottom right.
This puzzle is often attributed to Sam Loyd. It turns out that this is completely false. He did not invent the puzzle, nor did he invent the version with 14 and 15 swapped, nor was he the first to offer a $1000 prize for anyone who could swap the 14 and 15. The 15 puzzle was a big craze in the early part of 1880, lasting only a few months. Some 10 years later Loyd started claiming to have invented it, and many believed him. Loyd was not only a master puzzle setter, but also a master self-publicist. These facts were recently uncovered due to some meticulous research by Jerry Slocum. Jerry has written it all up in an excellent book, released in 2006.
During the craze, there were even prizes offered for solving the puzzle starting from the position with just tiles 14 and 15 swapped. These prizes went as high as $1000, but of course it is impossible to win. Suppose the inside of the tray containing the tiles has a checkerboard pattern. Sliding a single tile will then always change the colour visible in the space. Any sequence of moves that brings the space back to where it started will therefore have an even number of moves. A single move can be considered to be a swap between the space and the tile, and an even number of moves is therefore an even permutation. A single swap of the tiles 14 and 15 is an odd permutation and hence not possible. One of Loyd's stories is that he was not granted a patent for this puzzle since he could not supply a working (solvable) model. The original inventor did apply for a patent, and was not granted it, but the reasons for refusal are not known.
It is not known exactly when the puzzle first appeared on the market. One well known early wooden version of the puzzle says on the box: "No. 2 Patent embossed PUZZLE OF FIFTEEN and Magic Sixteen. Manufactured by the Embossing Co. Patented Oct 24, 1865." I have searched for this patent and finally found it - US 50,608 by Henry May. Unfortunately it only refers to the method of embossing wood, and makes no mention of puzzles, so the puzzle is probably from a later date. There is a patent by Ernest U. Kinsey, US 207,124, published on August 20 1878 which shows a 6x6 version of the puzzle with the now standard groove arrangement that prevents the tiles from being lifted out.
A very neat variation of the puzzle has a single letter on each tile, which when solved says 'RATE YOUR MIND PAL'. The first two words have different colours from the last two words. Here the 14-15 swap is possible, i.e. you can start with 'RATE YOUR MIND PLA' and solve it. The reason is that there are two identical tiles, the R's in the first two words, which can be swapped too. Making two swaps is an even permutation and therefore possible. Some puzzles which have a picture on them are also designed so that they have two identical tiles.
The puzzle is usually a 4x4 square, with 15 square tiles. It could also be made with different dimensions, say a 5x5 square or 3x7 rectangle. This does not make the puzzle much more difficult.
One unusual variant was Genius by Milton Bradley. This is an eight tile 3×3 puzzle. The twist is that the tiles are identical, and that there is an LED light under each. The aim is to slide the tiles to make all their LEDs light up. Actually, a tile lights up only when it in its correct position, so it is not very difficult. It has patent US 4,323,243, April 6, 1982 by Steven P. Hanson, Howard J. Morrison, and Douglas P. Montague. Its electronics is extremely simple, just eight LEDs and eight membrane switches activated by the tiles.
The Metropolitan Museum of Art's Color Magic Puzzle is a beautiful version. It is large and heavy,
with felt underneath, intended as a display piece on a table.
The tiles are coloured transparent plastic, and the base behind it has coloured squares. The squares in the base come in three colours, red, blue, and yellow, alternating in that order all the way through, except for the sixteenth square which is grey. The tiles are also red, blue, and yellow, five of each.
At the start, every tile is on a square of the same colour, so that the puzzle shows diagonal lines of the primary colours red, blue, and yellow. The aim is to mix the tiles so that the diagonals now show the secondary colours orange, green and purple. This can be done in two ways (orange can be a yellow tile on a red square or a red tile on a yellow square, etc).
Another amusing variation is called Virus, and it has a big spider-like bug with each of its six legs stuck to a tile of a 4×4 grid. The legs restrict some of the movement of the tiles. It was patented by Dov Nesis, US 5,785,318, July 28 1998.
Phase 1: Solve the top row.
You will solve the row from left to right.
Phase 2: Solve the rest of the puzzle
If you wish to solve a puzzle so that the blank space ends up in a position other than the bottom right corner, then you can still use the same method. Whenever the next unsolved row should have the blank space in it, then turn the puzzle upside down so you can start solving the remaining area from the other end. Eventually the remaining unsolved area is still reduced to a 2x2 square, but this time that does not lie in the bottom right corner.
There are quicker ways to solve the last two tiles of a row. One good way is first to place the last tile in the position of the next-to-last one, and then place the next-to-last tile in position (which displaces the last tile to its proper place).
This puzzle has three sets of 5 identical tiles. It therefore has 16!/5!3 = 12,108,096 positions, which is small enough for God's algorithm to be calculated. The results are shown in the tables below.
|Multiple Tile Metric||Single Tile Metric|
The booklet that comes with this puzzle show a solution of 86 moves, where a move includes sliding two or three tiles at the same time. This is extremely inefficient. By hand it can easily be done in about 25 moves, and a computer search found an optimal 14 move solution. If moves only involve sliding one tile at a time, then 26 moves is optimal.
Using U, D, L and R for the directions Up, Down, Left,
and Right, the optimal solution (for both ways of counting moves) is:
D R D RR UU LLL DDD RRR UUU LL D R U LL
This sequence cycles the three types of tile, thus cycling between the starting position (red/yellow/blue diagonals) and the two solutions (orange/green/purple diagonals).
It is also possible to swap two types of tile, with the sequence:
D R DD R UUU LL DD RRR U LL U L
leading to one of three positions with diagonals of only two colours (red/green/green, blue/orange/orange, or yellow/purple/purple). Cycling between these three positions is once again done with the first move sequence.