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
def getInvCount ( arr ) : NEW_LINE INDENT inv_count = 0 NEW_LINE for i in range ( 0 , 2 ) : NEW_LINE INDENT for j in range ( i + 1 , 3 ) : NEW_LINE INDENT if ( arr [ j ] [ i ] > 0 and arr [ j ] [ i ] > arr [ i ] [ j ] ) : NEW_LINE INDENT inv_count += 1 NEW_LINE DEDENT DEDENT DEDENT return inv_count NEW_LINE DEDENT def isSolvable ( puzzle ) : NEW_LINE INDENT invCount = getInvCount ( puzzle ) NEW_LINE return ( invCount % 2 == 0 ) NEW_LINE DEDENT puzzle = [ [ 1 , 8 , 2 ] , [ 0 , 4 , 3 ] , [ 7 , 6 , 5 ] ] NEW_LINE if ( isSolvable ( puzzle ) ) : NEW_LINE INDENT print ( " Solvable " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ Solvable " ) NEW_LINE DEDENT