n-puzzle solving with A* algorithm using C++

Question

I am implementing A* algorithm in C++ to solve the n-puzzle problem.
I tried to implement the pseudocode in this link.
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 AStar function given below.

The problem is, I am having an infinite loop situation. How can I solve this?

PS: I can give the implementations of the other functions used in AStar, if requested.

Any help would be appreciated.

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<node> openList;                                                              // initialize open list
vector<node> 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(&openList, &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<char> 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<node> 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<openList.size(); i++)
        {
            int** existing = openList[i].puzzleArray;
            int existingCost = openList[i].cost;

            if (StateCheck(successor, existing, size))
            {
                locationOpen = i;
                if (successorNode.cost > 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<closedList.size(); i++)
        {
            int** existing = closedList[i].puzzleArray;
            int existingCost = closedList[i].cost;

            if (StateCheck(successor, existing, size))
            {
                locationClosed = i;
                if (successorNode.cost > 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);
    }    
}

}

Answer 1

Because of the possibility of loops, i.e. a sequence of moves that takes you back to a state you've already visited, it's important to check for duplicate states (not a problem with tree search, obviously). I can't quite follow what you're doing with your checking for this, but that's likely to be where the problem lies. I had a similar sort of problem to you when writing a Haskell implementation (details here and here), and it came down to a problem of handling the explored set. Get that right, and everything works. (Getting solutions for the 4x4 puzzle remains a bit of a hit-and-miss affair, especially if you start from a state a long way from the goal in state space, but that's mostly down to the deficiencies of A* and the naïve way we're dealing with possible moves.)

Answer 2

do you delete the state that you pick from your open list ? this is a C# code that is very easy and well written maybe it can help you : http://geekbrothers.org/index.php/categories/computer/12-solve-8-puzzle-with-a and also A* automatically avoid loops because it taken the moves you take to account

Answer 3

I also made an implementation of a n-puzzle (depth first and a*) and it entered in infinite loop. This happened because of the following loop: up, left, down, right, up, left... I really don't know if there is a way to prevent such thing (the maximum I could do was prevent loops like left-right-left... by remembering the last move it made).

Don't know if this is what causes your loop, the best way would be to in every iteration print the board to see what is really happening ;)