How to check if the Sliding puzzle is solvable?

Question

Hello, I am developing a small work where I need to solve a puzzle through algorithm A* more precisely this puzzle:

---

Basically it consists of sliding the pieces to the white space in order to keep them in order (or in the desired state).

Example: https://www.proprofs.com/games/puzzle/sliding/

But before starting the resolution, I need to check if it is solvable, I have researched but I can’t understand why the inversion count guarantees this, and what are these inversions.

The part where I’m gonna check this out is this:

function countInversions(array) {
    // Contar inversões
    // TODO
}

console.log(tiles);
return countInversions(tiles) % 2 == 0;

---

I saw that the result is acquired by counting the inversions and then capturing the module by 2, in case to find out if the result is odd or even, so I’ve already added to the code.

The game grid configuration is a array containing the sequence of numbers.

Ex.

[5, 3, 2, 1, 4, 6, 8, 7, ""]

Answer 1

The determining formula for verifying solvability is related to Parity of a permutation or in English Parity of a permutation.
Which briefly calculates the amount of inversions needed to order a certain numerical sequence, determined by Possible the amount of even inversions and Impossible the amount of odd inversions.

And there really is a way to check whether it’s solvable or not.

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

Writing in a linear way we will have: 2,8,3,1,6,4,7,5 ignore the blanks.

Now we need to find the number of inversions counting the numbers after each field preceding the analyzed number.

The sum of the inversions determines whether it is solvable or not. Even inversions are solvable, odd not.

Following your example, passing house by house:

2 tem como precedente 1 - 1 inversão.
8 tem como precedentes 3,1,6,4,7,5 - 6 inversões.
3 tem como precedente 1 - 1 inversão.
1 não tem precedentes - 0 inversões.
6 tem como precedentes 4,5 - 2 inversões.
4 não tem precedentes - 0 inversões.
7 não tem precedentes - 0 inversões.
5 não tem precedentes - 0 inversões.

Total inversions 1+6+1+2 = 10 (Even number). Solvable Puzzle.

Already that case:

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

It is not solvable because the inversion number is 1 (unique).
For 1,2,3,4,5,6 is unprecedented.
8 has 7 as precedent - 1 inversion.
7 has no precedent.

source