Why does it say my sliding puzzle is unsolvable?

Every slide swaps the blank with one tile, and one count keeps its parity through every slide. Read the tiles row by row with the blank left out and count the pairs that are out of order, the inversions. On a 3 x 3 board a slide never changes whether that count is odd or even; on 2 x 2 and 4 x 4 boards, add the blank's row counted from the top, and that sum keeps its parity instead. If the start and the goal disagree, no run of slides joins them, so exactly half of all arrangements can never reach a given goal. A solved 4 x 4 with 14 and 15 swapped is the famous case: 1 inversion plus the blank's row 4 makes 5, against the goal's 4.

Is the answer the shortest possible?

Only where it says proven shortest. IDA* and breadth-first rule out every shorter sequence before they answer, and on 2 x 2 and 3 x 3 boards they always finish, so every answer there is a shortest one; other answers of the same length may exist. On 4 x 4, IDA* is proven shortest when it finishes inside your node limit; if it reaches the limit first it says unresolved and gives a proven minimum, such as at least 26 moves. Row by row is quick and can be longer than the shortest; it is called shortest only when its length equals the lower bound.

How long does a 4 x 4 (15 puzzle) search take?

It depends on the board and your device. The search counts nodes, the boards it looks at, and stops at your node limit: 100,000,000 by default, and anything from 1,000 to 1,000,000,000. A randomly shuffled 4 x 4 usually needs somewhere between a few hundred thousand and several tens of millions of nodes, and a fast computer searches millions of nodes a second. While it runs you see the nodes used and the length ruled out so far, and Cancel stops it at once. Row by row answers any solvable 4 x 4 in a fraction of a second, usually without a proof that it is the shortest.

How do I enter my puzzle?

Type the tiles into the text field under each board in reading order, row by row from the top, with 0, _ or . for the blank, for example 1 2 3 / 4 5 6 / 7 8 _. Spaces, commas, slashes and semicolons all separate tiles. Or select a square and then another square on the same board to swap them; with a keyboard, the arrow keys move between squares and Enter or Space selects. The goal can be any arrangement: two buttons set the tiles in order with the blank last or first, and Shuffle start deals a random board that is always solvable.

What do the moves mean?

Each number is the tile that slides into the blank, in order, and the line under it gives the way each tile moves: U up, D down, L left, R right. Some apps list the blank's moves instead, which run the opposite way. Step through the answer with First, Back, Next and Last or the step slider, or press Play to watch it; the board marks the tile that just moved, and Copy puts both boards and the answer on the clipboard as text.

What is the difference between IDA*, breadth-first and row by row?

IDA* searches in rounds, each round allowing a longer answer, and skips any line that a lower bound (Manhattan distance plus linear conflicts) shows cannot fit, so it needs very little memory. Breadth-first visits every board one move away, then two, and so on, keeping all of them in memory, which is why it runs on 2 x 2 and 3 x 3 only: a 3 x 3 start can reach 181,440 boards. Row by row places the tiles of one outer row, then one outer column, and then solves the smaller board left over with IDA*.

Can it solve a 3 x 4, a 5 x 5 or a picture puzzle?

It takes square boards of 2 x 2, 3 x 3 and 4 x 4 with numbered tiles, so a 3 x 4 or a 5 x 5 cannot be entered. For a picture puzzle of one of those sizes, number the pieces by the square each belongs in and type those numbers. It does not read or play puzzles on other sites.

Is my puzzle sent anywhere?

No. Every search runs in your browser, in a background worker where the browser can start one, and the boards and settings are saved in this browser's local storage so they are there next time.

Sliding Puzzle Solver

Enter a start board and a goal board, 2 x 2, 3 x 3 or 4 x 4, by swapping squares or typing the tiles, and the solver first checks tile parity: exactly half of all arrangements can never reach a given goal, and those are called unsolvable before any search runs. A solvable board is searched with IDA* or breadth-first, which prove the shortest move count on every 2 x 2 and 3 x 3 board, or row by row (3 x 3 and 4 x 4), which places an outer row, then an outer column, then solves the rest, for a quick answer that can be longer than the shortest. A 4 x 4 IDA* search runs in the background up to a node limit you set, shows its progress, can be cancelled, and reports unresolved with the lower bound it proved when it stops early. Every answer is replayed slide by slide to the goal before it is shown, and you can step through it or play it back.

Size

Solver

Node limit, 4 x 4 IDA*nodes

start3 x 3, example board

Start

Start as text

Goal

Goal as text

Select a square, then another on the same board, to swap them. Arrow keys move between squares, Enter or Space selects, Escape lets go. Editing the squares rewrites the text.

parity: 10 inversions, even, same as the goal's 0, even: solvable
lower bound: Manhattan 14 + linear conflicts 2 = 16
search: IDA*, exhaustive on 3 x 3
node limit: not used: this search always finishes

solutionno answer yet

Loading any saved boards.

Moves: none yet

Lower bound: 16 (Manhattan 14)

Inversions: 10, even

Playback: none

Solution as text

Sliding puzzle, 3 x 3
Start
2 1 6
7 _ 8
3 4 5
Goal
1 2 3
4 5 6
7 8 _
Solver: IDA*
Parity: 10 inversions, even, same as the goal's 0, even: solvable
Result: not solved yet

