Tile Order is the sliding number puzzle — the 15-puzzle, the one with the tiles and the single empty square. We wanted it to show you the fewest moves a board can be solved in, not an estimate, because a puzzle that tells you "par 34" when the truth is 28 is a puzzle that has quietly decided your best result does not count.

Showing a proven minimum means solving optimally, which for a 4x4 means IDA* and a good heuristic. We built that. Then we measured it, and it was unusable.

The measurement

A fully shuffled 4x4 costs up to 22 seconds to prove optimal. Not to solve — solving is instant — but to prove that no shorter route exists. That is the expensive half, and it is the half a "fewest" label is promising.

Nobody waits 22 seconds for a puzzle to load.

The obvious next move is to make the solver faster. Better heuristic, better move ordering, transposition tables. We did some of that and it helped, and it was never going to close a gap that size.

The move that actually worked

We stopped shuffling.

A board built by walking the tiles away from the solved state, to a capped depth of 45, costs 9ms median and 223ms worst case to prove. Same solver. Same heuristic. The only thing that changed is which boards we ask it about.

That is a ~2000x improvement obtained by making the question easier rather than the answer faster, and it generalises: when a game wants to show a proven number, the generator is the lever, not the search. A bounded generator is what buys the claim.

What it costs, said out loud

There is no free lunch here and the copy says so. Those capped 4x4s average 34 moves, where a free shuffle averages around 53. The boards are shorter. A player who wants a genuinely hard 15-puzzle is not getting one from us at that size.

We decided that was the right trade, because a shorter board with a true number beats a longer board with a number we cannot stand behind. But it is a trade, and hiding it would make the "fewest" label do the lying instead.

And where the proof is impossible, we changed the word

The cap works at 3x3 and 4x4. At 5x5 and 6x6 the search is out of reach at any depth worth playing, so those sizes do not get a proof.

They also do not get the word. 3x3 and 4x4 show Fewest — proven, and shown in green. 5x5 and 6x6 show Par — the best route the game itself holds, beatable, and we would like you to beat it.

One label covering two different claims is the lie. If you cannot prove it, say a different word.

Two ways a solver returns a wrong number and never looks broken

Both of these shipped into a working game and neither threw an error.

A shared scratch buffer inside a recursive search. One Int32Array(4) held the neighbouring cells, reused at every level of the IDA* depth-first search. A child overwrites the parent's list mid-loop, so the parent then "moves" the gap to a square it is not adjacent to. Routes came back containing the same cell twice, and the board still looked plausible. The fix is one buffer per depth. A non-recursive breadth-first search with the identical pattern was fine — recursion is the trigger.

A heuristic that over-counts is not conservative, it is wrong. Our linear conflict term counted out-of-order pairs. A row holding 3,2,1 has three such pairs, so it billed 6 extra moves — but only two tiles actually need to leave the row, so the truth is 4. Over-billing breaks IDA*'s admissibility, and an inadmissible heuristic returns a non-minimal answer. Still a number. Just not the smallest one, which is the only thing the label promised. The fix is 2 x (line length - longest increasing subsequence).

Neither bug was caught by asking "does the route solve the board?" Both routes solved the board.

What caught them

A brute-force breadth-first search on shallow boards, compared against the number we were about to show. It is 25 lines, it uses no heuristic, and because it uses no heuristic it cannot be fooled by a broken one.

This is the same move that saved a different generator of ours from shipping boards with every clue still on them: verify the counter, do not trust it. If a number is going on the screen, something that shares no code with the thing computing it should agree first.

One free result

Generating by walking away from the solved state removed the parity rule from the codebase entirely.

Half of all 15-puzzle arrangements are unsolvable, and normally you need a parity check to avoid dealing one. But a board reached by walking home-to-here is solvable by construction — you just walked the route — and the walk reversed is a real solution, which is also what lets an unprovable 5x5 back its par with something honest.

No solvability fact stored in two places, so no chance of the two disagreeing. That is a whole class of bug that stopped being possible, and we did not set out to fix it.

Play it: Tile Order · how to play

Related reading: we deleted our puzzle bank · rate a puzzle by what breaks without it