In the funny story of this mind game, you can see "the 15-14 problem", which we say has no solution. In fact, in order to make possible this online game, I must give you only "good" positions. That's why I had to solve this problem: which are the puzzles with solution and which are not?

Of course, the mathematicians know the answer: the parity of the permutation (rearrangement) which represents the actual position is preserved during the moves.

For example, let's take the game with the size 2 by 2. You will see that only the positions from the left are possible:

Possible positions:

1 2 3

2 3 1

3 1 2

Impossible positions:

3 2 1

2 1 3

1 3 2

If we try to see the difference, we can notice that the first positions are (1, 2, 3), (2, 3, 1), and (3, 1, 2), the even permutations. The impossible ones are the odd permutations. But what does means even and odd permutations?

Let me tell you first what an inversion is. An inversion is a pair of numbers contained into the permutation, in which the bigger one is before the smaller one. For example, the permutation (2, 3, 1) has two inversions: (2, 1) and (3, 1). The number of the inversions gives us the parity. In this example, the parity is even. But there are permutations with an odd parity. For example (1, 3, 2) has only one inversion, (3, 2). The permutation (3, 2, 1) has three inversions (all of them). So, the impossible positions are corresponding to odd permutations.

Well, it is true, but we cannot generalize from the case 2x2 to the case 4x4, at least not yet. In the case 2x2 it's easy to see that every possible move leave unchanged the parity. But in the case 4x4, if we slide the tile horizontally, the permutation's parity is preserved. If we move the tile vertically, the parity is changed, because the tile jumps over other three tiles. That made three inversions, so, if the parity was even it becomes odd, if it was odd it becomes even.

Some demonstrations incorrectly generalize the case 2x2 to the rest, and the others are more complicated. I would like to show you a simple and nice demonstration.

The key is the tile's order we choose to associate the positions with the permutations.

Usually, we think at this order:

I will suggest an order like these shown next, and I will show you why:

We have the observation #1:

1. The order in which we choose the tiles to form the permutation respects the rule: every two consecutive tiles must be adjacent.

   But why? Let's color the tiles alternatively with black and white, like this:

   If we choose the tiles' order by the rule #1, every two consecutive cells have different colors. When we slide a tile, it moves from a black cell to a white one, or reverse. Because it changes the cell's color, there is an even number of tiles between the initial and the final positions of the tile. According to the order choosed by the rule #1, it jumps over an even number of tiles. This means the parity is preserved. We can conclude with the observation #2:

2. If we color alternately the cells, we can understand the rule #1.

Now, that's a rule valid for all the possible tables, at least of the size 2x2.

Sam Lloyd knew that the 15-14 problem had no solution, because the start position was an odd permutation, while the end position was even (they differs by an inversion).

Why the case 2x2 was solved by the usual order? Because in this special situation, the usual order is the same as that proposed by us (we doesn't count the empty cell).

We showed that a good position has to be even, in order to solve the puzzle. But are all the even positions good?

I will let this problem as your homework: are all the even permutations good positions (do they have solutions)?

I showed you the way to see whether or not some position has solution, because some programmers don't think at this or they shuffle the tiles by starting from the ordered position and doing some legally moves. This works, but is not so elegant.

Now, maybe you want to ask me why, at the funny story of this game, we had launch the same problem, but we claim it can be solved. The true is that it isn't exactly the same problem. Go here to solve the mystery!

1. Play online Sam Lloyd's "15" puzzle
2. The funny story of this game
3. Mathematical implications of this game
4. Some funny logical problems with the 15 game.