Thirty-one moves from solved

The puzzle that is exactly half solvable settles a yes-or-no question. Hand someone a sliding puzzle in some arrangement, and one number — the pairs out of order in the reading plus the blank’s distance from its corner, taken modulo two — says whether it can be solved at all. Half the arrangements can, half cannot, and no amount of cleverness moves an arrangement from one half to the other.

That answer is complete and it is also strangely unsatisfying, because it is not the question anyone holding the puzzle is asking. They already believe it can be solved; they want to know how long it will take. And the parity argument, for all its finality, says nothing about that at all. An arrangement one slide from solved and an arrangement that needs thirty slides both pass the test with the same bit.

This essay answers the second question on the three-by-three tray, the one sold as the eight-puzzle, and it answers it the only way currently known for a puzzle of this kind: by visiting every arrangement that can be reached and recording how far each one is.

Every arrangement, sorted by distance #

The three-by-three tray has nine squares and eight tiles, so there are $9! = 362{,}880$ ways to lay the tiles and the blank into it. Parity cuts that to half, $181{,}440$, and every one of those can be reached — that is the content of the half-solvable result. Nothing else is special about them, and they are few enough to list.

The listing is a breadth-first search, which is the most literal algorithm there is. Start from the solved tray and call it distance zero. Every tray one slide away is distance one. Every tray one slide from those, not already seen, is distance two. Continue until a round finds nothing new. Each arrangement is recorded the first time it is met, and because the rounds go outward one slide at a time, the round in which it is first met is exactly the fewest slides that reach it — which, since every slide can be undone, is also the fewest slides that solve it.

Read left to right, the bars are one, two, four, eight, sixteen, twenty, thirty-nine, sixty-two, and on up past twenty thousand. The first few double because at the start almost every slide goes somewhere new. The doubling fails quickly — by distance five the tray has twenty arrangements where doubling would have given thirty-two — because slides start to lead back into arrangements already recorded, and because the blank in a corner has only two moves while the blank in the middle has four.

Then, in the low twenties, the counts peak and fall. The average arrangement is almost exactly twenty-two slides out, and nearly three quarters of the reachable tray lies between twenty and twenty-six. At thirty the bar has shrunk to two hundred and twenty-one, and at thirty-one it is two. The search then runs one more round, finds nothing, and stops. No arrangement of the eight-puzzle needs more than thirty-one slides, and that sentence is not an estimate: it is what an exhaustive list says.

The shape deserves a moment, because it is not the shape the early doubling suggests. A graph in which every vertex had four neighbours and no route ever closed up would keep doubling until it ran out of vertices and then stop dead. This one rises for twenty rounds and then spends ten rounds dying away, which is the signature of a graph that is finite, fairly well connected, and full of short cycles. The long thin tail is where the difficult arrangements live, and there are very few of them.

The two at the far end #

Two arrangements sit thirty-one slides from solved. They can be drawn, and they are worth looking at, because they are not what intuition picks as “maximally scrambled”.

The obvious candidate for the worst arrangement is the one with every tile rotated half a turn about the centre, or the tiles written in reverse. Neither is on the list. The two actual extremes each keep one tile at home, and each has a recognisable structure: the eight and the seven have been walked round to the top row, the one sits in the far corner, and the middle is filled with tiles that are each one or two squares from home. What makes them hard is not that the tiles are far away. It is that they are in each other’s way.

That can be measured. The quickest lower bound on the number of slides is to pretend each tile can glide through the others: a tile two rows and one column from home then needs at least three slides of its own, and the sum over the tiles of these taxicab distances can never exceed the true answer, because a single slide moves a single tile a single square. For both of the far arrangements that sum is twenty-one. The tiles, left to themselves, would need twenty-one slides; sharing a tray with one hole in it, they need thirty-one. Ten slides — a third of the solution — are spent on traffic.

This is also the answer to a question the half-solvable argument raised and could not settle, about how different the two halves are. An invariant sorts arrangements into classes and then treats every member of a class as the same. Here, inside the one class that can be solved, arrangements differ by a factor of thirty-one in how hard they are, and the ones at the far end look, to the eye, only moderately scrambled.

Parity again, as a law about distance #

Parity was supposed to be finished once it had split the arrangements in two. It is not, and the search makes the second appearance impossible to miss.

