2
$\begingroup$

So this is supposedly a very popular puzzle by Sam Loyd. (I don't want answerers to provide solutions directly from some website etc. I mean, an ingenious solution is more welcome please.)

enter image description here

Now, as you see all numbers are arranged in ascending order except the last two. The rule of the game is to move a numbered block which is adjacent to the blank space and create another blank place in its original position (I mean, you just shift the position of blank space around by sliding the numbers around) .

Now the question goes as, can you arrange all the numbers in the correct ascending order? (The final outcome would be just interchange the positions of $15$ and $14$).

I know of a solution using a very clever trick of invariance (the invariant seemed quite non-trivial to me ;-P). Can others here come up with some interesting solutions?

|cite|improve this question
$\endgroup$
  • $\begingroup$ So this is just a 15-puzzle? $\endgroup$ – ericw31415 Mar 30 '18 at 14:49
  • $\begingroup$ @ericw31415 I don't know if it's just a... but it seemed quite interesting and the mathematics behind it didn't seem just trivial to me ... $\endgroup$ – tatan Mar 30 '18 at 14:50
  • 1
    $\begingroup$ this puzzle is impossible to solve $\endgroup$ – Vasya Mar 30 '18 at 14:51
  • 2
    $\begingroup$ Every move swaps the blank space with an adjacent block. In the end the blank space must return to its original position, but this requires an even number of moves. Now consider the parity of the desired permutation. $\endgroup$ – Rahul Mar 30 '18 at 15:09
  • 2
    $\begingroup$ It's not just "a" 15-puzzle. It is "the" 15-puzzle. Very well known. Should read up on it. en.wikipedia.org/wiki/15_puzzle Upshot. All even permutations are solveable and all odd permutations are not. This is an odd permutation. $\endgroup$ – fleablood Mar 30 '18 at 15:09
5
$\begingroup$

This can be shown using some elementary abstract algebra.

In short, a puzzle configuration is not solvable if and only if it's an odd number of swaps away from the solved state, like the one in your image is (14 and 15 swapped = 1 swap). I used this fact a few years ago to quickly generate random configurations for a 15-puzzle app I used to have in the App Store.

Reference: http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/15puzzle.pdf

|cite|improve this answer
$\endgroup$

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.