Which graphs let the tokens go anywhere

A sliding puzzle has two ingredients that are easy to run together. One is a set of tiles that get permuted. The other is a board — a particular arrangement of squares, some of them next to each other — on which the empty space moves. The half-solvable argument proved that exactly half the arrangements of the tray can be reached, and it proved it using both ingredients at once: the permutation’s parity and the blank’s distance, flipping together.

That leaves a question the tray cannot answer by itself. Is the half a fact about permutations — something any puzzle of sliding pieces would have to obey — or a fact about the board? The only way to find out is to change the board. Replace the grid of squares by any graph whatever, put a token on every vertex but one, and let a move slide a token along an edge into the empty vertex.

The answer was worked out completely by Richard Wilson in 1974, and it is one of the cleanest theorems about puzzles there is. It says the half is the board’s fault.

The tray is just a graph #

On the three-by-two tray, the squares are six vertices and two squares sharing a side are joined by an edge: seven edges in all, drawn as two rows of three dots with three vertical edges joining them. Nothing about the puzzle needs the squares to be square. What a slide does is carry a token along an edge into the empty vertex, and what makes an arrangement reachable is whether some sequence of such slides produces it.

So the tray’s puzzle is one instance of a general game, and every count on the tray can be recomputed as a count on its graph. The question becomes: with the empty vertex back at its home, which permutations of the tokens can the slides produce?

The search is the same breadth-first search that measured distances on the eight-puzzle: start from one arrangement, slide in every possible way, record what is new, repeat until nothing is. It is a complete census, and on a graph of six vertices there are only $6! = 720$ positions in all, of which $120$ have the empty vertex at home.

The count agrees with the tray: sixty of a hundred and twenty. But the graph has made one property of the tray visible that was easy to overlook on the board, and it is the whole of the story. The grid’s vertices can be coloured black and white so that every edge joins a black to a white — the tray’s chessboard colouring. The graph is bipartite: it has no cycle of odd length.

Why a two-coloured board forces the half #

The half-solvable proof can be retold in the language of graphs, and when it is, the colouring appears where the grid used to be.

Each slide exchanges the empty vertex with one token, so as a permutation of everything on the board — tokens and blank together — it is a transposition, and it flips the sign. Each slide also moves the empty vertex across one edge, from black to white or white to black. On a bipartite graph, therefore, the sign of the whole arrangement and the colour of the empty vertex’s position flip together at every move. Their combination never changes.

Now bring the empty vertex home. It is back on its original colour, so the combination says the sign is back to its original value too. With the blank where it started, the tokens have undergone an even permutation. That is exactly the tray’s invariant: the crossing count plus the blank’s taxicab distance, where the taxicab distance modulo two was only ever a way of saying which colour square the blank is on.

Read this way, the argument uses nothing about permutations beyond the sign, and nothing about the board beyond its two-colouring. Which means it breaks the moment the board cannot be two-coloured.

One triangle breaks it #

Add a single odd cycle. The smallest example is a house: a square with a triangular roof on top. The roof is a triangle, and a triangle is a cycle of length three.

The tour the empty vertex makes is a closed walk of five steps: up one edge, round the three edges of the triangle, and back down. Every closed walk on a bipartite graph has even length, because it has to return to the colour it started on; this one has odd length, which is exactly what a triangle permits. And the effect on the tokens is visible in the last frame. The two tokens on the triangle have swapped. Everything else is where it was.

A single exchange of two tokens is an odd permutation, and it has been produced with the empty vertex at home. So on this graph the invariant is simply false, and the argument that capped the tray at half has nothing to hold on to. What remains is whether anything else caps it.

Nothing does. Every one of the twenty-four arrangements is reachable. On this board the tokens really can go anywhere, and the famous impossibility of the fifteen-puzzle — the one Sam Loyd claimed to have offered a prize for, safe in the knowledge that nobody could collect — disappears.

That is the surprising half of Wilson’s theorem, and it recasts the tray completely. The fifteen-puzzle is half-solvable not because permutations have parity but because a chessboard has two colours. Sell the same puzzle on a tray with one triangular cell and every arrangement becomes solvable.

