question: public int eval ( INode state ) { EightPuzzleNode node = ( EightPuzzleNode ) state ; int Pn = 0 ; for ( int r = 0 ; r <= EightPuzzleNode . MaxR ; r ++ ) { for ( int c = 0 ; c <= EightPuzzleNode . MaxC ; c ++ ) { if ( node . isEmpty ( r , c ) ) { continue ; } int digit = node . cell ( r , c ) ; Pn += Math . abs ( diffs [ digit ] [ 0 ] - r ) ; Pn += Math . abs ( diffs [ digit ] [ 1 ] - c ) ; } } int Sn = 0 ; if ( ! node . isEmpty ( 1 , 1 ) ) { Sn = 1 ; } for ( int r = 0 ; r <= EightPuzzleNode . MaxR ; r ++ ) { for ( int c = 0 ; c <= EightPuzzleNode . MaxC ; c ++ ) { int idx = r * 3 + c ; if ( r == 1 && c == 1 ) { continue ; } if ( node . cell ( r , c ) == EightPuzzleNode . EmptyMark ) { continue ; } if ( succ [ node . cell ( r , c ) ] != node . cell ( succs [ idx ] [ 0 ] , succs [ idx ] [ 1 ] ) ) { Sn += 2 ; } } } int gn = 0 ; DepthTransition t = ( DepthTransition ) state . storedData ( ) ; if ( t != null ) { gn = t . depth ; } return gn + Pn + 3 * Sn ; }
target:  h^(n) = P(n) + 3*S(n), where P(n) is the sum of the distances (via manhattan metric) that each tile is from "home". S(n) is a sequence score obtained by checking around the noncentral squares in turn, allotting 2 for every  tile not followed by its proper successor and 0 for every other tile, except that a piece in the center scores 1. <p> Compute f^(n) = g^(n) + h^(n) where g(n) is the length of the path form the start node n to the state.