http://people.cs.pitt.edu/~alanjawi/memo.txt

A test to determine impossibility for initial state to converge to
goal state has to do with counting `inversions.' Take the starting
state, and write out the numbers on the tiles from top-to-bottom,
left-to-right as a list (the blank assumed to be in the last
tile). You may assume that the board is represented by an array. If
the number of inversions is odd then the puzzle is solvable, otherwise
it is not.

How to count inversions?
We said a pair of numbers in an array is an inversion when they appear out
of order in the array. So assume that we have the following array {1, 2,
4, 3}, then the pair (4,3) is an inversion because 4>3 and 4 appears before
3. The array {3, 1, 2, 4} has two inversions (3,1) and (3,2), and {1, 2,
3, 4} has 0 inversions.
Therefore, counting number of inversions in an array boils down to a
simple algorithm as follows: 
for all i in the array a  
scan the array for all j:i-n 
if a[i]>a[j] number_of_inversion++;

Were n is the length of the array a.

Examples:
+--+--+--+
| 1| 8| 3| 
+--+--+--+
| 5| 6| 7|
+--+--+--+
| 2| 4|  |
+--+--+--+

has 6+1+2+2+2=13 inversions(odd), so it is solvable.
6 for (8,3), (8,5), (8,6), (8,7), (8,2), (8,4)
1 for (3,2)
2 for (5,2), (5,4)
2 for (6,2), (6,4)
and 2 for (7,2), (7,4).

+--+--+--+
| 8| 1| 3|
+--+--+--+
| 5| 6| 7|
+--+--+--+
| 2| 4|  |
+--+--+--+

has 7+1+2+2+2=14 inversions(even), so it is unsolvable.

+--+--+--+
| 1| 2| 3|
+--+--+--+
| 4| 5| 6|
+--+--+--+
| 8| 7|  |
+--+--+--+
has one inversion(odd), so it is solvable.

+--+--+--+		   +--+--+--+
| 1| 2| 3|			| 1| 2| 3|
+--+--+--+			  +--+--+--+
| 8|  | 4|  ==>  		  | 8| 4| 5|
+--+--+--+  			  +--+--+--+
| 7| 6| 5|				| 7| 6|  |
+--+--+--+				  +--+--+--+

the puzzle on the left has 4+2+1=7 inversions (odd), The goal state.
by moving the blank to the last tile, the puzzle(on the right) still has odd number of inversions (4+1=5 inversions).*see NOTE 1 below.

NOTE: 
1. any sliding move in the puzzle does not change the oddity (odd/even) of
the inversions. That is why the above algorithm works.
2. the blank is assumed to be in the last tile for this algorithm to work,
otherwise another slightly more complex algorithm do exist.


See also 
https://www.geeksforgeeks.org/check-instance-15-puzzle-solvable/
https://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/