Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
This probably fits in better over at math.stackexchange under game theory:… – 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 – SQB Aug 15 '14 at 20:08
up vote 6 down vote accepted

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.

share|improve this answer

Your Answer


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.