Many Tiles, One Space, Two Worlds

At Least Two Worlds

We begin with a list of $n+1$n + 1 distinct integers, constructed from the puzzle after moving the empty space to the lower-right corner. Since we treat the empty space as tile $n+1$n + 1, the final element of the list is $n+1$n + 1. Running Bubble Sort produces the ascending sequence $1,2,\dots ,n+1$1, 2, ..., n + 1.

Bubble Sort repeatedly scans the list, inspecting neighboring pairs of elements. Consider such a pair, $A$A and $B$B, where $A$A appears before $B$B. The algorithm swaps them if and only if $A>B$A > B. It stops when a complete pass makes no swaps.

Now pick any two elements, $X$X and $Y$Y, from the original list, not necessarily neighbors. By Bubble Sort’s rule, $X$X and $Y$Y can cross each other in the list only when they become neighbors who are in the wrong order relative to each other. Once they cross, they are in the correct relative order; Bubble Sort will therefore never swap them again. Thus, any two elements can cross at most once.

Since Bubble Sort finishes with the entire list in ascending order, $X$X and $Y$Y must end in the correct relative order. If they never cross, their relative order never changes; it must have been correct from the start. Conversely, if they cross once, their relative order reverses; it must have been wrong from the start.

Now return to a moment when Bubble Sort is inspecting neighboring elements $A$A and $B$B. Pick any two other elements in the list, $X$X and $Y$Y. If Bubble Sort swaps $A$A and $B$B, the relative order of $X$X and $Y$Y remains unchanged, since neither element moves.

Furthermore, because $A$A and $B$B are neighbors, $X$X must appear either before both of them or after both of them. Therefore, swapping $A$A and $B$B cannot change the relative order of $X$X and $A$A, or of $X$X and $B$B. The same reasoning applies to $Y$Y. Thus, swapping $A$A and $B$B changes only their relative order, leaving the relative order of every other pair unchanged.

Putting this together, Bubble Sort swaps a given pair of elements exactly once if and only if they were in the wrong relative order in the original list. Each swap corrects that pair’s relative order without affecting the relative order of any other pair.

Let’s call the number of element pairs in the wrong relative order in the original list $K$K. Every one of these pairs is swapped exactly once, and no other pairs are swapped. Therefore, the total number of swaps performed by Bubble Sort is exactly $K$K.

Now consider $A$A and $B$B as they appeared in the original list, not necessarily as neighbors. What happens to $K$K if we swap them before running Bubble Sort?

First, pick any two other elements, $X$X and $Y$Y. Swapping $A$A and $B$B cannot change the relative order of $X$X and $Y$Y, since neither moves. Next, consider $X$X in relation to $A$A and $B$B. If $X$X appears before both or after both, its relative order with either element remains unchanged. However, if $X$X appears between $A$A and $B$B, swapping them places $A$A on the opposite side of $X$X; the relative order of $X$X and $A$A is reversed. The swap also places $B$B on the opposite side of $X$X; the relative order of $X$X and $B$B is reversed.

If both of these pairs were originally in the correct order, they become incorrect, increasing $K$K by $2$2. If both were incorrect, they become correct, decreasing $K$K by $2$2. If one was correct and the other incorrect, they exchange their statuses, leaving $K$K unchanged.

Therefore, every element between $A$A and $B$B changes $K$K by either $-2$-2, $0$0, or $+2$+2, while elements outside that interval have no effect. Finally, $A$A and $B$B reverse their relative order, changing $K$K by either $-1$-1 or $+1$+1. Adding these changes together, swapping $A$A and $B$B must change $K$K by an odd number.

Returning to the $n$n-puzzle, we can construct the list and run Bubble Sort to compute $K$K. Each legal move exchanges the empty space, represented by $n+1$n + 1 in our list, with a numbered tile. Consequently, every legal move flips $K$K’s parity: an even count becomes odd, and an odd count becomes even.

But consider what happens when the empty space starts and finishes in the same position. Every move to the left must be balanced by a move to the right, and every move upward by a move downward. Therefore, returning the empty space to its starting position always requires an even number of moves.

Since each move flips $K$K’s parity, an even number of moves leaves its parity unchanged. Thus, whenever the empty space starts and finishes in the same position, $K$K must be either even in both configurations or odd in both.

Now recall our two examples. The solved puzzle has $K=0$K = 0 because its list is already sorted. Swapping tiles $n-1$n - 1 and $n$n creates exactly one incorrectly ordered pair, giving $K=1$K = 1. Since both configurations have the empty space in the same position but opposite parities, no legal sequence of moves can connect them.

Thus, at least two separate worlds exist, unreachable from one another.

At Most Two Worlds

Here’s an inefficient algorithm that can solve the 15-puzzle from any starting configuration... well, almost.

First, move the empty space to the lower-right corner. Now consider the following arrangement:

