[Solved]: Why can the state space of the 15 puzzle be divided into two separate parts?

Problem Detail: 

I am trying to understand the proof here of why the state space in 15 puzzle is divided into two separate parts, but the explanation is complicated for me.

Could someone please explain it in simpler terms? I have been struggling with this for days :(

Asked By : Abramo K.

Answered By : Steven Stadnicki

Perhaps the simplest way to understand the proof is by the idea of a conserved quantity : find some quantity that can be derived from a configuration and show that every move preserves that quantity. A static version of the idea is found in the following old puzzle:

Remove the northeast and southwest corner squares from a standard 8x8 checkerboard. Can the remaining 62 squares be tiled using 31 dominos?

Here, the parity principle is simple: each domino takes up exactly one black and one white square on a checkerboard, so any shape that can be tiled by the dominos has to have exactly as many white squares as black. Since the 62-square shape has 32 squares of one color and 30 squares of the other, there's no way of tiling it.

The conservation principle for the 15-puzzle is a bit more complicated, but it's fairly close to this: it's also a parity principle. Let's number the blank square '16' for the time being and imagine it being filled in; then we can talk about the state of the puzzle as a permutation of the numbers (1...16). Now, given an arbitrary permutation of the numbers (1...$n$), we can count how many pairs of numbers we have to swap to return all the numbers to their 'original place'. There are many different possible sets of swaps that can be made - for instance, if you have the permutation (3, 2, 1) you can get back to (1, 2, 3) by either swapping the first and third positions (3 with 1) or by swapping the first and second positions (3 with 2), then the second and third positions (3 with 1), then the first and second positions (1 with 2). (The minimum number of swaps that need to be made is called the number of inversions of the permutation, and it's an interesting quantity in its own right, but that's not important here). However you swap numbers around, though, the total number of swaps will either always be odd (like it is for (3, 2, 1)) or always be even; we call this number the parity of the permutation.

Now, going back to the fifteen puzzle: every move is to swap the blank square (the one we've labeled as '16') with some other square, one unit away from the blank square's current position. This means that a swap always comes with a move of one square - so if you consider the quantity 'total number of swaps I have done' + 'moves the 16 is away from its home square', then this quantity will always be even. In particular, when the 16 is back at its home square (0 moves away) then the overall number of swaps that's been performed must be even. This means that the parity of the permutation of the numbers (1..16) corresponding to our resulting position is always even. But now imagine the position of the original puzzle where the 14 and 15 have exchanged places; the 16 is at home but there's been only one 'swap' made. Since this is an odd number of swaps rather then an even number, it can't possibly be reachable from the base configuration.

There's one more minor catch: this shows that there are at least two categories that 15-puzzle positions can fall into, but it doesn't show that there are only two. For that, a slightly more complicated result is needed: namely, that any even permutation can be decomposed as a product of what are known as 3-cycles (i.e. swaps $a\rightarrow b\rightarrow c\rightarrow a$). I won't try to prove this here, but the simplest proofs work algorithmically - similar to how bubble sort shows that every permutation can be generated by swapping only adjacent elements. With this result in hand, though, it's easy to get any even permutation: we can get an arbitrary 3-cycle by moving our three elements into positions 11, 12, and 15 on the puzzle (with the blank square in position 16, of course), and then moving the blank square Up, Left, Down, Right - you can convince yourself that this motion cycles the three elements. Once we've done this, we just undo the same motions that got the three elements into those positions, leaving the final positions of all the other elements unchanged from their starting positions. This way of getting an arbitrary 3-cycle, along with the theorem allowing any even permutation to be expressed in terms of 3 cycles, then gives a way of getting every reachable (i.e., corresponding to an even permutation) position.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10130