A second empty square

A sliding puzzle sold with two tiles exchanged cannot be solved, and the proof is a single quantity that no slide changes: the sign of the arrangement, read as a permutation of the tiles and the blank together, multiplied by the colour of the square the blank sits on. Every slide exchanges the blank with one tile, which flips the sign, and carries the blank to a square of the other colour, which flips the colour. The product survives every move, so the trays split into two halves that never meet, and Richard Wilson’s theorem says that on any board that can be coloured like a chessboard the split is exactly in two.

That argument has a hidden requirement, and it is the subject of this essay. It needs the blank to be a single object with a name — something a permutation can move about and count transpositions of. Take one more tile out of the tray and leave two squares empty. Now there are two blanks, and they are interchangeable: nothing distinguishes the hole on the left from the hole on the right. The question of what the second hole buys has two halves. The first is about reachability, and its answer is that the barrier disappears completely. The second is about distance — how much nearer to solved every arrangement becomes — and its answer is the figure above, found by searching every arrangement of three small trays with every possible number of holes.

What a move is when there are two holes #

The rules do not change. A move slides one tile into an adjacent empty square; tiles never pass through each other and never leave the tray. Solved means tile 1 on the first square, tile 2 on the second, and so on in reading order, with the holes occupying the last squares. With one hole the three-by-three tray carries tiles 1 to 8 and the solved arrangement has the blank in the bottom right corner. With two holes it carries tiles 1 to 7 and the bottom row reads 7, then two empty squares.

What does change is the number of moves available. With one hole a position offers two, three or four moves, according to whether the blank is in a corner, on an edge or in the middle. With two holes there are up to eight — every tile next to either hole can slide into it — and when the holes are next to each other neither can move into the other, since nothing moves into a hole except a tile. A position with more moves available is nearer, on the whole, to every other position, and the question is how much nearer.

The count of arrangements changes too. With one hole there are $9! = 362{,}880$ ways to lay eight distinct tiles and one blank into nine squares. With two holes the two blanks are the same, so the arrangements number $9!/2! = 181{,}440$ — exactly the number that one hole could reach. With three holes there are $9!/3! = 60{,}480$, and in general $9!/k!$ for $k$ holes, down to nine positions for a single tile alone in the tray. Every one of these spaces is small enough to visit completely, by the method the search for the far end used on the eight-puzzle: start from solved, find every arrangement one move away, then every arrangement one move beyond those, and continue until nothing new appears. The search records each arrangement’s distance the first time it is reached, and that distance is the fewest moves that solve it.

The barrier is gone #

The searches answer the reachability question at once. With one hole the three-by-three search stops after visiting 181,440 arrangements, half of the 362,880, exactly as the sign predicts. With two holes it stops after visiting 181,440 arrangements, which is all of them. The same happens on every tray searched: one hole reaches half, two or more reach everything.

The reason is visible in the smallest move that one hole cannot make. Take the solved tray with two holes and exchange tiles 5 and 6, leaving everything else at home. With one hole that arrangement — two tiles exchanged, the blank home — is the classic unsolvable puzzle, the one Sam Loyd offered a prize for knowing that it was safe. With two holes it is four moves from solved.

The four moves walk two tiles round the two-by-two block in the bottom right corner. Tile 6 drops into the hole below it, tile 5 slides left into the square tile 6 vacated, tile 6 slides right into the corner, and tile 6 rises into the square tile 5 left. The block holds two tiles and two holes, and the tiles have each gone part of the way round it; the holes have done the rest. With one hole the same block holds three tiles and a blank, and sending them round it is a cycle of three tiles — an even permutation, which is why that cycle is the workhorse of every one-hole solving method and why no combination of such cycles exchanges just two tiles.

With two holes the bookkeeping that made this impossible falls apart, and the place it falls apart is precise. To speak of the sign of an arrangement, every object in the tray has to be a definite thing that a permutation moves from one square to another. With two identical holes, an arrangement does not determine a permutation: the two holes could be labelled either way round, and the two labellings differ by one transposition, so they have opposite signs. The quantity that was conserved is no longer defined, and a quantity that is not defined cannot block anything.

Why the exchange of two equal things has no sign #

This is the same fact that makes a determinant vanish when two of its rows are equal, and the parallel is worth making exact. The determinant is the one function of the rows that changes sign whenever two rows are exchanged. If two rows are equal, exchanging them changes nothing, so the determinant must equal its own negative, and the only number with that property is nought. The sign of a permutation and the sign of a determinant are the same sign — the determinant is a sum over permutations, each weighted by it — and both stop carrying information as soon as two of the things being permuted cannot be told apart.

