8 Puzzle solvable or not

Sometimes the configuration given in the input to the 8 puzzle solver might not be solvable. In order to check that whether the given input is solvable or not we have to count the number of “inversions”.

What is inversion?

A pair of tiles form an inversion if the values on tiles are in reverse order of their appearance in goal state.

Following is simple rule to check if an 8 puzzle is solvable.

It is not possible to solve an instance of 8 puzzle if number of inversions is odd in the input state.

In the examples given in above figure, the first example has 10 inversions, therefore solvable. The second example has 11 inversions, therefore unsolvable.

If the 8 puzzle solver produces the output in ascending order then,
# of inversions = # of pairs of tiles in descending order.
For example,

Puzzle:

1  2  3

4  0  5

8  6  7

Goal State:

0  1  2

3  4  5

6  7  8

inversions are : (8, 6) and (8, 7)
and the puzzle is solvable because the number of inversions = 2 i.e. an even number.

If the 8 puzzle solver produces the output in descending order then,

# of inversions = # of pairs of tiles in ascending order.
For example,


Puzzle:

7  3  6

0  1  5

4  8  2

Goal State:

8  7   6
5  4   3

3  1   0

inversions are : (7,8), (3,6), (3,5), (3,4), (3,8), (6,8), (5,8)

and the puzzle is unsolvable because the number of inversions = 7 i.e. an odd number.