Colour the nine squares like a chessboard, so that the blank’s home corner is dark. There are five dark squares and four light ones. Every slide moves the blank to a neighbouring square, which is always the other colour. So after an even number of slides the blank is on a dark square, and after an odd number it is on a light one, whatever the slides were.

Now run that backwards. An arrangement at distance $d$ is solved by $d$ slides, which carry the blank from wherever it is to its dark corner. If the blank starts on a dark square, $d$ must be even; on a light square, odd. The parity of the distance can be read off the arrangement without solving it — from the colour of one square.

The totals are exact for a reason as clean as the colouring. Among the reachable arrangements the blank is equally likely to be on any of the nine squares — for each position of the blank, the eight tiles can be arranged in $8!/2 = 20{,}160$ reachable ways, the same number wherever the blank sits. Five squares are dark, so five ninths of the arrangements have even distance. That is why the bars alternate in height through the middle of the chart: the even ones stand on five squares’ worth of arrangements and the odd ones on four, and the distribution is not one smooth hump but two interleaved ones.

The same fact appears in the distance of a code and anywhere else a graph can be two-coloured: on a bipartite graph, every walk between two vertices has the same parity. The tray’s graph of squares is bipartite, the blank walks on it, and the solution length inherits the parity of the walk.

A second parity, hiding in the bound #

The taxicab bound turns out to carry the same bit, and its version is subtler.

Each slide moves exactly one tile one square — nearer its home or farther from it. So each slide changes the sum of taxicab distances by exactly one, up or down, never by zero and never by two. After $d$ slides the sum has changed $d$ times by one, and the arrangement’s sum and its distance from solved therefore have the same parity. Combined with the bound itself, this says something sharp: the taxicab sum is at most the distance, and the gap between them is always even.

The chessboard pattern is the parity; the empty triangle above the diagonal is the bound; and the thickness of the band below it is the traffic. Near the origin the band is thin — for arrangements a few slides from solved, the tiles hardly obstruct one another, and the bound is nearly right. Further out the band fans downward: among arrangements at the same distance in the high twenties, the bound can be a few slides short or well over a dozen, and nothing about an arrangement’s appearance says which.

This matters to anyone who has to solve these puzzles by computer rather than by listing. The standard method searches from the scrambled arrangement, depth-first, and abandons any line of play whose moves so far plus the taxicab bound already exceed the current budget — a method called iterative deepening with a heuristic, and it is exactly as fast as the bound is tight. The parity of the gap is used there too: since the gap is even, the budget can be raised two at a time rather than one, halving the number of passes. On the eight-puzzle none of this is needed, because the whole tray fits in a list. On larger trays it is the only method there is.

What a shortest solution looks like from inside #

The search does more than measure distances. Once every arrangement carries its distance, a shortest solution from any of them can be read off by walking downhill: from an arrangement at distance $d$, some slide leads to one at $d - 1$, and following such slides reaches solved in exactly $d$ moves.

Watching it is instructive in the way a chess engine’s best line is instructive: it does not look like progress. The one tile that begins at home is dislodged on the first slide. For the next nineteen moves no tile is on its own square at all, and a person measuring progress by tiles in place would conclude the solver was lost. Then, in the last dozen moves, the tiles fall home one after another, as though the whole tray had been wound up and released.

This is the tray’s version of a general truth about searching large spaces, and it is the reason simple rules of thumb do badly here. A method that insists on never moving a correctly placed tile — the way most people learn to solve the puzzle, finishing the top row first and then never touching it — gives up access to the shortest solutions entirely. Human methods for the eight-puzzle are therefore well above thirty-one on the hard arrangements, not because the people are careless but because the shortest routes pass through arrangements that look like regress.

The pattern is also a warning about the taxicab bound’s meaning. The bound falls by at most one per slide, and on this route it barely falls for twenty moves: the solver spends that time rearranging the queue so that the last twelve slides can each put a tile home.

Shape decides the far end as much as size does #

The same search runs on every tray small enough to fit in memory, and the comparison is where the eight-puzzle’s thirty-one stops being a lone fact.

The two-by-two tray is a cycle of four squares and its twelve reachable arrangements lie on a single ring, so the farthest is six slides away, exactly opposite solved. The two-by-three tray, six squares, reaches twenty-one. Then the two-by-four and the three-by-three, which differ by one square, give thirty-six and thirty-one — the smaller tray has the more distant far end.

