CODEWITHSUNDEEP
algorithmsliding-tile-puzzle
Raveen Mobile
Raveen Mobile

Reputation: 59

Does 8 puzzle solvability rules work for any goal state?

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.

Upvotes: 1

Views: 2655

Answers (2)

user4668606
user4668606

Reputation:

Yes, it does work. There's a pretty trivial way of showing this. Just map the values in the solution to the values of let's say your GoalState2, for which the check works:

state we want to reach   Goal State2
3   1   5                1   2   3
6   4   8                4   5   6
2   0   7                7   8   0

map:
3 -> 1
1 -> 2
3 -> 5
...

Now apply this table to your start-state, by replacing each value with the one it's mapped to, solve the entire problem in the way you used to for GoalState2, and reverse the mapping for the final-state. And there you are with your desired result, if it exists. And the solvability-rule can be reused without changing a bit of it, just by using that simple remapping.

An illustration of how this works:

state we want to reach   Goal State2
3   1   5                1   2   3
6   4   8                4   5   6
2   0   7                7   8   0

build map

map:
3 -> 1
1 -> 2
3 -> 5
...

Start state
3   1   5   apply map  1  2  3  solve for  1  2  3  apply        3  1  5
6   0   4   -------->  4  8  5  -------->  4  5  6  --------->   6  4  8
2   7   8              7  0  6   GoalS2    7  8  0  reverse map  2  0  7

That's the most trivial way of solving it. Just consider the numbers as labels without any meaning and you're already halve way done.

For a more complex answer that gives you a better understanding of the rule itself, take a look at @trincots answer.

Upvotes: 1

trincot
trincot

Reputation: 350232

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>

Upvotes: 2

Related Questions