Why is this 8 puzzle unsolvable?
- by Ashwin
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?
