title: A * Heuristic for Sliding Puzzle is not working as expected
body: <p>I am implementing a solver for a sliding puzzle. In one implementation, I used a Breadth First Search. In the second one, I am using A *. However, A * is going slower than the BFS approach. I measured the average time for BFS to solve a 9x9 puzzle is around .227 seconds whereas for A * it is taking almost 2 seconds long. </p>
  
  <p>The heuristic I am using for A * is the following : F = G + H where G is the number of blocks out of order and H is the combined sum of manhattan distance for every tile to its supposed position in the goal state (which the user defines). </p>
  
  <p>Here is the relevant parts of A * code (The comparator is used in a priority queue): </p>
  
  <pre><code>private void addToPriorityQueue(PuzzleState nextPS) {
      if (nextPS != null &amp;&amp; !this.visited.contains(nextPS))
          pQueue.add(nextPS);
  }
  
  private boolean solveByAStar() {
      pQueue.clear();
      pQueue.add(this.initialState);
  
      while(!pQueue.isEmpty()) { 
          if (pQueue.size() &gt; maxQueueSize)
              maxQueueSize = pQueue.size();
  
          this.currentState = pQueue.poll();
  
          if (this.currentState.equals(finalState)) { 
              return true;
          }
  
          visited.add(this.currentState);
  
          this.addToPriorityQueue(this.currentState.moveUp());
          this.addToPriorityQueue(this.currentState.moveDown());
          this.addToPriorityQueue(this.currentState.moveRight());
          this.addToPriorityQueue(this.currentState.moveLeft());
  
      }
      return false;
  }
  
  private class puzzleStateComparator implements Comparator&lt;PuzzleState&gt; {
  
      @Override
      public int compare(PuzzleState o1, PuzzleState o2) {
          //TODO
  
          int[] goalState = FastPuzzleSolver.this.initialState.getStateArray();
  
          int o1GScore = PuzzlePropertyUtility.numBlocksOutOfPlace(o1.getStateArray(), goalState);
          int o2GScore = PuzzlePropertyUtility.numBlocksOutOfPlace(o2.getStateArray(), goalState);
  
          int o1HScore = PuzzlePropertyUtility.calculateManhattanDistanceSum(o1.getStateArray(), goalState);
          int o2HScore = PuzzlePropertyUtility.calculateManhattanDistanceSum(o2.getStateArray(), goalState);
  
  
  
          return Integer.compare(o2GScore + o2HScore, o1GScore + o1HScore);
  
  
      }
  
  }
  </code></pre>
  
  <p>And here are the methods used to calculate G and H : </p>
  
  <pre><code>public static int numBlocksOutOfPlace(int[] ps, int[] goal) {
      int difference = 0;
      for (int i : ps) {
          if (ps[i] != goal[i])
                  difference++;
      }
      return difference;
  }
  
  public static int calculateManhattanDistanceSum(int[] ps, int[] goal) {
      int rowSz = calculatePuzzleRowSize(ps);
      int manhattanDistanceSum = 0;
      for (int i = 0; i &lt; ps.length; i++) {
          for (int j = 0; j &lt; ps.length; j++) {
              if (ps[i] == goal[j])
                  manhattanDistanceSum += (Math.abs(i/rowSz - j/rowSz) + Math.abs(i%rowSz - j%rowSz)); 
          }
      }
      return manhattanDistanceSum;
  }
  </code></pre>
  
  <p>Is the reason behind the slowness because of the efficiency of my code or is it that my heuristic is flawed or both?</p>
  
  <p>Thanks in advance.</p>