Saturday, January 15, 2011

Check out this puzzle

An easy technique for solving sliding-tile puzzles.
I've hated these puzzles my entire life. It seemed like no matter what I did there always ended up being one tile out of position and to get it where it had to go I had to scramble all the pieces that had taken so much effort to get into place. It got so that I hated even looking at these things.
Then one day I decided that I didn't want to die without having mastered this demon. Internet searches turned up many sites that presented elaborate mathematical theories on their solutions and several that offered programs that solved them, but none explained how to do it manually. So, I purchased a 15-puzzle, sat down with it, took out a pencil and graph paper and dug in for the battle.
Two days later I not only solved it but developed a simple technique anyone can learn to solve their 15-puzzles. This page shows this technique. If you've been haunted by these monsters of the puzzle realm, then this page will help you conquer them.
The goal is to get all the numbers to line up in order from left to right and top to bottom like this:
Let's begin by taking a second look at the scrambled puzzle shown at the top of this page:
Start by moving tiles around any way you want to get the empty space between the 1 and the upper left corner.
Slide the 1 up into this empty space to move it closer to the upper left corner.
Repeat as often as needed until the 1 is in the upper left corner. Don't worry about any other tiles at this point.
Repeat this process with the 2, 3 and 4 to get them in order along the top row.
Once in a while things work out so you can slide the 4 into the upper right corner. If it does, great... you got lucky. More often than not you'll end up with a nightmare like the following:
The trick to figuring out how to get the 13 out of the corner and the 4 up into it is the key to solving 15 puzzles. Fortunately, it's an easy trick to learn.
The 1, 2 and 3 tiles can be moved down and around the corner as shown by the arrows in the picture below so that their order isn't disturbed. Later, they can be moved back into place.
Slide the 9, 7 and 6 one space to the right and the 8 down. This opens up a space below the 1. Move the 1 down and the 2 and 3 to the left. You get the following:
Note that even though the 1, 2 and 3 are bent around a corner, they are still in order. Now, without touching them, rotate the 13, 4 and 10 tiles counter clockwise until the 4 is in the upper right corner and there is an empty space on its left. Now move the 3, 2 and 1 tiles back into place like this:
...and your top row is complete!
This trick of moving tiles while keeping them in order to create an opening where you need it is the key to solving 15-puzzles.
Once the first row is done we forget about it and use the simple tile-moving technique used to get the 1, 2 and 3 tiles into their places to get the 5, 6 and 7 tiles in order along the second row.
Just as we had with the 4, the place where the 8 is supposed to go is filled and there is no empty space close to it. The solution is to repeat the in-order temporary shift used to complete the top row. Start by moving the tiles in the bottom row to the right, then the 5 down and the 6 and 7 to the left to get this:
Take a look at the 5, 6 and 7. Just like with the top row they are still in order, they're just temporarily parked around the corner to get them out of the way.
As with the 4, rotate the 11, 8 and 14 tiles until the 8 is where you want it and then slide the 7, 6 and 5 tiles back into place.
Two rows done!
As it happened, the 9 ended up sitting where it needed to be. If it hadn't been there, I would have simply slid the bottom 8 tiles around until it was.
Now we need to move the 10 next to the 9. It looks tough because since we don't want to touch the top two rows we don't have much maneuvering room. Don't worry, simply move the 15 to the left and slide the 12, 11, 14, 10 and 13 tiles around in a sort of rotational pattern until the 10 is next to the 9.
To get the 11 next to the 10 just rotate the 13, 11 and 12 tiles clockwise.
Now things get a little more interesting.
At first this would appear to be an impossible situation because tiles are at opposite ends of where they are supposed to be and because there is so little maneuvering room. The solution is to employ the same trick we used to get the 4 and 8 into their spots: create an empty space near the target tile by temporarily moving other tiles "in order" out of the way. Some times at this late stage of solving a 15 puzzle the exact same technique can be used to finish it off. In this particular case things are a little more complicated so we have to modify the process a little.
First, start as before by moving the 12, 14 and 15 tiles to the right. Then slide the 9 down and the 10 and 11 to the left.
Now we are free to rotate the positions of the 13, 12 and 14 tiles so the 12 is in position next to the 11.
Then slide the 12, 11, 10 and 9 tiles back into place and the third row is done.
Now things really look hopeless. Fear not. We're almost done. This is where we modify the basic move-tiles-in-order-temporarily-out-of-the-way technique: we cut it in half.
Rather than moving the first three tiles in the third row down and over to get them out of the way, we only do it with the 9 and 10 to get the following after moving the 15 up into the 10's spot:
Next we do the same thing with the right half of the third row but this time we go down and across to the right. First the 13 and 14 are slid to the left.
Then the 12, 11 and 15 are moved over and down around the corner. Note that the 11 and 12 are still in their proper order.
Do you see the solution?
Move the 10 and 9 back into their proper places, then the 13 and 14 to the left.
Next slide the 15 down and the 11 left and 12 up to get them back into their positions.
And the puzzle is solved!
Once again, the trick to solving any of these puzzles is simply to realize that tiles can be moved out of the way while their order is retained to create elbow room where you need it to move other tiles around. Then the first tiles can be moved back and they will still be in order.
Although the photos on this page only show how to use this technique to solve a single puzzle, I've used the same trick to solve dozens of different ones and it always works. The only tricky part is that sometimes you have to split the in-order temporary shifting in two steps at the very end.
There's one final trick that may save you a little time on some puzzles. Before plowing the 1 through the center of the puzzle to get it in the upper left hand corner, take a look at how the tiles lay. In the case below the 15 and 1 are in opposite corners. Rotating all the outside tiles around does two things at once: it gets the 1 into its corner and moves the 15 down close to where it needs to be.
In this particular case it also gives you the entire top row free of charge. Careful and creative examination of an initial puzzle may suggest similar time-saving moves.

No comments: