How to check if the Sliding puzzle is solvable?

Question

How to check if the Sliding puzzle is solvable?

Navigation

#1 by (3 votes)

1

Hello, I'm developing a little work where I need to solve a puzzle, precisely this puzzle:

Itbasicallyconsistsofslidingthepiecestothewhitespaceinordertoleavetheminorder(orinthedesiredstate).

Example: link

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

The part where I'll 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 module by 2, in case to find out if the result is odd or even, so I already added it to the code.

The game grid setting is an array containing the sequence of numbers.

Ex.

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

algoritmo

asked by anonymous 02.10.2018 / 15:39

1 answer

How do I read an XML with HTML markup Error opening V10 engine - Can not execute runtime binding on a null reference

score 3 · Accepted Answer

The determining formula for checking for solvency refers to the Parity of a permutation or in English Parity of a permutation . Which briefly calculates the amount of inversions needed to sort a certain number sequence, determined by Possible the amount of even inversions and Impossible the amount of odd inversions.

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

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

Writing linearly 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 that precedes the number analyzed.

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

Following your example, going from house to 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). Puzzle Solved.

Already this case:

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

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

font