Take the 2-minute tour ×
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. It's 100% free, no registration required.

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

1 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 (pairs of tiles that are out of order on this row compared to the board being in order). The board is solvable if and only if the number of inversions is even.

share|improve this answer

Your Answer

 
discard

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.