How to check if an instance of 8 puzzle is solvable ? | C ++ 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 progra to test above functions
#include <iostream> NEW_LINE using namespace std ; int getInvCount ( int arr [ ] ) { int inv_count = 0 ; for ( int i = 0 ; i < 9 - 1 ; i ++ ) for ( int j = i + 1 ; j < 9 ; j ++ ) if ( arr [ j ] && arr [ i ] && arr [ i ] > arr [ j ] ) inv_count ++ ; return inv_count ; } bool isSolvable ( int puzzle [ 3 ] [ 3 ] ) { int invCount = getInvCount ( ( int * ) puzzle ) ; return ( invCount % 2 == 0 ) ; } int main ( int argv , char * * args ) { int puzzle [ 3 ] [ 3 ] = { { 1 , 8 , 2 } , { 0 , 4 , 3 } , { 7 , 6 , 5 } } ; isSolvable ( puzzle ) ? cout << " Solvable " : cout << " Not ▁ Solvable " ; return 0 ; }