0

## Solving the 15 Puzzle

Published on Sunday, October 03, 2010 in , , , ,

## Upper Rows

The 15 puzzle is a true classic, and fiendishly difficult to solve. By sliding the pieces, the challenge is to arrange them in such a way that the pieces are in numerical order, reading from left to right, and then top to bottom, as in the following image:

The challenge would be much easier (in fact, trivially easy), if you were working with only 3 pieces in a 2 by 2 grid. Think about it: There would be no challenge, as just consistently rotating the pieces clockwise or counterclockwise would eventually return you to the proper arrangement.

Ultimately, though, that is the ultimate goal of any 15 puzzle. Once you get all but the space and the last 3 pieces in place, you can simply keep moving them around in a clockwise direction (or counterclockwise), until the puzzle is solved.

If the square marked 1 is already in the upper left corner, click on Shuffle until it is no longer there.

The challenge, of course, is getting there. How do we do that?

We're going to start with a puzzle containing 3 rows and 3 columns, as you see below (yes, it's a real working 15 puzzle). Clicking any piece adjacent to the empty space will slide it into that space. Clicking the Shuffle button will rearrange the pieces.

Step 1: Slide the pieces around so as to get the 1 square in the upper left corner. Don't worry about the positions of any other pieces except the 1 square.

Step 2: Without ever moving the 1 square, slide the remaining pieces so as to move the 2 square to the upper middle square.

At this point, you'll be in one of two possible positions. Here's how to handle both of them.

Step 3a: If the 3 piece is already in place, you're set. If the upper right corner is the empty space, with the 3 below it, simply move the 3 into the empty space. In either of those cases, skip step 3b. Otherwise, you'll need to go directly to step 3b.

Step 3b: If the upper right corner is empty, slide the nearest piece up into it (obviously, if there's a piece other than the 3 in the upper right corner, just leave it there). Slide the pieces so as to move the 3 square directly below that piece (in other words, move the 3 piece so it's the rightmost square in the middle row). For the following sequence, you'll also need to make sure that the empty square is directly below the 3 (in the bottom right corner).

We're now going to use a sequence to temporarily disturb the 2, so that we can maneuver the 3 next to it. Down means slide a piece downward into the empty square. Similarly, up means slide a piece upward into the empty square, right means slide a piece to the right into the empty square, and left means slide a piece to the left into the empty square. Here's the sequence:

Down
Down
Right
Up
Left
Up
Right
Down
Down
Left
Up

Fortunately, you don't really need to remember this sequence. Once you see and understand what it does, and practice it enough, you'll be able to remember and execute it easily.

At this point, the top row should be in 1-2-3 order, and you're ready to learn how to handle the last 2 rows.

## Last 2 Rows

To make sure you've learned how to handle getting the first row done, and that you can get the last piece in its proper place without peeking at the sequence from the previous page, arrange the following puzzle so that the top row is in 1-2-3 order:

Once you can solve the top row, you've effectively reduced a 3 by 3 puzzle to a 2 by 3 puzzle. The final 2 rows will be solved at the same time, but this isn't as scary as it sounds.

Instead of going left to right in a row, as we did previously, we're going to work from the bottom up in columns for the final 2 rows. So, the next piece we'll place is the 7.

Step 4: Without moving pieces 1, 2, and 3 in any way, move the pieces so as to place the 7 piece in the bottom left corner.

We're going to place the 4 directly above the 7, using approaches very similar to steps 3a and 3b. In fact, they're exactly the same, except for being rotated 90 degrees counterclockwise!

Step 5a: If the 4 piece is already in place, you're set. If the leftmost square in the middle row is the empty space, with the 4 to its immediate right, simply move the 4 into the empty space. In either of those cases, skip step 5b. Otherwise, you'll need to go directly to step 5b.

Step 5b: If the leftmost square in the middle row is empty, slide the nearest piece into it (obviously, if there's a piece other than the 4 in the leftmost square in the middle row, just leave it there). Slide the pieces so as to move the 4 square directly to the right of that piece (in other words, move the 4 piece so it's in the center square).

For the following sequence, you'll also need to make sure that the empty square is directly to the right of the 4 (in the rightmost square of the middle row).

Just as we did with the 2 and the 3 in steps 3a and 3b, we're now going to put the 4 and the 7 together by using a sequence that temporarily disturbs the 7 before returning it to its original position.

Right
Right
Up
Left
Down
Left
Up
Right
Right
Down
Left

If done correctly, at this point the top row should read 1-2-3, and the leftmost column should now read 1-4-7.

Step 6: This is the last step! Since you've now reduced the 3 by 3 puzzle effectively to a 2 by 2 puzzle, the rest is easy.

You will now have 5, 6, and 8 remaining in the bottom right of the puzzle. Simply keep moving the remaining pieces in a clockwise (or counterclockwise, as long as you choose one direction and stick with it) direction until the puzzle is solved!

