10
$\begingroup$

I'm not sure how to count permutations in the 15 puzzle. They say that an odd count means it's impossible but not sure how to count this puzzle. How do I count whether this is even or odd? If it is solvable how can I solve? The last two tiles always seems to be swapped in the wrong position no matter how much I slide it around. I've been keeping the moves to the bottom half, do I need to do a big permutation around the whole puzzle?

Here's my grid results

| 1  | 2  | 3  | 4  |
| 5  | 6  | 7  | 8  |
| 9  | 10 | 11 | 15 |
| 13 | 14 | 12 |    |

Here's what I'm referencing

http://www.math.ubc.ca/~cass/courses/m308-02b/projects/grant/fifteen.html

$\endgroup$
4
  • 3
    $\begingroup$ Try giving this a read $\endgroup$
    – Will
    Jan 20, 2016 at 13:12
  • 13
    $\begingroup$ The puzzle is solvable, if and only if the number of swaps that restore the board is even. Here a single swap 12<-->15 restores the board; hence your puzzle is unsolvable. $\endgroup$
    – Gamow
    Jan 20, 2016 at 13:44
  • 2
    $\begingroup$ @Gamow Though if this is actually a physical puzzle OP owns, it's more likely the variant they own simply intends the blank to be in the top row. I own a couple sliding puzzles designed that way. $\endgroup$
    – Will
    Jan 20, 2016 at 13:48
  • 1
    $\begingroup$ it's a puzzle from an ios app - so not a physical one. $\endgroup$ Jan 20, 2016 at 15:11

3 Answers 3

9
$\begingroup$

The puzzle is:

Unsolvable!

The steps to show that:

I will just focus on the bottom-right 2x3 rectangle.

| 10 | 11 | 15 |
| 14 | 12 | |

| 10 | 11 | 15 |
| | 14 | 12 |

| | 11 | 15 |
| 10 | 14 | 12 |

| 11 | 15 | |
| 10 | 14 | 12 |

| 11 | 15 | 12 |
| 10 | 14 | |

| 11 | 15 | 12 |
| 10 | | 14 |

| 11 | | 12 |
| 10 | 15 | 14 |

| | 11 | 12 |
| 10 | 15 | 14 |

| 10 | 11 | 12 |
| | 15 | 14 |

| 10 | 11 | 12 |
| 15 | 14 | |

Which gives this configuration:

| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 15 | 14 | |

This is the classic unsolvable position, so the original puzzle was unsolvable.

$\endgroup$
2
  • $\begingroup$ Actually, any single swap of 2 tiles makes the puzzle unsolvable. If [12] and [15] are swapped it has the same effect as when it is [14] and [15]. $\endgroup$
    – Florian F
    Jun 7, 2020 at 14:18
  • $\begingroup$ @FlorianF Thanks, I know that now that I'm more well-versed in the properties of permutations (and I believe it was pointed out by Gamow in the comments). But I think this makes it more explicit if you didn't know that beforehand, only assuming you know that that last position is unsolvable. $\endgroup$
    – boboquack
    Jun 7, 2020 at 23:47
9
$\begingroup$

For a 15 puzzle to be solvable it has to meet the following:

  1. If the grid width is odd, then the number of inversions in a solvable situation is even.
  2. If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
  3. If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

A piece is inverted when a bigger number is in front of any amount of smaller numbers.

Check this page for more information.

$\endgroup$
1
  • $\begingroup$ Hi, I asked a doubt based on this answer here. Please see if you can have a look. $\endgroup$
    – Mahesha999
    Feb 24, 2021 at 15:55
7
$\begingroup$

I had the same problem.
Eventually I realized that ...

I was putting the blank space on the wrong corner!
Instead of having the blank space on the right bottom corner it should be on the left top.
Then you would have this --
| | 1 | 2 | 3 |
| 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 |

(Convention for these puzzles is that the space goes in the bottom right, but I've certainly seen examples of puzzles designed for the space to be in the top left. --Rubio)

Hope I've helped!

$\endgroup$
4
  • 2
    $\begingroup$ Welcome to Puzzling.SE. This question already has an accepted answer (the green tick). $\endgroup$ Jul 19, 2018 at 21:47
  • 2
    $\begingroup$ Welcome to Puzzling.SE, as it appears, this answer has no issues. We welcome new answers, even if there is already an accepted answer, as long as they add more information, or answer in a different and significant way $\endgroup$ Aug 30, 2018 at 23:09
  • 5
    $\begingroup$ Unless there's something that actually tells you where the blank spot should be in the solved grid, distinguishing a 4x4 15-puzzle where the blank goes top-left from one where the blank goes bottom-right isn't really possible other than by attempting to solve it. The puzzle layouts are not interchangeable. If it's designed for a top-left-open solution, the puzzle cannot be solved as a bottom-right-open, and vice versa. This answer is not only correct, it explains why the OP found the puzzle unsolvable. $\endgroup$
    – Rubio
    Aug 30, 2018 at 23:11
  • $\begingroup$ @Rubio will every unsolvable 15 puzzle becomes solvable if we swap the position of blank spot? $\endgroup$
    – senseiwu
    Feb 21, 2021 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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