I have a 8-puzzle
1|2|3 -+-+- 4|5|6 -+-+- |8|7
How can be checked if the puzzle is solvable?
Wikipedia states that it is solvable, but does not prove it. Can anybody explain the prove?
|show 4 more comments|
If you ignore the gap and just look at the ordered sequence of numbers, any "horizontal" move leaves the sequence unchanged and any "vertical" move of the puzzle has the form $$(\ldots, x, y, z, \ldots)\to (\ldots, y, z, x, \ldots)$$ or vice versa. These are even permutations and therefore the group of possible permutations is a subgroup of $A_8$ (alternating group) and cannot be all of $S_8$ (full symmetric group). The situation in your post corresponds to an odd permutation of the target ordering and therefore is not solvable.