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.

enter image description here enter image description here enter image description here

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

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

enter image description here enter image description here

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?

  • 3
    This probably fits in better over at math.stackexchange under game theory: math.stackexchange.com/questions/754827/…
    – Hao Ye
    Aug 10, 2014 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. Aug 12, 2014 at 23:40
  • Or perhaps even better yet: the puzzling stack at puzzling.stackexchange.com
    – SQB
    Aug 15, 2014 at 20:08

1 Answer 1


This article has an extensive discussion of the solution:


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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .