Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

1,0,3,2,4,5,6,7,8

and

7,0,2,8,5,3,6,4,1

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

1 Answer 1

up vote 10 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 Utility.java 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

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.