7
$\begingroup$

How do I proof that this 8 puzzle enter image description here cannot be solved if the final state is enter image description here ?

$\endgroup$
  • 2
    $\begingroup$ Do you know about parity of permutations? $\endgroup$ – Ankoganit May 25 '17 at 2:54
  • $\begingroup$ @Ankoganit no. Can you explain it to me? $\endgroup$ – Vivek Laikan May 25 '17 at 3:00
  • $\begingroup$ @VivekLaikan, I hope you understand now. check this gamedev.stackexchange.com/questions/40307/… for better understanding. $\endgroup$ – CR241 May 25 '17 at 4:13
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$ – Rubio May 28 '17 at 18:28
9
$\begingroup$

The standard way of determining the solvability of sliding-block puzzle is analysing the parity of the corresponding permutation. A permutation is simply a reordering of some things — the tiles, in this case. We can assign a notion of parity – i.e., evenness or oddness to every permutation.

To understand how this works, consider the following numbers: 1,2,3,4,5. Suppose we want to reorder it into some way, say we want to turn the order into 4,2,1,3,5. Of course, we could just take out the numbers and put them in the desired order, but let's say we have to do it in a sequence of a special kind of moves: let's say, in each move, we can take any two numbers and swap their positions. This kind of move is what is known as a transposition.

So how can we attain the final desired configuration? Pretty easy, you just swap 3 and 4 first, getting 1,2,4,3,5, and then swap 1 and 4, yielding 4,2,1,3,5.

As it turns out, every permutation on any number of objects can be achieved by performing a finite number of transpositions (try to prove it, or see theorem 1 here). Note that the number of moves required is not fixed for a given permutation; for example, if some permutation is achievable in 3 moves, we can just take two random objects and swap them twice, thus getting the same permutation in 5 moves. But it turns out that there is one thing about the number of moves that's fixed; it's the parity of that number. That is, if you can achieve a permutation via an odd number of swaps, you can never achieve it in an even number of swaps, and vice versa. Therefore we call a permutation even if the number of swaps necessary to attain it is even, and odd otherwise. (A proof can be found here.)

Now let's get back to the 8-puzzle at hand. We can look at the final state as a permutation of the tiles in the initial state. But the central slot doesn't have a tile, so let's imagine it is in fact a ghost tile, one that gets swapped with some adjacent tile in every move. Now note that the final state is an odd permutation of the initial state: one simply needs 1 swap (swapping A and B), which is an odd number. If we hope to attain the same permutation by the legal moves (i.e., swapping the ghost tile with an adjacent tile), that must again take an odd number of swaps.

Now mentally color the 3x3 grid black and white in a chessboard pattern. Every move switches the color of the slot the ghost tile is on, and at the final stage, it's the same color again. So there must have been an even number of moves. This contradicts the conclusion obtained in the preceding paragraph; therefore the puzzle must be unsolvable. $\blacksquare$

$\endgroup$
  • 2
    $\begingroup$ Fantastic! An explanation good enough for even me to understand. $\endgroup$ – Forklift May 25 '17 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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