3
$\begingroup$

Would it be possible to solve a sliding puzzle like this (x is the space)?:

1  3  2

4  5  x

I haven't been able to solve this and I don't even know if it's possible.

$\endgroup$
1
8
$\begingroup$

Solution:

no, it's not possible to get from the position you gave to the "solved" puzzle with $1,2,3,4,5$ in the right order and the gap at the bottom right. This can be proved in the same way as the original (famous) "14,15 puzzle".

It can be shown using some basic group theory, similar to the proof found here.

Each position of the puzzle can be interpreted as a permutation of $\{1,2,3,4,5,6\}$, with the blank square interpreted as $6$. Each move of the puzzle can then be interpreted as a transposition in the symmetric group $S_6$, swapping the blank square $6$ with one of the actual tiles. The position you gave is one transposition away from the solved position, but it could only be reached in an even number of $6$-swaps, since that blank square $6$ must end up in the same position, so it must have had an even number of up-down movements and an even number of left-right movements. But any combination of an even number of transpositions must be in the alternating group $A_6$, and therefore we can't reach a single transposition by such a combination.

$\endgroup$
6
$\begingroup$

If your goal is to get "1 2 3" on the first row and "4 5 x" on the second, the answer is no, it is not possible.

This is a smaller version of Sam Loyd's 14-15 puzzle. If you have a sliding puzzle with a single empty space, you can check if it's solvable based on parity -- the number of switches you would need to get to the solution. Specifically:

  • First, make moves so the empty tile is in the right place.
  • Now imagine you could magically choose two tiles to swap positions. How many swaps does it take to solve the puzzle?

If the number of swaps is even, the original puzzle is solvable. If the number of swaps is odd, the original puzzle is not solvable. (In other words, starting from a solved puzzle, no matter what moves you make you'll always be in the even case - there's no way to jump between the two cases just by sliding tiles around. You would have to cheat by taking the tiles out.)

In your example, there is exactly one swap needed to solve the puzzle. So it is not possible to solve by sliding.

$\endgroup$
2
  • $\begingroup$ Five seconds, Deus. Five. Seconds. :-) $\endgroup$ Jan 29 at 19:42
  • $\begingroup$ @Randal'Thor Ha! I thought about editing the phrasing some more... didn't realize it would be that close. $\endgroup$
    – Deusovi
    Jan 29 at 19:44

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.