In the tray the consequence is not that the sign becomes nought; it is that it stops being a property of the arrangement at all. With one hole, the sign was the only bit a sequence of moves could not change, and the crossings of the strings that draw a rearrangement were the way to compute it. With two indistinguishable holes the strings for the holes can be drawn crossed or uncrossed at will, the crossing count can be made odd or even by choice, and nothing about the arrangement decides which.

Wilson’s theorem was stated for one empty vertex, and the extension to several was made in 1984 by Daniel Kornhauser, Gary Miller and Paul Spirakis, who showed how to decide reachability for any number of empty vertices on any graph and that every reachable arrangement can be reached in a number of moves bounded by a polynomial in the number of vertices. On the tray their answer reduces to what the searches found: one hole, half; more than one, everything. The searches add the part their theorem does not state — the exact distances.

How far the far end comes in #

The hero answers the distance question for every tray and every number of holes. On the three-by-three tray the farthest arrangement is 31 moves out with one hole, 24 with two, then 21, 17, 13, 10, 7 and 4 as further tiles are lifted out. With eight holes there is one tile, and the far end is the four moves that carry it from the bottom right corner to the top left. With seven holes there are two tiles, and the far end is seven moves.

The largest single drop is the first. The second hole takes seven moves off the far end of the three-by-three tray, and every hole after it takes three or four. On the two-by-four tray the first extra hole takes ten moves off — 36 down to 26 — and on the two-by-three tray nine, from 21 to 12. Each later hole removes a smaller amount. A hole is worth most when the tray is most crowded, which is when a tile wanting to cross the tray must first persuade every other tile in its way to step aside, and the one blank can only be in one place at a time.

The averages fall in step. Over all reachable arrangements of the three-by-three tray the average distance is 21.97 with one hole, 16.04 with two, 12.70 with three, then 9.99, 7.88, 5.92, 3.75 and 2.00. The ratio of far end to average stays between 1.4 and 2 the whole way down, so the far end and the typical case shrink together; the next figure shows how the whole distribution moves.

Adding a hole slides the whole distribution to the left. The one-hole curve rises from almost nothing at ten moves to a peak at twenty-four and dies at thirty-one; the two-hole curve peaks at sixteen and dies at twenty-four; the three-hole curve peaks at fourteen. An extra hole does not merely trim the hardest arrangements and leave the rest alone. Almost every arrangement is brought nearer, and at the first extra hole the average moves by six.

All three curves obey the parity law that the one-hole search found as a law about distance. Every move carries exactly one hole one square, so the sum of the holes’ row and column numbers changes by one at every move, and an arrangement’s distance from solved is odd or even according to where its holes sit. Arrangements at odd and even distances are therefore drawn from different pools, which is why neighbouring points on each curve can differ by more than the curve’s smooth shape suggests. The law outlives the sign: with two holes the permutation has no parity left, but the holes’ positions still do.

What one tile was costing #

The cleanest way to see what a second hole is worth to a particular arrangement is to take a one-hole arrangement and lift out tile 8, leaving its square empty. The result is a two-hole arrangement with the same tiles 1 to 7 in the same places, and its distance from solved can be compared with the original’s. Lifting out a tile can never make the puzzle harder: any sequence of moves that solves the original still solves the copy, since every slide of tile 8 can simply be skipped and every other slide is still legal. So the saving is never negative, and the search measures it exactly for all 181,440 arrangements.

The savings run from nought to sixteen moves and average 5.94. Only 210 arrangements gain nothing — for them, some shortest solution with tile 8 in place is already as short as the best solution without it. Ten arrangements gain sixteen. The example drawn is twenty-three moves from solved with tile 8 in place and seven without it: tile 8 sits in the way of almost everything, and with it gone the remaining tiles need only a short rearrangement. The two arrangements at the far end of the one-hole tray fall to twenty-two and twenty-three moves — still near the two-hole far end of twenty-four, but no longer at it.

What the histogram shows is that the second hole is not a uniform discount. The savings spread across most of the range the distances themselves cover, so a large part of a one-hole arrangement’s difficulty can be the cost of one particular tile being in the way. Tile 8 was chosen because lifting it out leaves the holes on the last two squares, where the two-hole puzzle’s solved arrangement wants them; lifting out a different tile would pose a different puzzle with its holes elsewhere, and the comparison would need a different solved arrangement to measure against.

Where the far end lies #

With one hole the farthest arrangements of the three-by-three tray are two, and their shape was a puzzle: not a simple reversal, not a rotation of the solved tray, and with a taxicab bound well short of thirty-one. With more holes the far end is easier to read.

With three holes there are exactly three farthest arrangements, twenty-one moves out, and all three put the first row of the solved tray — tiles 1, 2 and 3 — along the bottom row, reversed. The other three tiles sit in the top two rows in some reversed order with the holes among them. The pattern is close to the obvious guess, which is to carry everything as far from home as it can go: tile 1 to the bottom right corner, the farthest square from its own, and tile 3 to the bottom left. The holes, which have no homes, end up wherever the tiles leave room.

