How to check if Sliding puzzle is solvable?
Hello, I am developing a small work where I need through the algorithm a * solve a puzzle, more precisely this puzzle:
Basically consists of sliding the pieces into the blank in order to leave 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 the same is solvable, I've researched but I can't understand why counting inversions guarantees this, and what these inversions are.
The part where I'm going to check this 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 modulo by 2, in case to find out if the result it is odd or even, so I have already added to the code.
The configuration of the game grid is a array containing the sequence of number.
Ex.
[5, 3, 2, 1, 4, 6, 8, 7, ""]
1 answers
The determining formula for checking solvability is referring to the parity of a permutation or in English Parity of a permutation.
Which briefly calculates the amount of inversions required 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 if it is solvable or not.
2|8|3
-+-+-
1|6|4
-+-+-
7| |5
Writing form linear we will have: 2,8,3,1,6,4,7,5 ignore the blanks.
Now we need to find the number of inversions by counting the numbers after each field that precede the analyzed number.
The sum of inversions determines whether it is solvable or not. Even inversions is solvable, odd not.
Following his 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 this case:
1|2|3
-+-+-
4|5|6
-+-+-
|8|7
Is not solvable because the inversion number is 1 (odd).
For 1,2,3,4,5,6 is unprecedented.
8 has 7 as precedent - 1 inversion.
7 has no precedent.