# Why can the state space of the 15 puzzle be divided into two separate parts?

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 :(

• Can you be more specific? Should one be looking at the "Theorem", or somewhere else? What exactly is confusing? If you can answer these questions, it makes it easier for someone to answer :) – Juho Feb 27 '13 at 2:32
• from the page ... "Assume the board of (the generalized) "Fifteen" consists of nxm squares. The graph of the puzzle is always bipartite, and, therefore, puz(Fifteen) has two connected components, one consisting of odd and another of even permutations." this is not really a proof, its just a sketch of a proof. it presumably 1st appeared in some paper, not sure which one. note there is a similar property of rubiks cubes where quarter twists of some of the cube edges lead to "impossible" [to solve] configurations – vzn Feb 27 '13 at 23:05
• aha wikipedia has the answer: "Johnson & Story (1879) used a parity argument to show that half of the starting positions for the n-puzzle are impossible to resolve, no matter how many moves are made. This is done by considering a function of the tile configuration that is invariant under any valid move, and then using this to partition the space of all possible labeled states into two equivalence classes of reachable and unreachable states." more on that pg – vzn Feb 27 '13 at 23:10

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.
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.