# 14-15 puzzle / Boss 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, 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.

 R A T E Y O U R M I N D P A L

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.

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:

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

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

## Color Magic Puzzle:

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.

Click to show combined table.
Multiple Tile Metric Single Tile Metric
DepthPositions
0 1
1 6
2 18
3 54
4 162
5 486
6 1,449
7 4,239
8 11,724
9 31,021
10 78,743
11 185,981
12 403,236
DepthPositions
13 782,376
141,319,134
151,871,872
162,170,065
172,022,014
181,522,906
19 938,255
20 481,594
21 200,356
22 64,814
23 15,044
24 2,377
25 169
Total12,108,096
DepthPositions
01
12
24
310
424
554
6107
7212
8444
9932
101,870
113,624
126,769
1312,428
1422,375
1539,018
DepthPositions
1666,131
17108,126
18170,518
19257,648
20374,076
21516,550
22682,219
23851,926
241,009,346
251,123,642
261,177,597
271,156,022
281,067,763
29930,032
30758,785
31585,812
DepthPositions
32424,233
33293,522
34192,030
35120,796
3672,370
3740,854
3821,761
3910,740
404,858
411,874
42709
43222
4457
452
461
Total12,108,096

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