Every reachable arrangement is a product of tours #

The triangle’s tour is not a trick; it is the general mechanism, and it explains both halves of the tray’s answer at once.

Any sequence of slides that brings the empty vertex home is a closed walk on the graph, and a closed walk can be cut into pieces each of which runs out along a path, round a single cycle, and back along the same path. The running out and back cancels: whatever the path did on the way out, the return undoes. So every arrangement reachable with the empty vertex at home is a product of tours round cycles of the graph, each conjugated by the path that reaches it.

A tour round a cycle of length $k$ moves the $k - 1$ tokens on that cycle one place along it — the same observation the tray essay drew as a closed route of the blank. A cycle of $k - 1$ tokens has sign $(-1)^{k}$. On the tray every cycle of squares has even length, so every tour is an even permutation, which is the upper bound again. And the shortest tour, round a two-by-two block of squares, moves three tokens — a three-cycle. Overlapping blocks give three-cycles on overlapping triples, and three-cycles on overlapping triples generate every even permutation, which is the lower bound: the tray reaches all of its even half, not merely some of it.

On the house, the roof’s tour of length three moves two tokens, a transposition, and the square’s tour moves three. A transposition together with the three-cycles that generate the even permutations generates everything, and the census’s twenty-four follows. The whole of Wilson’s theorem is, in this reading, a statement about which permutations the tours of a graph’s cycles can generate, and the cases are sorted by the lengths of the cycles available: all even, some odd, or — on a cycle graph — only one cycle, whose tours all commute and generate nothing but rotations.

Graphs that cannot even do that much #

Not every graph reaches even half. The simplest counterexample is a cycle, and it fails for a reason that has nothing to do with parity.

On a cycle the tokens are threaded on a necklace. The empty vertex can wander, but every token keeps the same two neighbours in the cyclic order forever; the only freedom is how far round the whole necklace has turned. So the reachable arrangements are the $n - 1$ rotations of the tokens, and nothing else. The two-by-two tray is the four-cycle, which is why its move graph splits into rings of twelve: four positions of the blank, three rotations each.

A cycle is also the extreme case of a weakness Wilson’s theorem excludes by hypothesis. The theorem is stated for two-connected graphs — graphs with no single vertex whose removal disconnects them. The cycle is two-connected but has no room: there is no second route for a token to overtake along. Every other two-connected graph has at least one vertex of degree three, and that branch point is a passing place.

A graph that is not two-connected fails in yet another way, which the theorem deliberately does not address.

The bow tie has two odd cycles and still reaches only a sixth of its arrangements. Its trouble is the single vertex through which every exchange between the two halves must pass: a token can only cross when the empty vertex brings it to the centre, and at that moment the rest of the board is frozen in place. The graph’s triangles let tokens swap inside each wing, but the wings cannot trade occupants freely. Wilson excluded such graphs because on them the answer depends on how the pieces are hung together rather than on any single property, and the tidy classification applies to the two-connected pieces separately.

The graph with seven vertices #

Wilson’s theorem, in full: on a two-connected graph that is not a cycle, the tokens can reach every arrangement if the graph has an odd cycle and exactly the even arrangements if it does not — with one exception.

The exception is a graph Wilson called $\theta_0$. Take two vertices and join them by three separate paths: one with a single vertex in its middle, two with two vertices each. That is seven vertices and eight edges. It has odd cycles — the short path and either long path make a cycle of five — so the theorem’s main clause predicts all $6! = 720$ arrangements.

It reaches a hundred and twenty. The search leaves no room for doubt: a hundred and twenty distinct arrangements come back and no more, however long it runs. The permutations it reaches form a group of order 120 acting on six tokens, and it is a remarkable one — a copy of the permutations of five things, acting on six. The symmetric group on six letters has an automorphism that no other symmetric group has, one that exchanges its transpositions with products of three disjoint transpositions, and this strange copy of the five-letter group is its image under that twist. In a language the rest of algebra prefers, it is the group of fractional linear maps of the five-element field, acting on the six points of its projective line.

