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?

  • \$\begingroup\$ Try solving 1,0,3,2 \$\endgroup\$
    – badp
    Commented Oct 20, 2012 at 12:58

1 Answer 1


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.

  • \$\begingroup\$ Yes you are right! I went through the source code of Utility.java in the site with the applet. They have not counted zero as you mentioned. That is where I was wrong. Thanks. \$\endgroup\$
    – Ashwin
    Commented Oct 20, 2012 at 4:54
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Oct 20, 2012 at 10:22
  • \$\begingroup\$ 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... \$\endgroup\$
    – arun
    Commented Jul 17, 2015 at 3:30
  • \$\begingroup\$ Nvm, that board is indeed solvable and it takes 22 moves to do it! \$\endgroup\$
    – arun
    Commented Jul 17, 2015 at 3:39

You must log in to answer this question.

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