Given an n x n array of sliding tiles with one missing, is it possible to rearrange them into any given arrangement?

From a physics point of view, the natural way to understand this would be to think about groups and symmetries (which are, like fundamentally important to physics).

The set of possible tile moves generates a "group" which acts on the space of different configurations of the board (to be precise, I guess we should talk about the group generated by the 3+3 possible ways to slide the row and column in which there is an empty piece).

This group has a subgroup which leaves the empty piece in the corner spot. You can see that this is a subgroup because the combination of two moves leaving the corner piece empty will be a third move leaving the corner piece empty.

Then you'd show that this subgroup has the property that all elements are the product of an even number of generators in the group.

Lastly, you'd notice that any one of the generating moves always flips the "parity" of the board. This means that any even number of generators preserves the parity, and thus the parity is an "invariant" of the subgroup which leaves the corner empty. Thus there is no way to move the tiles which leaves the corner empty and swaps only two tiles.

For a geometric picture of some of the group ideas I mentioned, think about the group generated by reflections in a plane through the origin. Just as in the puzzle, each generator flips the parity (this time it's the old-fashioned physics parity). But the product of two reflections is a rotation! In fact, we can get all rotations as the product of two reflections. Thus, as with the puzzle, parity is an invariant of the rotation group SO(3). Therefore it makes sense to have physics interactions with a preferred parity (and this happens in nature!)

/r/math Thread Parent