Pick up an old plastic puzzle with numbered squares and one empty slot, and you are holding the answer to what is the 15 puzzle. It is fifteen numbered tiles in a four by four frame with one square left open, and the goal is to slide them back into order. It is the oldest well known sliding puzzle and the ancestor of games such as 2048, including the version played on a cube, Evolved 2048. Solving it is a skill anyone can learn: one check to see whether a start can be solved at all, then a fixed order of work, one row at a time.
What is the 15 puzzle, exactly
The 15 puzzle has 15 square tiles numbered 1 to 15, set in a frame four squares high and four squares wide. One position is empty. Any tile in the same row or column as the empty square can slide into it, and that is the only move there is. The goal is to put the tiles in numerical order, left to right and top to bottom, with the empty square last.
It goes by many names: the Gem Puzzle, the Boss Puzzle, the Game of Fifteen and the Mystic Square. A smaller cousin, the 8 puzzle, uses eight tiles in a three by three frame and follows the same rule.
The puzzle belongs to the wider family of sliding puzzles, where lifting a piece off the board is not allowed. That single restriction is the whole difficulty. You cannot pick up the 7 and drop it where it belongs. You have to walk it there through the gap, and every step it takes pushes some other tile somewhere else.
Where the puzzle came from
The puzzle was invented by Noyes Chapman, a postmaster in Canastota, New York, and copies spread through New England in 1879. By 1880 it was a craze across the United States. Years later the puzzle writer Sam Loyd claimed to have invented it, a claim he made from 1891 until his death, though he had no part in its creation.
Loyd did add one famous twist. He offered a $1,000 prize to anyone who could take a frame with only the 14 and 15 swapped and put it back in order. Nobody collected, and for a good reason: that position cannot be solved. The reason why is the first thing to learn before trying to solve any start.
Check first: can this 15 puzzle be solved
In 1879 Johnson and Story used a parity argument to show that exactly half of all possible arrangements of the tiles can never reach the solved order, no matter how many moves are made. Every legal slide keeps a hidden property of the board the same, so a start on the wrong side of that property stays on the wrong side forever.
For the common case, with the empty square in the bottom right corner, the check is simple. Read the tiles in order, left to right and top to bottom, skipping the gap. Count every pair where a larger number comes before a smaller one. Each such pair is called an inversion. If the count is even, the start can be solved. If it is odd, it cannot.
When the gap is somewhere else, slide it to the bottom right corner first, then count. Moving the gap along a row never changes the reading order, and the rule above holds once the gap sits in the corner.
A worked example: Loyd's 14 and 15
Take Loyd's prize position. The first three rows read 1 to 12 in order. The last row reads 13, 15, 14, then the gap.
- Write the tiles out in reading order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
- Look for pairs where a larger number comes first. Every number from 1 to 13 sits before all the larger numbers, so none of them adds anything.
- The 15 comes before the 14. That is one inversion.
- The total is 1, an odd number. The gap is already in the bottom right corner, so the rule applies directly.
- Odd means unsolvable. No sequence of slides, however long, will ever swap those two tiles back.
Now change the start a little. Suppose the last row reads 14, 15, 13, gap. The pairs are 14 before 13 and 15 before 13, which makes two inversions. Two is even, so this one can be solved. The difference between those two starts is invisible at a glance, which is why the count is worth the half minute it takes.
How to solve the 15 puzzle row by row
Once you know a start can be solved, a reliable method is to finish the board in pieces you never disturb again. The idea is to shrink the puzzle: each finished row turns a four by four problem into a smaller one.
- The top row. Bring 1 to the top left, then 2 next to it, then 3. The 4 is the awkward one: walk it to the square below its home first, park the 3 in the corner where the 4 belongs, then rotate both into place with the gap. After this, never touch the top row again.
- The second row. Do the same for 5, 6, 7 and 8, using the same trick for the last two tiles. You now have a four wide, two high puzzle left.
- The last two rows, by column. Place 9 and 13 together on the left: bring 13 into the 9 square, 9 beside it, then drop both down into place. Repeat for 10 and 14. What remains is a two by two corner with 11, 12, 15 and the gap, which you turn round until they sit in order.
If that last two by two corner never lines up however long you turn it, the start was on the unsolvable side, and the inversion count would have said so before you began.
How many moves a solution takes
The row method gets you to the end, but it is not the shortest route. Computer searches have shown that every solvable start of the 15 puzzle can be finished in at most 80 single-tile moves, and only 17 starts need all 80. The 8 puzzle never needs more than 31.
Finding some solution is easy for any size of frame. Finding the shortest one is a different matter: for larger versions it is NP-hard, which means no known method does it quickly as the frame grows. Programs that search for short solutions often guide themselves by counting misplaced tiles, or by adding up how many rows and columns each tile is away from its home.
From the 15 puzzle to 2048
2048 kept the slide and dropped almost everything else. In the 15 puzzle one tile moves into one gap and the set of tiles never changes. In 2048 a single swipe moves every tile at once, equal tiles merge into their sum, and a new 2 or 4 arrives after each move. Order is no longer the goal. Space is, since the board fills as you play. The family of sliding tile puzzles shows each step in that change.
On a cube of six faces, 54 squares in all, the slide works on the front face and rows can also be twisted a quarter turn, carrying tiles from one face to the next. A twist there plays the role the gap plays in the 15 puzzle: it moves a tile somewhere it could not reach by sliding alone.
Frequently asked questions
Is every 15 puzzle solvable?
No. Exactly half of all arrangements can be solved and half cannot. A start with the 14 and 15 swapped and everything else in order is the classic unsolvable case.
What is the fastest way to solve the 15 puzzle?
For a person, solving the top row, then the second row, then the last two rows column by column is the most dependable route. The shortest possible solution for any solvable start is at most 80 single-tile moves.
What is the difference between the 8 puzzle and the 15 puzzle?
The 8 puzzle has eight tiles in a three by three frame, and the 15 puzzle has fifteen in a four by four frame. Both leave one square empty and use the same sliding rule.
Who invented the 15 puzzle?
Noyes Chapman, a postmaster in Canastota, New York, invented it, and it spread through New England in 1879. The history of sliding puzzles records that Sam Loyd later claimed it falsely, with no part in its creation.
Why the 15 puzzle still rewards patience
The 15 puzzle has outlasted more than a century of newer games because it asks for two different kinds of thinking. The parity check is pure reasoning: thirty seconds of counting tells you whether hours of sliding could ever pay off. The row by row method is pure patience: finish a part, protect it, and let the problem shrink. Both lessons carry into every sliding game that came after it, where the space you keep open decides which moves you still have.
Evolved 2048
The 2048 puzzle on a Rubik's cube, and past 2048. Visit evolved2048.vlvd.net
