how to find that 8 number puzzle is solvable or not?

Question

I'm working on 8 number puzzle, where 8 numbers are randomly generated and placed in 9 cell board. One cell at bottom right corner is kept empty where we can swap with adjacent (top-bottom-left-right) cells if any available.

The puzzle can be solved if all numbers are arranged in sequence starting from top left cell.

Now after some trials, I found that some arrangements of (randomly generated) numbers in starting of the game are not solvable.

I think, after generating random numbers, we can find mathematically that random numbers can be solved after placing on board or not.

Can anybody help to find the solution/algorithm/mathematical formula to determine that numbers can be solvable or not?

Answer 1

This article has an extensive discussion of the solution:

http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

The summary for the 3x3 board is:

Lay out the board as a 9x1 row (row 1, then row 2, then row 3). Count the number of inversions (instances of a higher number coming before a lower number on this row). The board is solvable if and only if the number of inversions is even.

For example,

8   1   3
2       5
7   6   4

Written as a row is:

8, 1, 3, 2, , 5, 7, 6, 4

The 8 gives 7 inversions, the 1 gives none, the 3 gives 1 inversion, the 2 gives none, the 5 gives 1, the 7 gives 2, and the 6 gives 1. This example has a total of 12 inversions, which is even, so it is solvable.