Examples

Each one loads both boards and the solver, then solves at once. The line beside it is what the solver says.

A solved 3 x 3 boardstart equals goal
0 moves: already solved
A solved 3 x 3 with 7 and 8 swappedparity checked before any search
unsolvable: 1 inversion against the goal's 0, so no run of slides can reach it
2 1 6 / 7 _ 8 / 3 4 5IDA*, each slide checked against the blank
18 moves, proven shortest, replayed slide by slide to the goal
7 2 4 / 5 _ 6 / 8 3 1, blank first in the goala common textbook 8-puzzle, breadth-first
26 moves, proven shortest, replayed slide by slide to the goal
A 4 x 4 at the default node limitIDA*, 100,000,000 nodes
32 moves, proven shortest, replayed slide by slide to the goal
The same 4 x 4 at a 1,000 node limitIDA* stopped early
unresolved at the 1,000 node limit: at least 26 moves
The same 4 x 4, row by rowtop row, left column, then the 3 x 3
36 moves, not proven shortest, replayed slide by slide to the goal
A 4 x 4 with 14 and 15 swappedthe old 14-15 puzzle
unsolvable: inversions plus the blank's row make 5 against the goal's 4, so no run of slides can reach it

Common questions

Why does it say my sliding puzzle is unsolvable?: Every slide swaps the blank with one tile, and one count keeps its parity through every slide. Read the tiles row by row with the blank left out and count the pairs that are out of order, the inversions. On a 3 x 3 board a slide never changes whether that count is odd or even; on 2 x 2 and 4 x 4 boards, add the blank's row counted from the top, and that sum keeps its parity instead. If the start and the goal disagree, no run of slides joins them, so exactly half of all arrangements can never reach a given goal. A solved 4 x 4 with 14 and 15 swapped is the famous case: 1 inversion plus the blank's row 4 makes 5, against the goal's 4.
Is the answer the shortest possible?: Only where it says proven shortest. IDA* and breadth-first rule out every shorter sequence before they answer, and on 2 x 2 and 3 x 3 boards they always finish, so every answer there is a shortest one; other answers of the same length may exist. On 4 x 4, IDA* is proven shortest when it finishes inside your node limit; if it reaches the limit first it says unresolved and gives a proven minimum, such as at least 26 moves. Row by row is quick and can be longer than the shortest; it is called shortest only when its length equals the lower bound.
How long does a 4 x 4 (15 puzzle) search take?: It depends on the board and your device. The search counts nodes, the boards it looks at, and stops at your node limit: 100,000,000 by default, and anything from 1,000 to 1,000,000,000. A randomly shuffled 4 x 4 usually needs somewhere between a few hundred thousand and several tens of millions of nodes, and a fast computer searches millions of nodes a second. While it runs you see the nodes used and the length ruled out so far, and Cancel stops it at once. Row by row answers any solvable 4 x 4 in a fraction of a second, usually without a proof that it is the shortest.
How do I enter my puzzle?: Type the tiles into the text field under each board in reading order, row by row from the top, with 0, _ or . for the blank, for example 1 2 3 / 4 5 6 / 7 8 _. Spaces, commas, slashes and semicolons all separate tiles. Or select a square and then another square on the same board to swap them; with a keyboard, the arrow keys move between squares and Enter or Space selects. The goal can be any arrangement: two buttons set the tiles in order with the blank last or first, and Shuffle start deals a random board that is always solvable.
What do the moves mean?: Each number is the tile that slides into the blank, in order, and the line under it gives the way each tile moves: U up, D down, L left, R right. Some apps list the blank's moves instead, which run the opposite way. Step through the answer with First, Back, Next and Last or the step slider, or press Play to watch it; the board marks the tile that just moved, and Copy puts both boards and the answer on the clipboard as text.
What is the difference between IDA*, breadth-first and row by row?: IDA* searches in rounds, each round allowing a longer answer, and skips any line that a lower bound (Manhattan distance plus linear conflicts) shows cannot fit, so it needs very little memory. Breadth-first visits every board one move away, then two, and so on, keeping all of them in memory, which is why it runs on 2 x 2 and 3 x 3 only: a 3 x 3 start can reach 181,440 boards. Row by row places the tiles of one outer row, then one outer column, and then solves the smaller board left over with IDA*.
Can it solve a 3 x 4, a 5 x 5 or a picture puzzle?: It takes square boards of 2 x 2, 3 x 3 and 4 x 4 with numbered tiles, so a 3 x 4 or a 5 x 5 cannot be entered. For a picture puzzle of one of those sizes, number the pieces by the square each belongs in and type those numbers. It does not read or play puzzles on other sites.
Is my puzzle sent anywhere?: No. Every search runs in your browser, in a background worker where the browser can start one, and the boards and settings are saved in this browser's local storage so they are there next time.

A move count is called shortest only when it is proven, by an exhaustive search (IDA* and breadth-first finish one on every 2 x 2 and 3 x 3 board) or by equalling the lower bound; a 4 x 4 IDA* search that reaches your node limit says unresolved and gives the lower bound it proved. Solvability is decided exactly from tile parity before any search, and every returned sequence is replayed move by move to the goal before it is shown.