The reason is the queue. On a tray two squares high, a tile can only overtake another by going round a two-by-two block, and every such overtaking costs several slides. On a three-by-three tray the middle row gives tiles room to pass, and the blank can reach any square from the centre in two moves. Long thin trays behave like a single-lane road with passing places; square ones like a town square.

The two-by-four extreme makes the point numerically. Its tiles, gliding through each other, would need sixteen slides. Confined to two rows, they need thirty-six. More than half of the solution is traffic, against a third on the square tray, and it is the same kind of traffic — pairs of tiles that must swap order and can do so only by a long detour round the block beside them.

The fifteen-puzzle, and why no figure can do the same there #

The puzzle that made the subject famous is the four-by-four tray, with fifteen tiles, and it is exactly where the method in this essay stops. Its reachable half holds $16!/2$ arrangements — a little over ten trillion — and a breadth-first search over them is not a figure; it is a project.

It was done. Arrangements needing eighty slides were found by computer search in the 1990s, and it was shown by the end of the decade that none needs more. In 2005 Richard Korf and Peter Schultze carried out a complete breadth-first search of the whole four-by-four tray, storing each round on disk, and confirmed that eighty is the far end. That number is a theorem only in the sense that thirty-one is: an exhaustive computation, checked, with no argument behind it that a person can follow.

And no such argument is expected. Daniel Ratner and Manfred Warmuth showed in 1990 that finding a shortest solution on the general $n \times n$ tray is NP-hard, so there is no known method that does much better, in the worst case, than a search whose cost grows exponentially with the tray. The same pattern holds for the Rubik’s cube, whose greatest distance in face turns — twenty — was settled in 2010 by a computation using decades of accumulated cleverness and many years of processor time. The group drawn as a map is the right frame for all of these: the arrangements are vertices of a graph whose edges are the moves, the distance from solved is the distance in that graph, and the far end is its radius. How fast the ball fills is the question the bar chart above answers for one finite graph: how many vertices lie within each distance of the start.

Where exhaustion stops being an answer #

The figures above are complete: they rest on a list of every reachable arrangement, and there is nothing they could have missed. What they cannot do is explain. Thirty-one is the far end of the eight-puzzle because a list says so, and the list offers no reason why the answer is not thirty or thirty-two. The same is true of the fifteen-puzzle’s eighty and the cube’s twenty — each is the output of a search, and no argument predicts it from the shape of the tray.

The pictures also stay silent about which arrangements are hard in any describable way. The two extremes of the three-by-three tray share a structure that is easy to see and not easy to state as a rule, and the arrangements at distance thirty — two hundred and twenty-one of them — do not obviously resemble each other at all. No invariant computed from an arrangement, in the way parity is, is known to give its distance; the taxicab sum is the best simple bound, and it is off by ten on the far arrangements and by twenty on the long tray’s.

What survives the move from existence to distance is the parity itself. It told the half-solvable argument which half an arrangement lies in, and here it tells the length of every solution modulo two: read the blank’s square, and the answer is even or odd before any slide is made. That is the one bit a permutation carries, and it keeps turning up because the board beneath the tiles is two-coloured. A board that could not be two-coloured would lose it — which is what happens on the graphs in the essay on sliding tokens along any graph, where one odd cycle is enough to make every arrangement reachable.

Still open: a reason for the numbers #

Two questions sit beside each other here, and only the easy one has a general answer.

Whether an arrangement can be solved is decided by a crossing count and a colour, on a tray of any size, in a few seconds by hand. How far it is from solved is decided, on the eight-puzzle, by a list of 181,440 entries; on the fifteen-puzzle by a search over ten trillion; and on anything larger by nothing at all, since an efficient method for shortest solutions would be a surprise of the first order.

The far ends themselves are the sharpest open piece. For the $n \times n$ tray the worst case is known to grow like $n^3$ — solving row by row needs that many slides, and some arrangements need a constant fraction of it — but the constant is not known, and the exact far end is known only for the smallest trays listed above and the four-by-four. Whether the numbers six, twenty-one, thirty-one, thirty-six, fifty-five and eighty follow any rule that could be stated rather than computed is not known, and nothing in the lists suggests one.