title: n-puzzle solving with A* algorithm using C++
body: <p>I am implementing <code>A* algorithm</code> in C++ to solve the <strong>n-puzzle problem</strong>.<br>
  I tried to implement the pseudocode in <a href="http://www.heyes-jones.com/pseudocode.html" rel="nofollow">this</a> link.<br>
  Total cost(F=H+G) calculation is "cost depends on the number of misplaced tiles (Heuristics) + steps from initial state (G)". The algorithm of the <code>AStar</code> function given below.   </p>
  
  <p>The problem is, I am having an infinite loop situation. How can I solve this?</p>
  
  <p>PS: I can give the implementations of the other functions used in <code>AStar</code>, if requested.</p>
  
  <p>Any help would be appreciated.</p>
  
  <pre><code>void AStar(const int size, int** puzzle)
  {
  int moveCount = 0;                                                                  // initialize G(n)
  int**goalState = GoalState(size);                                                   // initialize  and assign goal state
  int openListIndex = 0;                                                              // initialize open list index
  vector&lt;node&gt; openList;                                                              // initialize open list
  vector&lt;node&gt; closedList;                                                            // initialize closed list
  
  node startNode;                                                                     // initialize start node
  startNode.puzzleArray = puzzle;                                                     // assign start node's state
  startNode.cost = moveCount + Heuristics(goalState,puzzle,size);                     // assign start node's cost
  
  node goalNode;                                                                      // initialize goal node
  goalNode.puzzleArray = goalState;                                                   // assign goal node's state
  
  openList.push_back(startNode);                                                      // push start node to the open list
  
  while (!openList.empty())                                                           // loop while open list is not empty
  {
      node currentNode = CalculateLowestCost(&amp;openList, &amp;closedList);                 // initialize current node which has the lowest cost, pop it from open list, push it to the closed list
      int** currentState = currentNode.puzzleArray;                                   // initialize and assign current state array
      /*********************************************************************************************/
      if (GoalCheck(goalState, currentState, size)) break;                            // GOAL CHECK//
      /*********************************************************************************************/
      vector&lt;char&gt; successorDirectionList = CalculateSuccessor(size, currentState);   // initialize a char vector for the directions of the successors
  
      int**successor;                                                                 // initialize successor state
      node successorNode;                                                             // initialize successor node
      moveCount++;                                                                    // advance G(n)
  
      for (;!successorDirectionList.empty();)                                         // loop over the successor list
      {
          char direction = successorDirectionList.back();                             // take a direction from the list
          successorDirectionList.pop_back();                                          // remove that direction from the list
          successor = MoveBlank(currentState, size, direction);                       // assign successor state
  
          successorNode.puzzleArray = successor;                                      // assign successor node's state
          successorNode.cost = moveCount + Heuristics(goalState,currentState,size);   // assign successor node's cost
  
          //vector&lt;node&gt; stateCheckList = openList;                                   // copy the open list for the checking the nodes in that list
  
          bool flagOpen = false;
          bool flagClosed = false;
          int locationOpen = -1;
          int locationClosed = -1;
  
          for (int i=0; i&lt;openList.size(); i++)
          {
              int** existing = openList[i].puzzleArray;
              int existingCost = openList[i].cost;
  
              if (StateCheck(successor, existing, size))
              {
                  locationOpen = i;
                  if (successorNode.cost &gt; existingCost)
                  {
                      flagOpen = true;
                      break;
                  }
              }
          }
          if (flagOpen) continue;
  
          int** existingInOpen;
          if(locationOpen != -1) 
          {
              existingInOpen = openList[locationOpen].puzzleArray;
              openList.erase(openList.begin()+locationOpen);
          }
  
          for (int i=0; i&lt;closedList.size(); i++)
          {
              int** existing = closedList[i].puzzleArray;
              int existingCost = closedList[i].cost;
  
              if (StateCheck(successor, existing, size))
              {
                  locationClosed = i;
                  if (successorNode.cost &gt; existingCost)
                  {
                      flagClosed = true;
                      break;
                  }
              }
          }
          if (flagClosed) continue;
  
          int**existingInClosed;
          if(locationClosed != -1)
          {
              existingInClosed = closedList[locationClosed].puzzleArray;
              closedList.erase(closedList.begin()+locationClosed);
          }
  
          openList.push_back(successorNode);
      }    
  }
  </code></pre>
  
  <p>}</p>