Sliding Puzzle Solver
Enter a 3x3, 4x4 or 5x5 slide puzzle and get the moves that solve it, one step at a time. The solver first checks whether your scramble can be solved at all. It runs in your browser and nothing is sent anywhere. The example below is one of the two hardest 3x3 positions.
Press Ctrl+Enter or ⌘+Enter to solve.
Or click two cells to swap them
Ready. The width (3) is odd, so only the inversions count: 24 inversions, which is even, so it can be solved.
How to use the sliding puzzle solver
- Choose the board size.
- Type the tiles row by row from the top left, using _ for the blank, or click two cells on the board to swap them.
- Read the solvability check under the buttons. If the board cannot be solved, it says why.
- Press Solve, then use Next and Previous to step through the moves. Each step names the tile to slide and the direction it moves.
Worked example: 31 moves on a 3x3
The board 8 6 7 / 2 5 4 / 3 _ 1 is one of only two 3x3 positions that need 31 moves, the most any 3x3 scramble needs. The solver finds this shortest solution (tile number and the direction it slides):
5↓ 6↓ 8→ 2↑ 3↑ 5← 1← 4↓ 7↓ 8→ 6↑ 3→ 5↑ 1← 4← 7↓ 8↓ 6→ 3↑ 5→ 1↑ 4← 7← 8↓ 6↓ 3→ 2→ 1↑ 4↑ 7← 8←
How the solver finds the shortest solution
For 3x3 and 4x4 boards the solver uses IDA* (iterative deepening A*). It searches move sequences depth first, but cuts off any branch whose moves so far plus an estimate of the moves left exceed a bound, then raises the bound and tries again.
The estimate is the Manhattan distance, the sum of how many rows and columns each tile is from its home, plus linear conflict: when two tiles are in their home row but in the wrong order, one must leave the row and come back, which costs two extra moves. The estimate never exceeds the true number of moves, so the first solution found is a shortest one.
Most 4x4 scrambles solve in under a second, but the hardest need 80 moves and billions of positions. The search runs in a background thread, so the page stays responsive, and it stops after 20 seconds with a message. You can also cancel it.
A 5x5 board has too many positions for an optimal search in a browser. For 5x5 the solver works row by row, the way people do, and says that the result is not the shortest. Shuffle on a 4x4 makes a board 50 random slides from solved so it stays quick to solve; on 3x3 and 5x5 it picks any solvable arrangement.
How to solve a sliding puzzle by hand
- Solve the top row first, one tile at a time. Bring each tile next to its home, then move the blank around it to push it in.
- The last two tiles of a row go in together. Put the last tile in the second-to-last tile's home and the second-to-last tile directly below it, then rotate both into the row.
- Repeat row by row until two rows are left. Do not disturb the finished rows.
- Solve the last two rows column by column from the left, using the same pairing trick turned on its side.
- Rotate the final 2x2 block until it is in order.
Why half of all scrambles are impossible
Read the tiles left to right, top to bottom, skipping the blank. An inversion is a pair where a larger number comes before a smaller one. A sideways slide does not change the reading order. On a board with an odd width, a vertical slide moves one tile past an even number of others, so the number of inversions stays even or stays odd forever. The solved board has zero, so only boards with an even count can be solved.
On an even width, such as 4x4, a vertical slide changes the inversion count by an odd number and moves the blank one row. So add the blank's row, counted from the bottom, to the inversions: the board can be solved only when the total is odd. Swapping any two tiles flips the parity, which is why exactly half of all arrangements are impossible, including the famous 14-15 swap.
FAQ
- Is the solution the shortest possible?
- For 3x3 and 4x4 boards, yes. The solver uses IDA* search with Manhattan distance plus linear conflict, which never overestimates the moves left, so the first solution it finds is a shortest one. For 5x5 boards it solves row by row instead, which is fast but usually not the shortest.
- Why does it say my puzzle cannot be solved?
- Exactly half of all tile arrangements can never reach the goal. Every slide keeps a parity value the same, so a board with the wrong parity, such as a solved board with two tiles swapped, is impossible. The solver counts inversions to check this before searching.
- Why does a 4x4 puzzle sometimes time out?
- A 4x4 puzzle has about 10 trillion solvable positions and the hardest need 80 moves. Most scrambles solve in under a second, but some need billions of positions checked. The search stops after 20 seconds and says so, and you can cancel it at any time.
- How do I enter my puzzle?
- Type the numbers row by row from the top left, with _ or 0 for the blank. Spaces, commas, slashes and new lines all work as separators. You can also click one tile and then another to swap them on the board.
- Is my puzzle sent anywhere?
- No. The search runs in a background thread in your browser. The board is not uploaded, saved or added to the URL.