Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 am developing a 8 puzzle game. I went through the rules in this (see Detecting Unsolvable Puzzles) link, which tell you how to detect if an initial state is unsolvable. It says that if the number of inversions is odd, then the goal state cannot be reached and if even the goal state can be reached.

An inversion is defined as follows:

Given a board, an inversion is any pair of blocks i and j where i < j but i appears after j when considering the board in row-major order (row 0, followed by row 1, and so forth).

There is a 8-puzzle solver (applet) here. Choose 8-puzzle from the options.




As you can see both of them contain an even number of inversions. Still the program says that the puzzle is unsolvable. So is the Princeton link wrong?

share|improve this question
Try solving 1,0,3,2 – badp Oct 20 '12 at 12:58
up vote 11 down vote accepted

The sequence 1,0,3,2,4,5,6,7,8 only has one inversion:

 1. 3,2

1 is odd, therefore this configuration is unsolvable.

Similarly, in 7,0,2,8,5,3,6,4,1:

 1. 7,2 
 2. 7,5 
 3. 7,3 
 4. 7,6 
 5. 7,4 
 6. 7,1 
 7. 2,1 
 8. 8,5 
 9. 8,3 
 10. 8,6 
 11. 8,4 
 12. 8,1 
 13. 5,3 
 14. 5,4 
 15. 5,1 
 16. 3,1 
 17. 6,4
 18. 6,1    
 19. 4,1

Nineteen inversions is odd. Hence, unsolvable.

I think your mistake is that you're counting the "0" as if it was a tile, when you're working out the number of inversions. But if you check the instructions in the article you linked, it isn't considering the blank space at all.

share|improve this answer
Yes you are right! I went through the source code of in the site with the applet. They have not counted zero as you mentioned. That is where I was wrong. Thanks. – Ashwin Oct 20 '12 at 4:54
@Ashwin, to be more precise, their notation is dodgy. If you look at the goal state, the blank tile should be 9 rather than 0. – Peter Taylor Oct 20 '12 at 10:22
It appears like this board with 2 inversions cannot be solved: 2,1,3,4,5,6,8,7,0 with 0 being the blank tile, at least with my implementation of the A* approach as mentioned on the OP's post. The f value just keeps increasing... – arun Jul 17 '15 at 3:30
Nvm, that board is indeed solvable and it takes 22 moves to do it! – arun Jul 17 '15 at 3:39

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.