How to check if an instance of 8 puzzle is solvable ? | 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
< ? php function getInvCount ( $ arr ) { $ inv_count = 0 ; for ( $ i = 0 ; $ i < 9 - 1 ; $ i ++ ) for ( $ j = $ i + 1 ; $ j < 9 ; $ j ++ ) $ inv_count ++ ; return $ inv_count ; } function isSolvable ( $ puzzle ) { $ invCount = getInvCount ( $ puzzle ) ; return ( $ invCount % 2 == 0 ) ; } $ puzzle = array ( array ( 1 , 8 , 2 ) , array ( 0 , 4 , 3 ) , array ( 7 , 6 , 5 ) ) ; if ( isSolvable ( $ puzzle ) == true ) echo " Solvable " ; else echo " Not ▁ Solvable " ; ? >