title: Solving 8 puzzle using A* algorithm and Manhattan Heuristic
body: <p>I have written a program to solve the 8 puzzle using the A* algorithm and the Manhattan heuristic but the programs doesn't seem to work correctly ( minimum number of moves ) for all the inputs and even for the correct output, the number of states expanded is much larger than what it should normally be.</p>
  
  <p>My program has four classes:<br>
  Game State: To represent the Game<br>
  AStar: AStar algorithm<br>
  AStarList: A data structure for representing the open and closed lists. (I know that my data structure is very bad in terms of performance. I will improve it later on)<br>
  Utilities</p>
  
  <p>Here is part of the code:</p>
  
  <p>(Sorry for the large code size. I suspect that something is wrong with my AStar algorithm. So, you probably need not go through the other classes.)</p>
  
  <p>AStar</p>
  
  <pre><code>public class AStar {
  
      public static void solve(GameState gameStateToSolve) {
          AStarList openList = new AStarList();
          AStarList closedlList = new AStarList();
          openList.add(gameStateToSolve);
          int iteration = 1;
          while (!openList.isEmpty()) {
              System.out.println((iteration++));
              GameState current = openList.getNext();
              if (current.isGoalState()) {
                  current.print();
                  return;
              }
              GameState children[] = current.expand();
              closedlList.addWithoutDuplication(current);
              for (int i = 0; i &lt; children.length; i++) {
                  boolean presentInOpenList = openList.isPresent(children[i]);
                  boolean presentInClosedList = closedlList.isPresent(children[i]);
                  if (!presentInOpenList &amp;&amp; !presentInClosedList) {
                      openList.add(children[i]);
                  } else if (presentInClosedList &amp;&amp; !presentInOpenList) {
                      if (closedlList.getCostOf(children[i]) &gt; children[i].getMovementsCount()) {
                          closedlList.remove(children[i]);
                          openList.add(children[i]);
                      }
                  } else if (presentInOpenList &amp;&amp; !presentInClosedList) {
                      if (openList.getCostOf(children[i]) &gt; children[i].getMovementsCount()) {
                          openList.remove(children[i]);
                          openList.add(children[i]);
                      }
                  }
              }
          }
      }
  
      public static void main(String[] args) {
          solve(new GameState(
                  new int[]{0,7,3,1,8,6,5,4,2},
                  new ArrayList&lt;Integer&gt;(),
                  GameState.NUMBERS_ARRAY));
      }
  }
  </code></pre>
  
  <p>AStarList</p>
  
  <pre><code>public class AStarList {
  
      ArrayList&lt;GameState&gt; list;
  
      public AStarList() {
          list = new ArrayList&lt;&gt;();
      }
  
      public boolean isPresent(GameState gameState) {
          for (int i = 0; i &lt; list.size(); i++) {
              if (list.get(i).equals(gameState)) {
                  return true;
              }
          }
          return false;
      }
  
      public void remove(GameState gameState) {
          for (int i = 0; i &lt; list.size(); i++) {
              if (list.get(i).equals(gameState)) {
                  list.remove(i);
              }
          }
      }
  
      public void add(GameState gameState) {
          for (int i = 0; i &lt; list.size(); i++) {
              if (list.get(i).manhattanDistance() &gt; gameState.manhattanDistance()) {
                  list.add(i, gameState);
                  return;
              }
          }
          list.add(gameState);
      }
  
      public void addWithoutDuplication(GameState gameState) {
          for (int i = 0; i &lt; list.size(); i++) {
              if (list.get(i).equals(gameState)) {
                  list.remove(i);
                  list.add(i, gameState);
              }
              if (list.get(i).manhattanDistance() &gt; gameState.manhattanDistance()) {
                  list.add(i, gameState);
                  return;
              }
          }
          list.add(gameState);
      }
  
      public boolean isEmpty() {
          return list.isEmpty();
      }
  
      public GameState getNext() {
          return list.remove(0);
      }
  
      public int getHeuristicOf(GameState gameState) {
          for (int i = 0; i &lt; list.size(); i++) {
              if (list.get(i).equals(gameState)) {
                  return list.get(i).manhattanDistance();
              }
          }
          throw new RuntimeException();
      }
  
      public int getCostOf(GameState gameState) {
          for (int i = 0; i &lt; list.size(); i++) {
              if (list.get(i).equals(gameState)) {
                  return list.get(i).getMovementsCount();
              }
          }
          return -1;
      }
  }
  </code></pre>
  
  <p>GameState</p>
  
  <pre><code>public final class GameState1 {
  
  
  
      public GameState1(GameState gameState) {
         // creates a GameState exactly similar to the one passed
      }
  
      public GameState1(int[] array, ArrayList&lt;Integer&gt; movements, int type) {
       //...
      }
  
      public int getMovementsCount() {
       // returns number of movements made so far
      }
  
      public int[] getPositionsArrayOf(int[] numbersArray) {
          //...
      }
  
      public int[] getNumbersArrayOf(int[] positionsArray) {
          //...
      }
  
      public void move(int direction) {
          //...
      }
  
      public GameState getStateOnMovement(int direction) {
         //...
      }
  
  
      public boolean movePossible(int direction) {
          //...
      }
  
      public int[] getPossibleMovements() {
         //...
      }
  
      public GameState[] expand() {
         //..
      }
  
      public boolean equals(GameState anotherState) {
       // returns true if the board state is the same
      }
  
      public boolean isGoalState() {
        // returns true if it is goal state
      }
  
      public void print() {
          //...
      }
  
  
  
  
      public int numberOfInversions() {
          // returns number of inversions
      }
  
      public boolean isSolvable() {
         //returns true if solvable
      }
  
      public int manhattanDistance() {
       // returns manhattan distance
      }
  
     }
  </code></pre>
  
  <p>Sorry for the large code size. I suspect that something is wrong with my AStar algorithm. S0, you probably need not go through the other classes.</p>