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;
}

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 ; }
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 .
