Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

According to this page: http://mathworld.wolfram.com/15Puzzle.html it says that

While odd permutations of the puzzle are impossible to solve

I've red this article: http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics) and, if I understand the formula given in it, specifically: $\text{inv}(A) = \# \{(A(i),A(j)) \mid i < j \text{ and } A(i) > A(j)\}$ I don't understand how this is true, if, given this example:

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

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

inversion i = 1 > j = 0, A(i) = 0 < A(j) = 4
inversion i = 2 > j = 0, A(i) = 2 < A(j) = 4
inversion i = 3 > j = 0, A(i) = 3 < A(j) = 4
inversion i = 5 > j = 0, A(i) = 1 < A(j) = 4
inversion i = 5 > j = 2, A(i) = 1 < A(j) = 2
inversion i = 5 > j = 3, A(i) = 1 < A(j) = 3
inversion i = 5 > j = 4, A(i) = 1 < A(j) = 5

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

There is the total of 7 inversion (obviously, odd, and should be unsolvable, but it is solved above in 6 steps). Where did I go wrong at counting inversions?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

If you read the MathWorld article carefully, you’ll see that the actual statement is a little more complicated than the shorthand version that you quoted. If $N$ is the number of inversions in the initial permutation of the $15$ of the $15$ tiles, and $e$ is the row number of the initial location of the empty cell, a solution is possible if and only if $N+e$ is even.

However, this doesn’t resolve your question, because in your example $N=6$ and $e=1$, so $N+e=7$, which is odd.

The resolution lies in the definition of solvable: a position is solvable if you can reduce it to

$$\begin{array}{c} 1&2&3&4\\ 5&6&7&8\\ 9&10&11&12\\ 13&14&15&\square \end{array}$$

with the empty cell in the lower right. In fact that’s impossible with your configuration. If you made your final configuration the goal, your solvable positions would be exactly the ones that are unsolvable in the standard puzzle, and vice versa.

share|improve this answer
    
Oh, I see now, thank you! –  wvxvw May 18 '12 at 9:55

In the cited phrase about the 15 puzzle, it is assumed that the puzzle is handed to you with the empty square in the right lower place. It is this condition that ensures that the number of inversions has to be even because you can follow the movement of the empty square and see that you have to make an even number of moves.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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