Why this graph and no other is an accident of size. A group generated by the slides on a two-connected graph is always transitive and usually enormous, and the proof of the main theorem shows it must contain a three-cycle, after which it is forced up to the whole alternating or symmetric group. On $\theta_0$ the three-cycle never appears: every short tour of the empty vertex produces permutations of the exotic group’s shape, and six points are too few for them to combine into anything larger. On a graph with one more vertex there is always room, and $\theta_0$ with a longer path is already back in the main case — the census includes the graph with paths of one, three and three inner vertices, which reaches exactly its even half.

What the census does and does not prove #

Each row of the opening table is an exhaustive search, so each is certain. Together they are twelve cases of a theorem about infinitely many graphs, which is exactly how many they prove.

The theorem’s own proof is a different kind of object. In outline, Wilson showed that on any two-connected graph other than a cycle, some tour of the empty vertex produces a three-cycle of tokens, and that the group generated by the tours is two-transitive; a two-transitive group containing a three-cycle contains the whole alternating group. The odd cycle then decides between the alternating group and everything, by the sign argument above. $\theta_0$ is the single graph on which the three-cycle cannot be produced, found by working through the small cases the general argument does not cover. None of that is in the pictures, which confirm the verdicts and cannot establish the reasons. A census of twelve graphs is also a census of small graphs, and small cases are exactly where exceptions live: had the search stopped at six vertices, $\theta_0$ would never have been met, and the clean dichotomy would have looked exceptionless. Its lesson runs the other way too. The exception was found because someone checked, and it is a single graph rather than a family because the proof that covers everything larger is an argument and not a search.

The census also cannot say how long anything takes. It shows that on the house every arrangement is reachable and says nothing about how many slides that costs — the question the essay on the eight-puzzle’s far end answered by exhaustion for the tray. For general graphs that question was taken up by Daniel Kornhauser, Gary Miller and Paul Spirakis in 1984, who showed that when an arrangement is reachable it is reachable in a number of moves bounded by a constant times the cube of the number of vertices, and that bound cannot be improved in general.

The parity, relocated #

Seen from here, the whole sequence of results about sliding puzzles has a different shape. The sign of a permutation is the only bit a permutation can carry into a commutative target. The half-solvable tray looked like an application of that bit. Wilson’s theorem shows it is really an application of a different bit — the colour of a vertex in a two-coloured graph — which happens to be locked to the sign by the fact that every move is a transposition that crosses one edge.

When the graph cannot be two-coloured, the colour bit does not exist, the lock has nothing to engage, and the sign is free to take both values. The index-two subgroup that cuts the tray’s arrangements into two blocks is still there as a subgroup of the permutations; it is simply no longer the subgroup the moves generate.

There is a small practical moral in this for anyone who designs puzzles. A sliding puzzle on a grid with one diagonal link added — any link that closes a triangle, provided the board stays free of cut vertices — has no impossible arrangements at all. The square grid is what makes the famous swindle possible: the half that cannot be solved exists only because the board can be coloured like a chessboard.

Still open: several empty vertices and the shortest route #

The classification with one empty vertex is complete. With several it is settled too — Kornhauser, Miller and Spirakis handled any number of empty vertices on any graph — and extra holes only loosen the constraints, since a second empty vertex gives the tokens room that an odd cycle was needed to provide.

What is not settled is the cost. Deciding whether an arrangement is reachable is fast on every graph, by the theorem and its extensions. Finding the fewest slides that reach it is NP-hard already on grids, by the result of Daniel Ratner and Manfred Warmuth, and on general graphs nothing better than exhaustive search is known for exact answers. The worst case over all arrangements — the far end that is thirty-one on the eight-puzzle — is not known as a function of the graph for any family beyond the simplest, and whether it is governed by any quantity as clean as bipartiteness is an open question. Even the diameter of the tray’s own move graph, seen in the map of a group drawn from its generators, is known exactly only for trays small enough to search, and the reachability theorem, sharp as it is, gives no hint of it.