Does 8 puzzle solvability rules work for any goal state?

Question

Ive learned that the solvability of a 8 puzzle can be checked via following certain rules. https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

http://ldc.usb.ve/~gpalma/ci2693sd08/puzzleFactible.txt.

My question is whether this solvability check applies only when the goal state (solution) is in correct ascending order? Example:

   Start state
    3   1   5 
    6   0   4 
    2   7   8

    Goal state1        Goal State2
    3   1   5           1   2   3
    6   4   8           4   5   6
    2   0   7           7   8   0

Now my obeservation is that, the solvability check would work if the goal state is Goal State2 in the example. But it would not work if the goal state is Goal state1.

Answer 1

The inversion count can be odd or even, and in short we can call a state even or odd. This is called a state's parity. If the start state is even, then it is solvable. In the referenced articles this does indeed mean that the target must be the one with the incremental order.

But since there are in fact two classes of states (based on parity) and you can only stay within one of those two classes by making legal moves -- i.e. the parity is invariable when you make legal moves -- this principle can be extended to any target state:

If the parity of the starting state is the same as the parity of the target state, then it is reachable (solvable).

In the example states you give, the starting state is odd, and also the first target state is odd. So they belong to the same class, and the one can be reached from the other.

Here is a simple implementation of the parity check in JavaScript. It works for even sized grids as well:

function parity(grid) {
    var inversions = 0;
    // take copy and remove blank (0) from it.
    var arr = grid.slice(0);
    arr.splice(arr.indexOf(0), 1);
    // perform sort and count swaps
    for (var i = 1; i < arr.length; i++) {
        for (var j = i - 1; j >= 0; j--) {
            if (arr[j] <= arr[j+1]) break;
            [arr[j+1], arr[j]] = [arr[j], arr[j+1]];
            inversions++;
        };
    }
    if (grid.length % 2 == 0) { // even grid width
        var size = Math.round(Math.sqrt(grid.length));
        var blankRow = Math.floor((grid.length - 1 - grid.indexOf(0)) / size);
        inversions += blankRow;
    }
    return inversions & 1; // only odd/even is needed as info
}

document.querySelector('button').onclick = function() {
    var res = '';
    var txt = document.querySelector('textarea');
    var grid = txt.value.trim().split(/[,\s]+/g).map(Number);
    var size = Math.round(Math.sqrt(grid.length));
    var res = size*size !== grid.length
            ? 'input is not a complete square matrix of data'
            : 'parity = ' + parity(grid);
    document.querySelector('pre').textContent = res;
}

Enter grid. 0 represents empty slot.<br>
<textarea rows=4>3   1   5 
6   0   4 
2   7   8
</textarea><button>Verify</button><br>
<pre></pre>