6
\$\begingroup\$

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?

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

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.

\$\endgroup\$
  • \$\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 Oct 20 '12 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\$ – Peter Taylor Oct 20 '12 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 Jul 17 '15 at 3:30
  • \$\begingroup\$ Nvm, that board is indeed solvable and it takes 22 moves to do it! \$\endgroup\$ – arun Jul 17 '15 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.