Slider Puzzles, Part 3: Explaining Unreachable States

Total swaps required: 1

Swap: 11 <--> 10

Let's take a look at how it works. We've colored the puzzle like a chessboard, and now a few facts become clear. First, we see that moving any tile from a blue position to a white position requires an odd number of moves. The same is true when moving a tile from a white position to any blue position. Second, it is similarly clear that moving a tile from a blue position to another blue position can only be achieved in an even number of moves. Likewise, moving from a white position to a white position requires an even number of swaps. A mathematical explanation of this even/odd behaviour is that the system forms a bipartite graph, with tiles forced to slide between the two colored states only through states of a different color.

Next, let's think about the swaps that happen each time we slide a tile in the puzzle. Each move consists of swapping the blank with a neighbouring tile, but let's generalize and suppose that on any given slide we could swap any two tiles in the puzzle. It is then quite easy to count how many of these pair-wise swaps are required to unscramble each configuration. The text below the puzzle provides this information, giving both the number of swaps and the sequence in which they can be executed.

Now play with the puzzle and watch what happens to the number of swaps required as the blank moves around. Observe that whenever the blank is in a white position, an odd number of pairwise-swaps are required to unscramble the puzzle. Likewise, when the blank is at a blue location, an even number of pairwise-swaps is required. And that lies at the heart of why the puzzle cannot be unscrambled from the state with the 11 and 10 swapped. An odd number of moves cannot complete an even number of pairwise-swaps, and an even number of moves cannot resolve an odd number of pairwise-swaps.

The puzzle exhibits a form of parity, where each state can be labelled as having even or odd parity based on how many pairwise-swaps are required. The mechanics of the sliding tiles dictate what changes in parity can occur as the blank moves around, and as a result there are certain configurations that simply can't be reached without violating the rules of the game. As you might guess, half the possible configurations have odd parity, and half have even parity, which explains our observation in a previous blog post that only 12!/2 states are reachable.