Why is this 8 puzzle unsolvable?

Posted by Ashwin on Game Development See other posts from Game Development or by Ashwin
Published on 2012-10-20T04:05:14Z Indexed on 2012/10/20 5:22 UTC
Read the original article Hit count: 238

Filed under:

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.
Inversion is defined as 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?

© Game Development or respective owner

Related posts about puzzle