How to check if an instance of 8 puzzle is solvable ? | Java program to check if a given instance of 8 puzzle is solvable or not ; A utility function to count inversions in given array ' arr [ ] ' ; Value 0 is used for empty space ; This function returns true if given 8 puzzle is solvable . ; Count inversions in given 8 puzzle ; return true if inversion count is even . ; Driver code
class GFG { static int getInvCount ( int [ ] [ ] arr ) { int inv_count = 0 ; for ( int i = 0 ; i < 3 - 1 ; i ++ ) for ( int j = i + 1 ; j < 3 ; j ++ ) if ( arr [ j ] [ i ] > 0 && arr [ j ] [ i ] > arr [ i ] [ j ] ) inv_count ++ ; return inv_count ; } static boolean isSolvable ( int [ ] [ ] puzzle ) { int invCount = getInvCount ( puzzle ) ; return ( invCount % 2 == 0 ) ; } public static void main ( String [ ] args ) { int [ ] [ ] puzzle = { { 1 , 8 , 2 } , { 0 , 4 , 3 } , { 7 , 6 , 5 } } ; if ( isSolvable ( puzzle ) ) System . out . println ( " Solvable " ) ; else System . out . println ( " Not ▁ Solvable " ) ; } }