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

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?

• This probably fits in better over at math.stackexchange under game theory: math.stackexchange.com/questions/754827/… – Hao Ye Aug 10 '14 at 18:12
• The mathematics is studied using Permutation Groups. Essentially all boards can be solved to either the correct solution, or the pseudo-solution with the 7 and the 8 swapped. An algorithm to generate valid boards might start by applying 1,000s of swaps randomly to a board that is known to be valid. – Joshua Shane Liberman Aug 12 '14 at 23:40
• Or perhaps even better yet: the puzzling stack at puzzling.stackexchange.com – SQB Aug 15 '14 at 20:08

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.