With two holes the far end holds seventy-seven arrangements, twenty-four moves out, and they are more varied. Thirty-six of them still carry 3, 2, 1 along the bottom row and forty-one do not, and the count of seventy-seven is itself informative: a far end made of many arrangements is a far end reached by many routes, where with one hole the two arrangements at thirty-one are the end of a narrow channel. A tray with more freedom has a broader horizon.

Every tray, every number of holes #

The three trays together make twenty searches, one for each combination of tray and number of holes, and the table below is their whole record.

Two patterns run through it. The first is that the far end falls by smaller amounts as holes are added, until it reaches the bare geometry of the tray: with a single tile left, the far end is that tile’s taxicab trip across the tray, three moves on the two-by-three, four on the two-by-four and four on the three-by-three, and with two tiles left it is five, six and seven. The second is that the two-by-four tray, which has fewer squares than the three-by-three, has the more distant far end with one hole and with two, and loses that lead at three holes. A long thin tray makes tiles queue: with one hole, every tile that needs to cross from one end of a two-row tray to the other must wait while the tiles between rotate through the only gap. A second hole relieves the queue more than a square tray needs relieving.

None of this follows from a formula. The far ends of these trays are known because every arrangement was visited, and the searches are complete — every number in the table is the exact answer for its tray. For the four-by-four tray with one hole the far end is 80 moves, established by computer search in 1999 and confirmed in 2005 by a complete breadth-first search of all 10,461,394,944,000 of its reachable arrangements. Nothing comparable has been computed here for the four-by-four tray with two holes, which has $16!/2$ arrangements, the same number as the fifteen-puzzle itself.

Exact numbers without a reason #

The searches give numbers, not reasons. The sequence 31, 24, 21, 17, 13, 10, 7, 4 is exact and has no explanation here beyond the observation that an extra hole is worth most when the tray is crowded. Whether the far end of an $n \times n$ tray with $k$ holes follows any expression in $n$ and $k$ is not something three small trays can say, and the two-by-four tray’s overtaking shows that the shape of the tray matters as much as its size.

The holes are interchangeable, and the conclusions depend on it. If the two empty squares were distinguishable — two blanks of different colours, each required to end on its own square — the sign would be defined again, since every object would have a name, and the half-and-half split would return in a modified form. The disappearance of the barrier is a fact about identical holes, not about extra room.

Distance is in moves of one tile by one square. Some puzzles count a slide of a whole row of tiles as one move, and in that measure the far ends are smaller and the gains from extra holes are different. The figures here count the slowest possible way and say nothing about the other measure.

The picture of the four-move exchange shows one exchange. Some pairs of tiles are much harder to exchange: with two holes, swapping tiles 1 and 6 and putting everything else back takes eighteen moves, because the two tiles start at opposite corners of a long route and the holes begin far from both. That the exchange is possible at all is the theorem; how long it takes depends on where the two tiles and the two holes are.

A transposition is a cycle with a hole in it #

The four-move exchange is the whole of the story in miniature. Running two tiles round a block of four squares with two holes in it is, for the tiles, a single exchange — and for the squares it is a rotation that the holes absorb. With one hole the same rotation is a cycle of three tiles, which is even. The second hole turns the cycle of three into an exchange of two by standing in for the third tile, and it can stand in because it has no identity of its own to keep track of.

That is also why the search finds every arrangement. Once one exchange of two adjacent tiles can be made with everything else put back, every exchange can — move the pair to be exchanged into the block, exchange them, move everything back — and exchanges of pairs generate every permutation, the fact from which the subject begins. So the half that was missing comes back in full, and the map of the tray’s states becomes one connected piece where with one hole it was two.

Still open: room that is not empty #

The general question this leaves is about trade-offs. A second hole takes a tile out of the puzzle and makes the rest easier in two ways at once: the barrier vanishes and the distances fall. Neither effect has a formula for the $n \times n$ tray, and the worst case with one hole is known only to grow like $n^3$, with constants that are not known; how the exponent and the constants change with a fixed number of extra holes, or with holes making up a fixed fraction of the tray, is open.

There is also a family of puzzles between one hole and two. A tray in which two tiles are identical — two tiles both marked 7, say — has the same lost sign as a tray with two holes, for the same reason, and every arrangement becomes reachable while the tray stays as crowded as it was. How far the far end comes in when the only change is that two tiles stop being distinguishable, with no room added at all, separates the two effects this essay has measured together: how much of the second hole’s benefit is room, and how much is the sign simply ceasing to exist. The ball of positions within a given number of moves grows at a rate set by both, and nobody has measured the two separately.