What this game is
The 15 puzzle is fifteen numbered tiles in a box with room for sixteen. One square is empty, and tiles can only slide into it.
The goal is to put them in order, 1 to 15. The machine playing against you here is of a particular kind: it does not race your fingers, it finds the shortest possible solution in a fraction of a second. You get the same box and must stay within the limit — the shortest solution times your level's margin.
On normal the margin is double, and winning is realistic. On expert it is a quarter on top of a near-random position: a contest against a search that sees dozens of moves ahead.
Rules
- Click a tile next to the empty square and it slides in. A tile further along the same row or column slides the whole line; every tile moved is one move.
- Arrow keys work too: an arrow moves the tile on that side of the empty square.
- A tile already in its place turns green.
- Solve it within the limit and you win; take longer and the computer does. The limit appears above the board as soon as the computer has finished its search.
- After a game, Game → The computer's solution plays the shortest solution from the starting position.
How to solve it
- The classic method goes row by row: first the top row 1–2–3–4, then the second, and the last two rows together, column by column.
- The last tile of a row is the hard one: park it under its place with the one before it alongside, and bring both in with a single turn.
- Do not break what is done. If a placed tile has to move, put it back as soon as you can.
- Row by row is reliable but long. To stay within the limit on the harder levels, watch several tiles at once and walk them home together rather than one at a time.
A bit of history
The puzzle was invented by Noyes Chapman, a postmaster in Canastota, New York, in the 1870s. In 1880 it became a craze, played in offices, in the street and in session halls. The famous puzzle-maker Sam Loyd later claimed it as his own and told of a thousand-dollar prize for swapping tiles 14 and 15 — a position that cannot be solved.
That had been proved in 1879 by William Johnson and William Story: exactly half of all arrangements are unreachable, and the parity of the permutation decides which. There are 16!/2 reachable positions, about 10.5 trillion. That is why the box here is always scrambled by random moves from the solved state: it is then solvable by construction.
For machines the 15 puzzle became the classic search problem. In 1985 Richard Korf introduced the IDA* algorithm and found optimal solutions to random positions for the first time. In 1999 it was proved that any position can be solved in at most 80 moves — the puzzle's "God's number".
About the levels
Normal: scrambled by 24 random moves, limit twice the shortest solution. A careful row-by-row solve usually fits.
Hard: 50 random moves, limit one and a half times the shortest. You have to think several tiles ahead.
Expert: 150 random moves — a near-random position whose shortest solution is usually around 45 to 50 moves — and a limit only a quarter longer. The computer pays under a second of search for it; a human, a very good game.