Sliding Puzzle

By shrinking the frame. Finish the top row and never touch it again, then the left column of what is left, and repeat — each pass turns an n × n puzzle into a smaller one, until a 3 × 3 corner is all that remains and you can simply see the end. Trying to place tiles in number order across the whole frame instead is the usual mistake: tile 6 goes home, then tile 7 arrives and has to push 6 out of the way to get past it.

1. 1Fill the top row, left to rightPlace every tile of the row except the last two, one at a time, and treat each finished cell as a wall you never move through again.
2. 2Place the last two of the row togetherPut the second-to-last tile in the CORNER cell and the last tile directly below it, then rotate them both into place with two slides. Placing them one at a time deadlocks — see below.
3. 3Do the same down the left columnSame method rotated a quarter turn: all but the bottom two, then the bottom two staged and rotated together.
4. 4Alternate until a 3 × 3 corner is leftA 4 × 4 frame becomes a 3 × 4, then a 3 × 3. A 5 × 5 takes two more passes to get there.
5. 5Finish the cornerEight tiles in nine cells is small enough to solve by eye, and small enough that this page solves it by exhaustive search — so the hint there is a proven shortest move.

Because a slide cannot change a certain quantity, and the finished frame has a particular value of it. Count the inversions: pairs of tiles that are out of order when you read the frame like a book, ignoring the gap. A sideways slide changes nothing at all. A vertical slide jumps one tile over the n − 1 tiles in between, which flips the inversion count by an odd amount on an even-width frame and an even amount on an odd-width one — and it also moves the gap one row.

• Odd width (3 × 3, 5 × 5) — solvable exactly when the inversion count is even.
• Even width (4 × 4) — solvable exactly when the inversions plus the gap's row counted up from the bottom come to an odd number.
• Either way — the arrangements split into two equal halves, and no slide crosses between them.

This board does not take that rule on trust. A 2 × 2 frame has 24 arrangements; a search from the solved frame reaches exactly 12 of them, and they are exactly the 12 the rule accepts. A 3 × 3 frame has 362,880 arrangements; the same search reaches exactly 181,440, and again the rule and the search agree on every one. Only arrangements from the reachable half are ever dealt here.

The famous consequence: take a finished frame and swap just the last two tiles. One transposition flips the parity, so that arrangement is now in the unreachable half and nobody will ever sort it. That exact position was the prize puzzle of the fifteen-tile craze of 1880, and the reason none of the prizes was ever paid: Johnson and Story had already published the proof in the American Journal of Mathematics in December 1879, a few months before the first advertisement went up.

Those route lengths are this page's own solver, measured across the first 1,000 deals of each frame: it averages 84 moves on the 4 × 4 frame and never needed more than 118, and averages 197 on the 5 × 5 frame with a worst case of 258. A move is one tile moving one cell — pushing a line of three counts three — so those figures are directly comparable with a person's move counter.

The shortest possible solution is a different question. On the 3 × 3 frame the answer is known exactly, because all 181,440 positions fit in memory: the average position is 21.97 moves from home, and precisely two positions in the whole space need 31, which is the worst there is. On the fifteen-tile frame the equivalent figure is 80 moves, established by Korf and Schultze's exhaustive search in 2005 — a computation that took a cluster, not a browser tab.

On the 3 × 3 frame, yes, and this page does it. A breadth-first search from the finished frame reaches all 181,440 positions and stores the exact distance of each in a table of 362,880 bytes, so the hint gives a genuine shortest move and the optional counter beside it is the true number of moves you still need.

On the 4 × 4 frame, no — and this is the honest part. There are 10,461,394,944,000 reachable positions, and holding one byte for each would need ten terabytes. So the solver here does not search: it places tiles row by row and column by column, exactly as the method above describes, and finishes the last 3 × 3 corner with the exact table. What it plays out always solves the puzzle, and it is never claimed to be the shortest route. On 5 × 5 the space is 7,755,605,021,665,492,992,000,000 positions and the same applies with more room to spare.

• Click or tap a tile in line with the gap. A tile three cells away takes the two between it and the gap along with it, and the counter goes up by three.
• Arrow keys slide a tile in the direction of the arrow — up moves the tile below the gap upwards. Every legal move on the frame is one of those four keys.
• Undo walks back the last 40 slides — a line push is one of them, however many tiles it carried, so forty entries can be a good deal more than forty moves — and Hint lights up one tile to slide next.
• Solve it for me plays a full solution out a move at a time, and Escape stops it. A puzzle the helper has played a move on is recorded as unsolved, so the fewest-moves record stays your own.
• Nothing is ever removed from the frame and no move is illegal in a way that loses the game: a sliding puzzle cannot be made unwinnable by playing it badly.

If you like the shrinking-frame idea, 2048 is the same board with the opposite problem — every move pushes every tile at once — and block puzzle asks you to clear lines rather than sort them. For pure deduction on a grid, try nonogram.