The letters represent positions on the board, not the numbers printed on the tiles. Starting from the empty space, we can follow a circuit through $\mathrm{A}$A, $\mathrm{B}$B, $\mathrm{C}$C, and so on, all the way to $\mathrm{O}$O, before returning to where we started.

If we move the empty space around the circuit, each numbered tile shifts one place in the opposite direction. The tile at $\mathrm{B}$B moves into $\mathrm{A}$A, the tile at $\mathrm{C}$C moves into $\mathrm{B}$B, and so on; the tile originally at $\mathrm{A}$A wraps around to $\mathrm{O}$O. We call this operation rotation. Moving the empty space around the circuit in the opposite direction reverses the rotation. In either case, the empty space returns to the lower-right corner.

Now consider just the 2×2 region in the lower-right corner:

Instead of following the entire circuit, move the empty space up, left, down, and right, returning it to its starting position. The maneuver rotates the three tiles without disturbing any others. Moving the empty space around the square in the opposite direction rotates those same three tiles in reverse.

Notice that $\mathrm{O}$O, $\mathrm{A}$A, and $\mathrm{B}$B are consecutive in the circular ordering of all the tiles, which skips the empty space between $\mathrm{O}$O and $\mathrm{A}$A.

Suppose we want to rotate any three consecutive tiles in the circular ordering. First, rotate the entire circuit until those three tiles occupy positions $\mathrm{O}$O, $\mathrm{A}$A, and $\mathrm{B}$B. Next, rotate those three tiles using our 2×2 maneuver. Finally, rotate the entire circuit back by the same number of positions in the opposite direction.

Because the two full-circuit rotations cancel for every other tile, we can rotate any three consecutive tiles in the circular ordering, in either direction, without changing the final positions of any other tiles. That is, if we label the tiles occupying three consecutive positions $\mathrm{X}$X, $\mathrm{Y}$Y, and $\mathrm{Z}$Z, we can perform either of these transformations:

Now we have everything we need to almost solve the puzzle.

First, rotate the entire circuit until tile 12 occupies position $\mathrm{A}$A.

Next, find tile 11, which belongs at position $\mathrm{B}$B. Using our three-tile maneuvers, move it toward $\mathrm{B}$B, one or two places at a time in the ordering $\mathrm{B}$B through $\mathrm{O}$O. We restrict the selected triples to these positions; each completed maneuver therefore returns tile 12 to $\mathrm{A}$A.

Continue in the same way, placing the correct tiles at $\mathrm{C}$C, $\mathrm{D}$D, $\mathrm{E}$E, and so on. Each time, select triples only from the positions that haven’t yet been completed. Previously placed tiles may move temporarily during the full-circuit rotations, but they return to their correct positions when the maneuver is complete.

If the required tile is at least two positions beyond its destination, rotate it with the two preceding tiles to move it back two positions. Repeat until it reaches its destination or the position immediately after it. In the latter case, rotate the tile at the destination, the required tile, and the following tile to move it back one final position. Since at least three unfinished positions remain, this final maneuver is always possible.

Eventually, we reach position $\mathrm{M}$M. With only $\mathrm{M}$M, $\mathrm{N}$N, and $\mathrm{O}$O remaining, we can rotate those three tiles until tile 13 occupies $\mathrm{M}$M.

That leaves just $\mathrm{N}$N and $\mathrm{O}$O, the positions of tiles 14 and 15.

Every other tile is now in its correct position, and the empty space is in the lower-right corner. There are only two possible outcomes: either the puzzle is solved, or tiles 14 and 15 are swapped.

Since every legal move can be reversed, any two starting configurations that lead to the same outcome can be transformed into one another. And since our algorithm has only two possible outcomes, the 15-puzzle can have at most two separate worlds.

But what about other grid sizes?

For rectangular grids with an even number of squares, at least one dimension must be even. When the number of rows is even, we can construct a circuit using the pattern described below. If only the number of columns is even, the same pattern works with the roles of rows and columns exchanged; the empty space and the goal arrangement stay in their original positions.

Starting from the empty space in the lower-right corner, move up one position. Snake left and right through the rows above the bottom row, working upward and leaving the leftmost column untouched. Because the number of rows is even, the number of rows above the bottom row is odd; the alternating passes therefore finish in the second column of the top row. Move one position left into the upper-left corner. Then follow the leftmost column downward and cross the bottom row to return to the empty space.

This circuit visits every position once before returning to its starting point. Furthermore, the three positions in the lower-right 2×2 region are consecutive in the circular ordering that skips the empty space, just as in our 15-puzzle example.

When we exchange the roles of rows and columns, the same construction works in the other direction. For example, a grid with three rows and four columns can use this circuit:

Here, $\mathrm{K}$K, $\mathrm{A}$A, and $\mathrm{B}$B are consecutive in the circular ordering of all the tiles, wrapping around from $\mathrm{K}$K to $\mathrm{A}$A. Our 2×2 maneuver can rotate the tiles occupying these three positions, and combining it with full-circuit rotations lets us perform the same operation on any three consecutive positions in that ordering.

