How to Solve a Sliding Puzzle

The plan

Every sliding puzzle, whatever its size, can be solved with one method:

1. Solve the top row, then the next row, working down, until only two rows are left. Never touch a finished row again.
2. Solve the last two rows column by column, from the left, until only a 2×2 corner is left.
3. Turn the last three tiles round the corner until they drop into place.

Most of each row is easy: bring each tile to its square while the tiles already placed stay put. The hard part is always the end of a row, and the end of a column in the last two rows. Each needs one trick.

The trick for the last two tiles of a row

Suppose 1 and 2 are in place and you need 3 and 4 in the top row of a 15 puzzle. Placing 3 first is a dead end: 4 then has to come in from below the corner, and there is no way to slide it up without pushing 3 out again.

So put them in together. Move 4 into the square where 3 belongs, then bring 3 directly below it, and bring the gap round to the corner. Now two moves finish the row: 4 slides right into the corner, then 3 slides up.

Getting 4 and 3 into that position takes some moving around, and 4 may need to go round the outside more than once. That is fine: until the trick is done, only the finished rows above must stay put.

The last two rows: one column at a time

Once only two rows are left, there is no room to finish a row the same way, so turn the method sideways and finish the bottom two rows one column at a time from the left. On the 15 puzzle the first column is 9 over 13. The trick is the same, turned through a quarter turn: put 13 where 9 belongs, 9 just to its right, and the gap below 13. Then 13 slides down and 9 slides left.

Do the same for 10 and 14, and so on, until only a 2×2 corner is left.

The last 2×2 corner

With every other tile in place, the last three tiles and the gap share a 2×2 square, and the only thing they can do is turn round it. Keep moving them round in the same direction and within a few moves they line up. If you have followed the method, they always can: the puzzle was solvable to start with, so the last three tiles cannot be stuck.

Why some puzzles can't be solved

If you buy a puzzle, take the tiles out and put them back at random, there is a 50% chance it can never be solved. In 1879 W. W. Johnson and W. E. Story showed why: every move changes two things at once, the order of the tiles counted in pairs and the distance of the gap from its corner, so a combination of the two never changes. A puzzle that starts on the wrong side of it stays there.

You can check one with a count. List the tiles row by row and count the pairs that are in the wrong order (a bigger number before a smaller one). On a 3×3 board the puzzle can be solved when that count is even. On a 4×4 board, add the row the gap is in, counting from the bottom as 1: the puzzle can be solved when the total is odd. The 15 puzzle with only 14 and 15 swapped has one pair out of order and the gap on the bottom row, 1 + 1 = 2, so it is impossible.

Tips

• Move the gap, not the tile. To move a tile one square, the gap has to come round to the other side of it first. Plan where the gap goes.
• Work in the open. Use the unfinished part of the board as working space and leave finished rows alone.
• Don't chase the fewest moves at first. Learn the method, then look for shortcuts. On 3×3 the result after each solve tells you the shortest possible solution, which shows how much room there is.
• Use Hint to get unstuck. On 5×5 it follows exactly this method, so you can watch it place the end of a row.