One method solves every 15 puzzle: the top row, the second row, the left column, then the last six squares, with a single trick for the last two tiles of each line. On a random solvable box it takes 96 moves on average, against about 53 for the shortest solution (a published figure), and the computer on this page finds the shortest solution every time. Played one tile at a time, the method wins 46% of games on Normal here, 10% on Hard and under 1% on Expert; planning a whole row at once raises that to 88%, 54% and 13%.
The idea is to fix the tiles in an order in which nothing already placed ever has to be disturbed for long. Each step leaves a smaller box, and the last box is small enough to solve by walking the empty square in circles.
| a | b | c | d |
|---|---|---|---|
| 1 | 1 | 2 | 2 |
| 3 | 3 | 3 | 3 |
| 4 | 5 | 5 | 5 |
| 4 | 5 | 5 | 5 |
Which step fixes which square. The top two rows are never touched again after step 3, and the left column never after step 4.
The method cannot get stuck. We checked every placement of the tiles each step works with, given the steps before it: every one of them can be finished without moving a tile that is already fixed. The worst cases are 21 moves for tile 1, 32 for the pair 3 and 4, 29 for 7 and 8, 24 for 9 and 13, and 21 for the last six squares.
The last tile of a row cannot simply be walked in: once 1, 2 and 3 are home, the corner can only be entered from below, and anything that goes round the corner has to push 3 out of the way. So 3 and 4 go in together. Park 3 in the corner, where 4 belongs, put 4 directly under it, and bring the empty square to the place of 3:
| a | b | c | d |
|---|---|---|---|
| 1 | 2 | □ | 3 |
| · | · | · | 4 |
| · | · | · | · |
| · | · | · | · |
□ is the empty square, a dot is any tile. From here two moves finish the row: 3 slides left, 4 slides up.
The mirror set-up works just as well: 4 on the square of 3, 3 directly under it, the corner empty — then 4 slides right and 3 slides up. Use whichever is closer.
The costly mistake is to put 3 home first and hope that 4 will follow. If 4 then ends up under 3 with the corner empty, the row looks one step from done and is in fact fifteen moves away:
| a | b | c | d |
|---|---|---|---|
| 1 | 2 | 3 | □ |
| · | · | 4 | · |
| · | · | · | · |
| · | · | · | · |
The shortest way to finish this row without touching 1 and 2 takes 15 moves. With 4 and 3 side by side in the wrong order (1, 2, 4, 3) and the empty square under 3 it is 17.
This pair is the most expensive part of the whole solve. On random boxes the top row costs 38.5 moves on average — 10.4 for tile 1, 9.4 for tile 2 and 18.7 for 3 and 4 — and the second row 31.5, of which 7 and 8 take 15.8. The two end-of-row pairs together are over a third of all the moves, so this is where care pays most.
With two rows and the left column fixed, five tiles and the empty square are left in a box two squares high and three wide. There are 720 ways to fill it, and exactly half of them, 360, can be reached by sliding; those are the only ones the method can leave you with. The farthest of them is 21 moves from solved and the average is 12.6 — we solved all 360.
The tool for this box is the cycle. Walk the empty square once round any block of four squares — four moves — and the three tiles in that block each move one place round it. Do it three times and everything is back where it was. The whole endgame is a matter of choosing which block of four to turn, and which way.
If you prefer to keep following rules, fix one more column — 10 and 14 as a pair, exactly like 9 and 13 — and three tiles remain in the last four squares. Bring the empty square to its corner and look: either 11, 12 and 15 are home, or they are exactly four moves away, one lap in one direction. There is no third case; of the 24 ways to fill those four squares only 12 can occur.
Solving the six squares as one box rather than as a column and a corner saves almost nothing: 12.7 moves against 13.0 on average. The moves are lost earlier, in the rows.
The computer here does not use a method. It searches for the shortest solution and always finds it, and your limit is that length times the margin of the level. So the question is how many times longer than the shortest solution the method is:
| Normal | Hard | Expert | Random box | |
|---|---|---|---|---|
| Shortest solution, typical | 22 | 36 | 46 | about 53* |
| Your limit, typical | 44 | 54 | 58 | – |
| The method, average | 47.6 | 70.7 | 88.4 | 95.8 |
| The method, times the shortest | 2.2 | 2.0 | 1.9 | about 1.8 |
| Allowed, times the shortest | 2 | 1.5 | 1.25 | – |
| Games the method wins | 46% | 10% | 0.9% | – |
“Typical” is the median. 5,000 deals on Normal, 2,000 on Hard, 1,050 on Expert, 10,000 random solvable boxes. The method was played by a program that takes the shortest route for each step, so these are its best figures; a person who walks tiles less neatly needs more. * The average shortest solution of a random box, about 53 moves, is a published result (Korf, 1985, and later larger samples), not something we computed.
On a random box the method needs between 79 and 112 moves in eight cases out of ten, and 139 in the worst of 10,000. On Normal it is right on the edge: the limit is twice the shortest solution, the method averages 2.2 times, and it stays inside the limit a little less than half the time.
Here is a real Normal deal that shows where the moves go. The shortest solution is 22 moves, so the limit is 44.
| a | b | c | d |
|---|---|---|---|
| 1 | 2 | 3 | 4 |
| 9 | 5 | 12 | 11 |
| 13 | 6 | 15 | 8 |
| 10 | □ | 14 | 7 |
The top row is already home. The method then spends 4 moves on tile 5, 7 on tile 6, 13 on the pair 7 and 8, 14 on 9 and 13, and 10 on the last six squares: 48 moves, four over the limit. The computer's 22 moves, by the tile it slides: 10, 13, 9, 5, 6, 10, 14, 15, 8, 11, 12, 8, 11, 7, 15, 11, 7, 12, 8, 7, 11, 15.
The method loses moves because every tile travels alone: the empty square goes to a tile, escorts it home, and walks back for the next one. The more tiles you plan as one group, the less of that walking there is. We let the program find the shortest way to bring a whole group home together and counted the result:
| Plan this many tiles at once | Normal | Hard | Expert |
|---|---|---|---|
| One tile at a time (the method as described) | 47.6 moves, wins 46% | 70.7, wins 10% | 88.4, wins 0.9% |
| Two at a time: 1 and 2, then 3 and 4, 5 and 6, 7 and 8 | 43.2, wins 55% | 65.5, wins 17% | 82.9, wins 1.4% |
| A whole row at a time | 32.4, wins 88% | 52.8, wins 54% | 67.0, wins 13% |
| Whole rows, then the bottom two rows as one box | 31.4, wins 92% | 50.5, wins 65% | 63.9, wins 20% |
The first two lines are from all 5,000, 2,000 and 1,050 deals; the whole-row lines from 1,000, 600 and 300 of them. A group is brought home by the shortest route that leaves finished rows alone, which is the ceiling of what planning that group can give.
Planning a row as a whole means looking at all four of its tiles before moving any, and collecting them on the way: a tile that is passed anyway is pushed towards its square, and 3 and 4 are steered into the set-up from the start instead of being fetched afterwards. Nobody finds the perfect route for four tiles at a glance, but the table shows what is at stake: the same order of work, and a quarter to a third fewer moves.
The order of work matters too, and unpredictably. The method can be run sideways — left column first, then the second column, then the top of what is left. For the deal shown above that takes 22 moves, the shortest possible, where rows first took 48. Over 5,000 Normal deals the better of the two orders averaged 41 moves and would have won 62% of games instead of 46%. But the obvious clues do not tell you which order it is: choosing by where more tiles are already home, or by which tiles are closer to home, picked the shorter order 43 to 54% of the time, no better than a coin.
What does not pay is greed. A player who looks four moves ahead, plays the sequence that brings the tiles closest to home overall, and falls back on the method when nothing improves, wins 49% on Normal, where the method alone wins 46%, and 7% on Hard, where the method wins 10%. Tiles that are near their squares but in the wrong order are worse off than they look.
Sixteen squares can be filled in 16! = 20,922,789,888,000 ways. Exactly half of them, 10,461,394,944,000, can be reached from the solved box by sliding; the other half cannot be solved by anyone, the computer included. This is general theory, proved in 1879, and the reason is short.
Every move swaps one tile with the empty square. Colour the squares like a chessboard: each move also changes the colour under the empty square, so bringing it back to its corner always takes an even number of moves. An even number of swaps can never add up to exchanging just two tiles. That is why the box below, the one a thousand-dollar prize was once offered for, has no solution:
| a | b | c | d |
|---|---|---|---|
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 15 | 14 | □ |
Tiles 14 and 15 exchanged. Given this box, the page's solver looks at its full allowance of three million positions and returns without an answer.
The same thing can be seen whole in a small box. Of the 720 ways to fill two rows of three squares, sliding reaches exactly 360; of the 24 ways to fill a two-by-two box, exactly 12. We listed them all.
To test a box by hand, read the tiles row by row and count the pairs that stand in the wrong order, a larger number before a smaller one. Add the number of the row the empty square is in, counting from the bottom. If the total is odd, the box can be solved; if it is even, it cannot. For the solved box that is 0 + 1.
You will never meet an unsolvable box here. The page does not deal the tiles out at random: it starts from the solved box and makes random moves, never undoing the move it has just made — 24 moves on Normal, 50 on Hard, 150 on Expert. A box that came out almost solved is dealt again. Two things follow. The shortest solution is never longer than the shuffle, and on Normal it is usually close to it: 20 to 24 moves in 82% of deals. And it is always an even number, on every level, because the shuffles are even: all 8,050 deals we generated had an even shortest solution.
Before you can touch the board, the computer solves the box. It uses iterative-deepening A*, the algorithm Richard Korf introduced in 1985 on this very puzzle: a depth-first search that is allowed a little more depth on each pass and never goes down a line that provably cannot finish in time. The proof is an estimate that never overstates — the sum of every tile's distance from its square, plus two moves for each pair of tiles that are in their own row or column but in the wrong order. Because the estimate never overstates, the first solution found is a shortest one.
| Normal | Hard | Expert | |
|---|---|---|---|
| Shuffle, moves | 24 | 50 | 150 |
| Positions the search looks at, typical | 153 | about 17,000 | about 464,000 |
| Shortest solution: typical, and the range in our deals | 22 (8–24) | 36 (18–48) | 46 (28–60) |
| Your limit | 2 × shortest | 1.5 × shortest | 1.25 × shortest, rounded up |
| Spare moves over the shortest, typical | 22 | 18 | 12 |
The search is capped at three million positions, about half a second. A box that needs more is thrown away and dealt again before you see it. On Normal that never happened in 5,000 deals and on Hard 7 times in 2,007, but on Expert it removes a third of all shuffles (529 of 1,579) — the ones the search finds hardest. So an Expert box is hard but not the hardest there is: its shortest solution averages 46.7 moves, against about 53 for a truly random box, and of 300 truly random solvable boxes we tried, the page's search finished only 157 inside its cap.
The counting is strict. Every tile that moves is one move, so clicking a tile two or three squares from the gap slides the line and costs two or three. The limit is on screen before your first move, next to the length of the shortest solution. You win if you finish in no more moves than the limit; the result is recorded only when the box is solved, so a game you abandon is not counted against you. After a game, Game → The computer's solution replays its shortest line from the starting position, which is the quickest way to see what it saw and you did not.
The hardest positions of the 15 puzzle need 80 moves, counting one tile per move. That is a published result of 1999 (general knowledge), far beyond anything this page deals: the longest shortest solution in our 1,050 Expert deals was 60.
Fix tiles 1 and 2, then bring 3 and 4 in as a pair: 3 in the corner, 4 under it, the empty square on the place of 3, then 3 left and 4 up. Do the second row the same way, then 9 and 13 as a pair down the left column, and finish the last six squares by walking the empty square in circles. On random boxes this takes 96 moves on average.
No. Of the 20,922,789,888,000 ways to fill the box exactly half can be reached from the solved position. Count the pairs of tiles in the wrong order, add the row of the empty square counted from the bottom: an odd total means solvable. The boxes on this page are shuffled by legal moves, so they are always solvable.
Each move swaps one tile with the empty square, and returning the empty square to its corner always takes an even number of moves. An even number of swaps cannot equal a single exchange of two tiles, so the box with only 14 and 15 exchanged is unreachable.
It depends on the box. A random solvable box needs about 53 moves at best, and the hardest need 80; both are published results. On this page the shortest solution is typically 22 moves on Normal, 36 on Hard and 46 on Expert, and it is shown above the board before you start.
With the row-by-row method, about 96 on a random box, a little under twice the shortest solution. Planning a whole row at once instead of one tile at a time cuts a quarter to a third: on the Normal deals here the average fell from 47.6 moves to 32.4.
It runs iterative-deepening A* with an estimate that never overstates the remaining moves: the tiles' distances from their squares plus a penalty for tiles in the right line but the wrong order. That prunes almost everything: a Normal box takes a typical 153 positions, an Expert box about 464,000, under a second.
You cannot solve it in fewer moves, since the computer's solution is the shortest there is; you win by staying inside the limit. The plain method does that in 46% of Normal games, 10% on Hard and under 1% on Expert. Planning whole rows wins 88%, 54% and 13%.