Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
What is a $9$ puzzle? –  Michael Albanese Feb 3 '13 at 11:01
1  
It is a 15-puzzle with only 9 items. –  ceving Feb 3 '13 at 11:02
    
Ok it would be more precise to call it 8-puzzle. –  ceving Feb 3 '13 at 11:07
    
Where does Wikipedia claim this is solvable? –  Chris Eagle Feb 3 '13 at 11:17
1  
A careful read of the Wikipedia article shows that what they're claiming is that if it's solvable then no more than 31 single tile moves required. Before that it definitely says the $n$ puzzle is only solvable for even permutations. –  coffeemath Feb 3 '13 at 14:29
show 4 more comments

2 Answers 2

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.

share|improve this answer
    
Is it really a group? It's not relevant, but it would be great if you could elaborate on that. It doesn't look obvious to me. –  Karolis Juodelė Feb 3 '13 at 14:21
    
Can you give me a hint, where to find an explanation of odd and even permutations? I do not understand, why the shown move is even and why getting the target ordering is odd. –  ceving Feb 13 '13 at 14:00
add comment

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.

Problem State:

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

    public function checkSolvable(pList:Array):Boolean{
        trace("checkSolvable called with : " + pList);
        var inversions:Number = 0;

        for(var i:int=0;i<pList.length;i++){
            for(var j:int=i+1;j<pList.length;j++){
                if(pList[j]>pList[i]){
                    inversions++;
                }
            }
        }

        if(inversions%2 == 1){
            trace("It's Unsolvable");
            return false;
        }else{
            trace("It's Solvable");
            return true;
        }
    }

Visit http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html for detailed information.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.