8-Puzzle with A* (A Star) C#

Rather than Depth-First, Breadth-First is complete, which means it will find a solution if it exist. But the solution may be so long and we might need to decide which node to expand, which we don't;

Assume that we are searching for a node with state 4, with regular BFS, (assuming 2 is the node that will be branching to) we need to create 7 nodes to find the node 4.

But if our algorithm can see that, branching to node 3 at the first point, is better than branching to 2, because if we branch to 2, we will need to create two extra nodes, which means performance loss.

But how is an BFS algorithm can decide which node to branch? 

If an algorithm is able to decide to perform an action than performing another action, it uses a heuristic function.

Heuristic function is shown as h(x). In A* algorithm, use f(x) which equals to g(x) + h(x); which takes advantage of two different methods. 

So, what can be h(x) for n-puzzle?

We can use Manhattan Distance to determine h(x) for 8-Puzzle. Manhattan Distance is the measurement of distance between a state and goal state. It is 0 when two states are the same, and it is higher when there are more difference between states.

Let's give an example;

{0,1,2,3,4,5,6,7,8} is goal state, {1,2,0,3,4,5,6,7,8} and {1,0,2,3,5,4,6,8,7} are states we generated. We want to reach to goal state after branching one of these nodes. So we calculate Manhattan Distance;

• h({1,2,0,3,4,5,6,7,8}) = 1+1+1+0+0+0+0+0+0 = 3 because there are only 3 piles which are in wrong space.

• h({1,0,2,3,5,4,6,8,7}) = 1+1+1+1 = 4 because there are 4 tiles in wrong spaces.

We branch to the node with low h(x), which is {1,2,0,3,4,5,6,7,8}.

That's how we make decision.

Function calculates h(x) can be written as;

        public int GetHValue(int[] State)
        {
            int hval = 0;
            for (int x = 0; x < 9; x++)
            {
                if (GoalState[x] != State[x])
                    hval++;
            }
            return hval;
        }

And we also have g(x) to consider. g(x) refers to path cost. When you go below in the tree, path cost increases as it decrease when you go back to the root node.

In this tree, numbers inside trees represent g(x), path cost. It is zero in root node, because g(x) is relative to root node, and it is increasing in every level of nodes. So, why do we use g(x)? We may find the same node which can generate same child nodes over and over, in different places in the tree. In this situations, to keep solution short, we choose the node with the lower path cost (that is closer to root node) than other which also has same state but more path cost, bottom in the tree. In this way we can reach to the goal state faster and shorten solution sequences.

So; how does A* algorithm take the advantage of both g(x) and h(x)? 

If it would only use h(x), it would be categorized as Greedy-Best First algorithm.

Uniform-Cost Search only uses g(x).

A* Searching algorithm follows the following ways to reach to the goal state;

• It creates an open list which called as Frontier and closed list which we call as Solution.
• In begins to loop

            Expands the node which has the lowest f(x) in the Frontier, and then adds it to Solution
            If a generated child node is in Solution, it is ignored
            If it is not in the Frontier, calculates f(x), h(x) and g(x) for nodes and en-queues into frontier

            If the node is in the Frontier already; compares the node in the Frontier with new node, and the node in the Frontier is replaced if it's g(x) is higher than new successor's g(x). If it is not, the node is en-queued to the Frontier.

• It ends the loop when the node is the goal state, or when the open list is empty.

I am going to use the same template that I have used in BFS algorithm I published. The change is going to be in Solve function of course, and in Node object we have a new attribute which is PathCost value. We also need to write set and get functions for PathCost.

For Frontier and Solution, we will use PriorityQueue to make the list faster. It is going to sort the queue after adding new item to the list automatically.

You can find PriorityQueue article at here.

We are going to create another class inherited from this PriorityQueue, that shows different behaviors for Frontier and Solution in AStar.

1.   class AStarQueue : PQueue.PriorityQueue<Node>
2.   {
3.     int QueueType;
4.  
5.     public AStarQueue(bool AllowRepeat, int QueueType)
6.     {}
7.  
8.     public override bool IsRepetitionExist(int Key, Node obj)
9.     {}
10.  
11.     public bool CompareStates(int[] s1, int[] s2)
12.     {}
13.   }

Only functionality change is in IsRepetitionExist function. Which denies the input and stops the function when it is Solution queue, and compare states and their heuristic values when it is Frontier. Here is the code:

