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: 270
puzzle
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