What is wrong with my A* search for 8-Puzzle?

Question

I am trying to use A* search with these heuristics to solve 8-Puzzle: - h1: number of misplaced tiles - h2: total manhattan distance - h3: sum of the above

The moving tile is known as 0.

My goal is to solve these sets:

4 1 2
5 8 3
7 0 6

and

8 6 7
2 5 4
3 0 1

The problem I am having is that with my current implementation of A*, it is able to solve the first problem, but not for the second problem..

So please help me out in understanding what is wrong with my A* code:

int[,] current = inputted from console as string (412583706) and turned into 2D int representing the puzzle. Same for correct, where 0 is in the lower right corner.

var openList = new List<int[,]> { current };
var closedList = new List<int[,]>();

while (openList.Count > 0)
{
    steps++;
    current = GetBestNodeFromList(correct, dimensions, openList, useHeuristic);
    // "GetBestNodeFromList()" finds the cheapest node in the openList.
    // cheapest node: lowest value of h3.

    openList.Remove(current);
    h1 = getHeuristic1b(current, correct, dimensions);
    h2 = getHeuristic2b(current, correct, dimensions);
    h3 = h1 + h2;
    if (h1 == 0 && h2 == 0) { break; }

    openList = Puzzle_PossibleNext(current, closedList);
    // the method "PossibleNext()" finds possible next moves from the current
    // position. if the next move exists in the closedList, it is discarded.

    // Drawing the puzzle and showing heuristics.
    DrawCurrentState(h1, h2, h3, current, steps);

    // adding last visited position to the closedlist.
    closedList.Add(current);
}

The first problem is solved with 7 steps. According to a different program I tested, the next problem can be solved with 32 steps.

Where my program differs from the other is that the first 4 steps are the same, then the other program chooses a different route, while mine just keeps going forever and cannot find a solution. It seems like my program did select the cheapest node, so this is why I cannot understand what is wrong.

It is my first time with pathfinding algorithms, so I would like to solve it. I have been having this problem for 3 days, and I feel like I have tried many solutions, but none work T_T

Best regards.

----Edit----- Additional code:

// Put heuristic value from all in list, then return list item with lowest h-value.
static int[,] GetBestNodeFromList(int[,] correct, int d, List<int[,]> list, string useHeuristic)
{
    int[,] n = new int[d,d];
    if (list.Count > 0)
    {
        List<Int32> heuristicsValueList = new List<Int32>();
        for (int i = 0; i < list.Count; i++)
        {
            if (useHeuristic == "h1")      { heuristicsValueList.Add(getHeuristic1b(list[i], correct, d)); }
            else if (useHeuristic == "h2") { heuristicsValueList.Add(getHeuristic2b(list[i], correct, d)); }
            else  { heuristicsValueList.Add(getHeuristic3(list[i], correct, d)); }
        }
        n = list[heuristicsValueList.IndexOf(heuristicsValueList.Min())];
    }
    return n;
}

---------edit 2-------- changed my code a bit, but still no luck the puzzle setup/node and its heuristics are all in the PuzzleNode object.

// returns a list over next possible moves from the current node. // does not include moves that are found inside closedNodeList.

static List<PuzzleNode> Puzzle_GenerateNextNodes(PuzzleNode node, List<PuzzleNode> closedNodeList)
        {
            List<PuzzleNode> nextList = new List<PuzzleNode>();
            Point isNow = new Point(0, 0);

            // 1) Find where [0] is.
            int dimensions = (int)Math.Sqrt((double)node.n.Length);
            for (int x = 0; x < dimensions; x++) {
                for (int y = 0; y < dimensions; y++) { if (node.n[x, y] == 0) { isNow.X = y; isNow.Y = x; break; } }
            }

            // 2) Check possible moves.
            bool moveUp = false, moveDown = false, moveLeft = false, moveRight = false;

            if (isNow.X == 0)
            {
                moveRight = true;
                if (isNow.Y == 0) { moveDown = true; }
                else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
                else if (isNow.Y == 2) { moveUp = true; }
            }
            else if (isNow.X == 1)
            {
                moveRight = true;
                moveLeft = true;
                if (isNow.Y == 0) { moveDown = true; }
                else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
                else if (isNow.Y == 2) { moveUp = true; }
            }
            else if (isNow.X == 2)
            {
                moveLeft = true;
                if (isNow.Y == 0) { moveDown = true; }
                else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
                else if (isNow.Y == 2) { moveUp = true; }
            }
            // 3) Create list of possible moves.

// Add moved puzzle node to list over next moves 
            if (moveRight)
            {
                int[,] right = new int[dimensions, dimensions];
                Array.Copy(node.n, right, node.n.Length);
                PuzzleNode tmp = new PuzzleNode( PuzzleMoveRight(right, isNow.X, isNow.Y) );
                if (!ListHasThisValue(tmp.n, closedNodeList, dimensions)) { nextList.Add(tmp); }
            }
// moveleft, up, down, same structure as moveRight
            if (moveLeft)
            {
                ..
            }
            if (moveUp)
            {
                ..
            }
            if (moveDown)
            {
                ..
            }

            return nextList;
        }

-----------edit 3----------------

By the way, I want to ask, if my implementation of the different steps of A* are correctly understood. At the moment, my program's A* search does this:

1. Create initial list OPEN and CLOSED, add starting node to OPEN
2. Starting loop, removing cheapest node from OPEN, adding it to CLOSED *Cheapest node is determined by its manhattan distance value.
3. Using the node to find neighbours/children/next moves, adding these to a SUCCESSOR list.
4. Explore SUCCESSOR list, check if any of them contains goal state, else add to OPEN list
5. repeat 2-4, exploring the nodes in the list.

When I try these steps with Q1, I get the solution in 7 steps, which is correct. This is also found by hand. But with Q2, it keeps going until OPEN list is empty and there is nothing else to explore. So what am I missing?

Answer 1

I want to thank all for helping me with this problem.

I was able to find the problem today. I don't know how to say it, it's really stupid. The problem was not the code or the A* implementation (my current code may differ from what posted earlier).

The issue was over-relying on the heuristics used. It seems that for Q1, heuristic h1, h2 and h3(h1 and h2 had same cost) could all find the solution. However for Q2, both h2 and h3 were not able to find the path to the solution, but h1 was. In my program I kept on using h3 as the default heuristic for debugging and testing, which also was my downfall.

So lesson that should be learned is to know what you are working with. I was not able to realize the difference even the simplest heuristics were able to make.

I am now able to solve Q1 and Q2. Thank you all, again. As a programmer, I sure learned from this.

I wish I could give you all more visible credit for taking the time to help out, though.

Answer 2

I was able to find solution quickly via brute force. A* should revert to brute force if you're using totally dumb heuristic. How are you comparing your state to list of closed states ?

var set = new int[,] {
  { 1, 2, 3 },
  { 4, 5, 6 },
  { 7, 8, 0 }
};
var clone = (int[,])set.Clone();

var foo = clone == set; // foo is false
var bar = clone.Equals(set); // bar is false

var closedStates = new List<int[,]>();
closedStates.Contains(state); // wrong - contains is using Equals
closedStates.Any(cs => AreEqual(cs, state)); // correct

static bool AreEqual(int[,] stateA, int[,] stateB) {
  for (var x = 0; x < DIMENSIONS; x++) {
    for (var y = 0; y < DIMENSIONS; y++) {
      if (stateA[x, y] != stateB[x, y]) {
        return false;
      }
    }
  }
  return true;
}