Jaap's Puzzle Page

14-15 puzzle / Boss puzzle

Fifteen puzzle

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

RATE
YOUR
MIND
PAL

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.

MB Genius Virus

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.

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.

If your browser supports JavaScript, then you can play the Fifteen Puzzle, or any other size from 2×2 to 10×10 by clicking the link below:

JavaScript Fifteen Puzzle

The number of positions:

The standard version has 15 pieces and a gap, giving a maximum of 16! positions. This limit is not reached because the permutation must be even or odd depending on the position of the gap. There are therefore 16!/2 = 10,461,394,944,000 positions, or 15!/2 = 653,837,184,000 positions with the space in one particular spot.

Links to other useful pages:

Dozens of pages have similar versions of this puzzle, so only a small selection of more unusual links is given here.
Cut-the-knot has a Java version of the game here as well as some history of it.
Harry Broeders' page has a Java and a downloadable Windows version which have a built-in solver, and can have different sizes or designs. Also a page with some history.

Solution:

This solution will work on all sizes.

Phase 1: Solve the top row.
You will solve the row from left to right.

  1. Find the next tile you want to place in position in the top row.
  2. If it is not the last tile of the row, it is fairly easy to place correctly, simply keep the following points in mind:
    1. Never disturb any previously placed pieces.
    2. To move the tile in a certain direction, move the other tiles around until the space is next to your tile on the side you want to move it to. Then you can move the tile.
  3. If the last tile is not already in position, bring it to the position directly below its correct spot, with the space directly below that. Then move tiles in the following directions: Down, down, right, up, left, up, right, down, down, left, up. This should place the piece in position. Note it does temporarily disturb the previously placed tile.

Phase 2: Solve the rest of the puzzle

  1. Use the technique in phase 1 to solve each row in turn, until there are only two rows left.
  2. Rotate the puzzle a quarter turn to the right. The left column of the two rows becomes the top row now.
  3. Use the technique in phase 1 to solve each row in turn, until there are only two rows left. This means there is only a 2x2 square left to solve.
  4. Move the pieces in the remaining 2x2 square around until one piece is positioned correctly, and the space is in the correct spot. The other two tiles should automatically be correctly positioned as well.
  5. If there are two tiles that need to be swapped, then this cannot be done unless two other tiles are swapped as well. If there are two identical tiles somewhere in the puzzle, then you will have to swap them and solve the rest again.

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