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
function getInvCount ( arr ) { let inv_count = 0 ; for ( let i = 0 ; i < 2 ; i ++ ) { for ( let j = i + 1 ; j < 3 ; j ++ ) { if ( arr [ j ] [ i ] > 0 && arr [ j ] [ i ] > arr [ i ] [ j ] ) inv_count += 1 ; } } return inv_count ; } function isSolvable ( puzzle ) { let invCount = getInvCount ( puzzle ) ; return ( invCount % 2 == 0 ) ; } puzzle = [ [ 1 , 8 , 2 ] , [ 0 , 4 , 3 ] , [ 7 , 6 , 5 ] ] ; if ( isSolvable ( puzzle ) ) document . write ( " " ) ; else document . write ( " " ) ;