public static boolean isSolvable ( EightPuzzleState state ) { // Take a copy of the puzzle to check. This is done because this puzzle will be updated in-place and the // original is to be preserved. EightPuzzleState checkState ; try { checkState = ( EightPuzzleState ) state . clone ( ) ; } catch ( CloneNotSupportedException e ) { throw new IllegalStateException ( "Puzzle state could not be cloned." , e ) ; } // Create the goal state to check against when swapping tiles into position. EightPuzzleState goalState = getGoalState ( ) ; // Count the number of illegal swaps needed to put the puzzle in order. int illegalSwaps = 0 ; // Loop over the whole board, left to right, to to bottom for ( int j = 0 ; j < 3 ; j ++ ) { for ( int i = 0 ; i < 3 ; i ++ ) { // Find out from the goal state what tile should be at this position. char t = goalState . getTileAt ( i , j ) ; // Swap the tile into its goal position keeping count of the total number of illegal swaps. illegalSwaps += checkState . swapTileToLocationCountingIllegal ( t , i , j ) ; } } // Check if the number of illegal swaps is even in which case the puzzle is solvable, or odd in which case it // is not solvable. return ( illegalSwaps % 2 ) == 0 ; }
To check for solvability the empty tile is moved to its goal position and then the number of swaps needed to put the other tiles in position is counted . For an odd number of rows on a square puzzle there must be an even number of swaps for an even number of rows an odd number of swaps .