1.     public override bool IsRepetitionExist(int Key, Node obj)
2.     {
3.       if (QueueType == 1) //frontier
4.       {
5.         LinkedListNode<PQueue.QueueItem<Node>> current = Items.First;
6.         //Checks other nodes in the frontier
7.         while (current != null)
8.         {
9.           if (CompareStates(current.Value.GetObj().GetState(), obj.GetState()))
10.           {
11.             //Compares Path Cost of two nodes
12.             if (current.Value.GetObj().GetPathCost() > obj.GetPathCost())
13.             {
14.               //Replaced the old one if it's deeper than new one.
15.               Replace(current, new PQueue.QueueItem<Node>(obj.GetHValue() +
16.                 obj.GetPathCost(), obj));
17.               break;
18.             }
19.           }
20.           current = current.Next;
21.         }
22.         return false;
23.       }
24.       else
25.       {
26.         LinkedListNode<PQueue.QueueItem<Node>> current = Items.First;
27.         while (current != null && current.Value.GetKey() <= obj.GetHValue())
28.         {
29.           if (CompareStates(current.Value.GetObj().GetState(), obj.GetState()))
30.             return true;
31.           current = current.Next;
32.         }
33.         return false;
34.       }
35.     }

And of course, our main class AStar.cs will have the following;

1.   class AStar
2.   {
3.  
4.     int[] GoalState = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
5.     enum QueueTypeEnum { Frontier = 1, Solution = 2 };
6.     private AStarQueue Solution;
7.     private AStarQueue Frontier;
8.     private Node RootNode;
9.  
10.     public AStar(int[] StartState)
11.     {
12.     }
13.  
14.     public void Solve()
15.     {
16.     }
17.  
18.     public IEnumerable<Node> GenerateSuccessor(Node ParentNode)
19.     {
20.     }
21.  
22.     public bool IsGoalState(int[] State)
23.     {
24.     }
25.  
26.     public void WriteSolution()
27.     {
28.     }
29.  
30.     public int GetHValue(int[] State)
31.     {
32.     }
33.  
34.     public bool CompareStates(int[] s1, int[] s2)
35.     {
36.     }
37.   }

Here, we are going to focus on Solve function. You can find other functions in my BFS example on this blog.

I've stated that, A* follows following steps;

• It creates an open list which called as Frontier and closed list which we call as Solution.
• In begins to loop

            Expands the node which has the lowest f(x) in the Frontier, and then adds it to Solution
            If a generated child node is in Solution, it is ignored
            If it is not in the Frontier, calculates f(x), h(x) and g(x) for nodes and en-queues into frontier
            If the node is in the Frontier already; compares the node in the Frontier with new node, and the node in the Frontier is replaced if it's g(x) is higher than new successor's g(x). If it is not, the node is en-queued to the Frontier.

• It ends the loop when the node is the goal state, or when the open list is empty.

Here is the code for Solve function. It is typically same with BFS example.

1.     public void Solve()
2.     {
3.       Node ActiveNode = RootNode;
4.       bool IsSolved = false;
5.  
6.       while (!IsGoalState(ActiveNode.GetState()) )
7.       {
8.         Solution.Enqueue(ActiveNode.GetHValue(),ActiveNode);
9.         foreach (Node successor in GenerateSuccessor(ActiveNode))
10.         {
11.           if (!Solution.IsRepetitionExist(successor.GetHValue() + successor.GetPathCost(), successor))
12.           {
13.             Frontier.Enqueue(successor.GetHValue() + successor.GetPathCost(), successor);
14.           }
15.         }
16.  
17.         if (IsSolved)
18.           break;
19.  
20.         ActiveNode = Frontier.Dequeue();
21.       }
22.       WriteSolution();
23.     }

* This source code was highlighted with Source Code Highlighter.

When we run it;

If we would use BFS, we would create thousands of nodes the find the solution. A Star shows intelligence and is able make choice while searching in the tree.

Here are the code files:
AStar.cs
AStarQueue.cs
Node.cs
PriorityQueue.cs
QueueItem.cs

You will run the code as;

1.   class Program
2.   {
3.     static void Main(string[] args)
4.     {
5.       int[] ex = { 3,2,4,6,0,1,7,8,5};
6.       AStar _AStarEx = new AStar(ex);
7.       _AStarEx.Solve();
8.     }
9.   }

* This source code was highlighted with Source Code Highlighter.