9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is a $9$ puzzle? $\endgroup$ – Michael Albanese Feb 3 '13 at 11:01
  • 1
    $\begingroup$ It is a 15-puzzle with only 9 items. $\endgroup$ – ceving Feb 3 '13 at 11:02
  • 2
    $\begingroup$ Ok it would be more precise to call it 8-puzzle. $\endgroup$ – ceving Feb 3 '13 at 11:07
  • $\begingroup$ Where does Wikipedia claim this is solvable? $\endgroup$ – Chris Eagle Feb 3 '13 at 11:17
  • 1
    $\begingroup$ 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. $\endgroup$ – coffeemath Feb 3 '13 at 14:29
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Isnt it if(pList[i]>pList[j]) after the two for loops? $\endgroup$ – rain_ Oct 30 '16 at 16:59
  • 1
    $\begingroup$ I know this isn't a programming question, but your Java function fails to strip out the blank tile and will therefore be inaccurate. $\endgroup$ – andydavies Mar 27 '17 at 15:20
  • $\begingroup$ Your answer is correct for the specific example in the question, and the other specific example you cite, but does not work in the general case (n-puzzle). I know the question itself is specific, but for people reading this, know that the Java function will only apply to odd-numbered grid widths. $\endgroup$ – andydavies Mar 27 '17 at 15:56
  • $\begingroup$ 7 precedes 3,6. $\endgroup$ – nguyen Sep 7 '17 at 13:12
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Karolis Juodelė Feb 3 '13 at 14:21
  • $\begingroup$ 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. $\endgroup$ – ceving Feb 13 '13 at 14:00
  • $\begingroup$ why can you ignore the gap? If the gap is between, say 1 and 2 with the sequence in order, it does appear obvious that the puzzle is solvable. $\endgroup$ – mathchai Dec 15 '15 at 3:37
  • $\begingroup$ *does not appear $\endgroup$ – mathchai Dec 15 '15 at 3:49
  • 1
    $\begingroup$ @ceving, check this out: puzzling.stackexchange.com/questions/52110/… $\endgroup$ – Henrikh Kantuni Sep 9 '18 at 3:02
1
$\begingroup$

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$ or $y, z, x$. The two cases are analogous- just reverse the arrows in the cycle- so we'll just deal with the $z, x, y$ case here. We proceed by focusing on the predecessors of $x, y, z$ in their respective cycles. Now there are $3$ cases to consider:

  • Same cycle: All elements are in the same cycle. In this case, exactly one cycle remains in the place of the old cycle, so the total number of cycles is preserved. See the image below for this case. Green circles represent predecessors, blue circles represent $x, y, z$. Dotted lines from blue to green denote a sequence of 0 or more elements, including the green i.e. the blue might equal the next green. Similar pictures for the other cases can be drawn.

Same Cycle Case

  • Two cycles: In this case, there is one cycle containing exactly $2$ elements, and one cycle containing $1$ element. Here, the swap generates $2$ new cycles in place of the old $2$ cycles. So again, the total number of cycles is preserved.

  • Three cycles: In this case, all three cycles merge into one cycle. So the total number of cycles decreases by $2$, preserving the parity of the total number of cycles.

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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