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?
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.
Though It's old question but I am trying to answer it.
There is a method to check whether the given state is solvable or not.
1|2|3 -+-+- 4|5|6 -+-+- |8|7
Write it in a linear way, 1,2,3,4,5,6,8,7 - Ignore the blank tile
Now find the number of inversion, by counting tiles precedes the another tile with lower number.
In our case, 1,2,3,4,5,6,7 is having 0 inversions, and 8 is having 1 inversion as it's preceding the number 7.
Total number of inversion is 1 (odd number) so the puzzle is insolvable.
Let's take another example,
5|2|8 -+-+- 4|1|7 -+-+- |3|6
5 precedes 1,2,3,4 - 4 inversions 2 precedes 1 - 1 inversion 8 precedes 1,3,4,6,7 - 5 inversions 4 precedes 1,3 - 2 inversions 1 precedes none - 0 inversions 7 precedes 3,4 - 2 inversions 3 precedes none - 0 inversions 6 precedes none - 0 inversions
total inversions 4+1+5+2+0+2+0+0 = 14 (Even Number) So this puzzle is solvable.
Here is a function which I have used in Flash Game to check whether the given puzzle is solvable or not
Visit http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html for detailed information.
Late answer, I know, but I'm expanding on Hagen von Eitzen's answer in a slightly more elementary way, if it's still of interest.
Short answer: This state is not solvable.
First note that every permutation can be represented as a graph of disjoint cycles (see cycle notation). In the usual way, then, we represent a game state as a permutation of the 8 non-blank tiles, flattened to row major order.
Now, we can show that the parity (oddness/evenness) of the number of cycles is invariant under the sliding of the tile. To see why, we only need to consider vertical moves, because horizontal moves preserve the permutation. Here, notice that exactly $3$ elements $x, y, z$ change position to $z, x, y$. We proceed by focusing on the predecessors of $x, y, z$ in their respective cycles. Now there are $3$ cases to consider:
Since parity is preserved in each case, it is always preserved. Hence you cannot get from a permutation with an odd number of cycles (like the one in the question) to one with an even number of cycles, by only sliding the blank tile.