Believe it or not, you now have the skills to solve the full 15 puzzle! Click here to learn how to apply your skills to a more general solution.

## Solution

To tackle the standard 15 puzzle, all you really need to know is how to apply the skills you've learned with the 3 by 3 version.

First, work across the top row, getting the rightmost 2 pieces in the row together via the sequence from step 3b, if needed. Then, work through the 2nd row in exactly the same way. Finally, place the 13 square at the bottom left, and place the 9 directly above it, as taught in steps 4-6. Use the same process to place the 14 directly under the 10 (and to the right of the 13, of course), then get the final four pieces in place and you're done!

Try it out below to see just how similar the process truly is.

For any puzzle 3 by 3 or larger, with the empty space of the solved puzzle in the bottom right, it's easy to see how to tackle it now:

1) Arrange the top row, getting the 2 rightmost pieces in place with the sequence from step 3b, if needed.

2) Repeat this process until you only have the bottom 2 rows remaining.

3)For the last two rows, work in columns going from right to left, using the sequence from step 4b, as needed, until there's only a 2 by 2 group remaining in the bottom right.

4) Keep moving the remaining pieces in a constant direction, clockwise or counterclockwise, until the puzzle is solved.

Once you've got this process down, you'll discover that you can work in other directions, such as right to left, or from the bottom up, as long as you follow the same general procedures. Once you can do that, you can work puzzles with the empty square anywhere, since all you need to do is work towards the empty spot's location as being among the final 2 by 2 group.

Once you're able to handle any size, there are other variations to trip you up. Start learning about other variations here.

## Pictures

One of the simplest ways to alter the challenge of the 15 puzzle, besides changing the size, is to eliminate the numbers, and replace them with parts of a picture. The challenge, of course, is to arrange the pieces so they form a coherent picture.

As long as you have an idea of what the picture is going to be, and where each piece should go, you can solve this type of puzzle with the same techniques you've already learned. Here's a 15 puzzle with a picture of a chipmunk to try out.

Since it helps to know the end picture, you can click the Original button to toggle between the puzzle and the original picture.

## Solvable?

In the late 19th century, puzzle maker Sam Loyd released a version of the puzzle with 15 and 14 pieces switched. The challenge was to start at that point and restore the puzzle to its traditional 1 through 15 arrangement. It was determined that this version was unsolvable in the traditional manner. In the video below, James Grime explains more about why this is, and discusses some alternative ways to handle this.

Click here to see a video of my responses to the challenges on this video.

Inspired by the 15-14 version of the puzzle, a version came out in 1959 that read RATE YOUR MIND PLA when packaged new. The challenge was to change the puzzle to read RATE YOUR MIND PAL.

At first glance, this seemed to be just as unsolvable as the 15-14 puzzle. However, there is an important difference that allows this version to be solved. Try it below, and see if you can work out what it is. There's a hint below the puzzle, if you need it.

Hint: Look for 2 identical pieces and swap those.

## Magic Square

The 15 puzzle came from an earlier puzzle that used blocks numbered from 1-16, and the challenge was to arrange them so that every row, column, and diagonal totaled 34, known as a magic square. Indeed, many early versions were packaged with both the 15 puzzle and magic square challenges.

With the 15 puzzle itself, counting the blank space as 0, it's still possible to arrange a magic square that totals 30. Since you can solve the 15 puzzle, solving it as a magic square is now just a matter of memorizing an arrangement.

## Prerequisites:

Major/Peg System

## Method

The arrangement you're going to memorize is this (there are other possible arrangements):
```14   3   8   5
9   4  15   2
7  10   1  12
13   6  11
```
Using the Major System, you need to memorize this pattern by turning the numbers into words and make a short story out of them.

Here's the story, with the important words bolded:

I had a dream that I could fly. During this, I came across a pretty lion.

Now, his dad had a tan. He got onto a jet, which was filled with lots of tomatoes and one single sock.

The words dream and fly help you remember the first row is 14-3-8-5. The phrase pretty lion covers the 2nd row, to remind you that it goes 9-4-15-2.

The remaining words are all mnemonics that read from the bottom up and right to left (effectively upside down and backwards), since that is how they're going to be placed.

Dad (11) and tan (12) help you to remember that the 11 is going into the bottom right corner, with the 12 directly above it. jet (6-1) should remind you that the 6 goes to left of the 11, with the 1 immediately above the 6.

At this point, you're down to a 2 by 2 square in the bottom left corner. The word tomatoes breaks down into 13 and then 10, so that you know to place the 13 on the bottom and the 10 directly above it. Sock is 0-7, so you know to place the empty square (effectively the 0 piece) in the bottom left corner, with the 7 above it and you're done!

Once you've got the pattern memorized, practice solving it here (to help minimize peeking at the information you're supposed to memorize). Below is a video that shows the many ways in which this pattern totals 30.