We can therefore arrange the tiles one by one, leaving only two positions unresolved. Those final positions need not always correspond to the last two numbered tiles, but there are still only two possible outcomes.

For grids with an odd number of squares, such as the 3×3 grid of the 8-puzzle, we need a small adjustment. As we established earlier, returning the empty space to its starting position requires an even number of moves. A circuit that visits every position exactly once and returns to its starting point requires one move per position; therefore, a circuit must contain an even number of positions.

To compensate, we can leave one position outside the circuit. For the 8-puzzle, let’s omit the upper-right corner:

Here, the cross marks the excluded position. Starting from the empty space, we can follow $\mathrm{A}$A through $\mathrm{G}$G and return to the beginning, rotating the seven tiles along the way.

Before using this circuit to arrange the tiles, we need tile 3 in the excluded corner. If it is already there, we can proceed directly to the solving algorithm. Otherwise, rotate the circuit until tile 3 occupies position $\mathrm{C}$C. Then move the empty space up twice and left once, pushing tile 3 into the corner. Finally, return the empty space to the lower-right by following the circuit from $\mathrm{C}$C through $\mathrm{D}$D, $\mathrm{E}$E, $\mathrm{F}$F, and $\mathrm{G}$G.

The remaining maneuvers leave tile 3 untouched.

Look again at the lower-right 2×2 region:

Moving the empty space around this square rotates the tiles at $\mathrm{G}$G, $\mathrm{A}$A, and $\mathrm{B}$B, which are consecutive in our circular ordering.

We can therefore combine full-circuit rotations with this smaller rotation to rotate any three consecutive tiles in the circular ordering, leaving all others in their original positions when the maneuver finishes.

Using the same algorithm, we first rotate the entire circuit until tile 6 occupies position $\mathrm{A}$A. Then we place the correct tiles at $\mathrm{B}$B, $\mathrm{C}$C, $\mathrm{D}$D, and $\mathrm{E}$E, in that order, restoring previously placed tiles at the end of each maneuver.

That leaves $\mathrm{F}$F and $\mathrm{G}$G, the positions of tiles 7 and 8.

Once again, there are only two possible outcomes: the solved puzzle, or the solved puzzle with its final two numbered tiles swapped.

Now consider the 5×5 grid of the 24-puzzle:

Notice the pattern. Starting from the empty space, the circuit moves up and then left. It continues upward through the two rightmost columns, crossing between them after each upward move except the move into the top row. Because the height is odd, it arrives immediately to the left of the excluded upper-right corner. From there, it snakes leftward through the remaining columns, alternating downward and upward, while leaving the bottom row untouched. After the two rightmost columns, an odd number of columns remains; the alternating passes therefore finish by descending the leftmost column. The circuit then crosses the bottom row to return to the starting position.

We can extend this pattern to larger odd-by-odd grids by adding pairs of rows or columns. Every position except the upper-right corner belongs to the circuit. The lower-right 2×2 region always contains the first two numbered positions and the last numbered position along the circuit; these are consecutive in the circular ordering that skips the empty space.

We can also place the correct tile into the excluded corner using the same procedure as before. If it is already there, leave it untouched. Otherwise, rotate the circuit until that tile occupies the position immediately to the left of the corner. Move the empty space up the rightmost column, then left, pushing the tile into place. Return the empty space to the lower-right by following the remainder of the circuit, without disturbing the completed corner.

We can now use our familiar rotations to arrange the remaining tiles one by one, leaving only the final two positions unresolved.

Thus, regardless of whether the rectangular grid contains an even or odd number of squares, every starting configuration can be transformed into one of just two possible outcomes. By the same reversibility argument used for the 15-puzzle, there can be at most two worlds.

Our algorithm starts and ends with the empty space in the lower-right corner; so, the initial and final values of $K$K have the same parity. The two possible outcomes are the solved arrangement, where $K=0$K = 0, and that same arrangement with just two numbered tiles exchanged, where $K$K is odd. Therefore, an even starting value of $K$K must lead to the solution; an odd value must lead to the other outcome.

The route used to move the empty space to the lower-right corner does not matter. Reversing one route and following another gives a sequence that begins and ends with the empty space in that corner, so $K$K’s parity cannot change.

Exactly Two Worlds

Bubble Sort revealed that there must be at least two worlds. Our inefficient solving algorithm demonstrated that there can be at most two. Together, they prove that every $n$n-puzzle has exactly two worlds.

The two worlds are equally large. To see this, pair every configuration with the one obtained by swapping tiles 1 and 2. Since the swap does not disturb the empty space but does flip $K$K’s parity, the paired configurations cannot belong to the same world. Swapping the same two tiles again restores the original configuration; thus, this rule pairs every configuration in one world with exactly one configuration in the other.

Therefore, each world contains exactly $\frac{(n+1)!}{2}$(n + 1)! / 2 configurations.