How to check if an instance of 8 puzzle is solvable? - GeeksforGeeks

How to check if an instance of 8 puzzle is solvable? - GeeksforGeeks
What is 8 puzzle?
Given a 3×3 board with 8 tiles (every tile has one number from 1 to 8) and one empty space. The objective is to place the numbers on tiles in order using the empty space. We can slide four adjacent (left, right, above and below) tiles into the empty space.

Following is simple rule to check if a 8 puzzle is solvable.
It is not possible to solve an instance of 8 puzzle if number of inversions is odd in the input state.

What is inversion?
A pair of tiles form an inversion if the the values on tiles are in reverse order of their appearance in goal state. For example, the following instance of 8 puzzle has two inversions, (8, 6) and (8, 7).

   1   2   3
   4   _   5
   8   6   7  

https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

fig 4 12  1 10 2 7 11 4 14 5   9 15 8 13 6 3

fig 5: Tiles written in a row 12 1  10  2  7 11 4 14 5     9 15 8 13 6 3

An inversion is when a tile precedes another tile with a lower number on it. The solution state has zero inversions. For example, if, in a 4 x 4 grid, number 12 is top left, then there will be 11 inversions from this tile, as numbers 1-11 come after it. To explain it another way, an inversion is a pair of tiles (a,b) such that a appears before b, but a>b. Count the number of inversions in the grid. For example, on the grid of fig.4:

• the 12 gives us 11 inversions
• the 1 gives us none

The formula says:

1. If the grid width is odd, then the number of inversions in a solvable situation is even.
2. If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
3. If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

Fact 1: For a grid of odd width, the polarity of the number of inversions is invariant. That means: all legal moves preserve the polarity of the number of inversions.
Example: consider the move below. The number of inversions on the left is 11, an odd number. By moving the 3 up, the 9 and the 8 both lose an inversion. So the result has 9 inversions, which is still odd.

11 inversions  7    1   2  5   9 8 3 6

goes to

9 inversions  7   1   2  5 3 9 8 6

Proof of fact 1:

• Moving a tile left or right does not change the number of inversions, and therefore doesn't change its polarity.

a) A row move doesn’t change the inversion count. See following example

   1   2   3    Row Move     1   2   3
   4   _   5   ---------->   _   4   5 
   8   6   7                 8   6   7
  Inversion count remains 2 after the move

• Moving a tile up or down does change the number of inversions. The tile moves past an even number of other tiles (which is the width of the board, minus 1). So the number of inversions changes by  ±1±1±1±1...±1, an even number of times. This is even.

b) A column move does one of the following three.
…..(i) Increases inversion count by 2. See following example.

         1   2   3   Column Move     1   _   3
         4   _   5   ----------->    4   2   5  
         8   6   7                   8   6   7
      Inversion count increases by 2 (changes from 2 to 4)
       

…..(ii) Decreases inversion count by 2

         1   3   4    Column Move     1   3   4
         5   _   6   ------------>    5   2   6
         7   2   8                    7   _   8
      Inversion count decreases by 2 (changes from 5  to 3)

…..(iii) Keeps the inversion count same.

         1   2   3    Column Move     1   2   3
         4   _   5   ------------>    4   6   5
         7   6   8                    7   _   8
        Inversion count remains 1 after the move 

So if a move either increases/decreases inversion count by 2, or keeps the inversion count same, then it is not possible to change parity of a state by any sequence of row/column moves.

int getInvCount(int arr[])

{

    int inv_count = 0;

    for (int i = 0; i < 9 - 1; i++)

        for (int j = i+1; j < 9; j++)

             // Value 0 is used for empty space

             if (arr[j] && arr[i] &&  arr[i] > arr[j])

                  inv_count++;

    return inv_count;

}

 

// This function returns true if given 8 puzzle is solvable.

bool isSolvable(int puzzle[3][3])

{

    // Count inversions in given 8 puzzle

    int invCount = getInvCount((int *)puzzle);

 

    // return true if inversion count is even.

    return (invCount%2 == 0);

}

Read full article from How to check if an instance of 8 puzzle is solvable? - GeeksforGeeks