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?