The 8-puzzle problem using A* algorithm

Let me first tell you about the 8-puzzle problem. This puzzle or game (however you like to call it) is a smaller version of the N-puzzle problem where n can be 8, 15, 24…

Basically, in our case we are taking a grid of 9 boxes or a 3X3 matrix as seen in the figure below:

Figure 1 Start state of the game

And we want to reach to some goal state let’s say for our example the goal state is this:

Figure 2 Goal state of the game

So, to reach to our goal state we must move our tiles that are not empty towards the empty space one at a time and make sure that we move the tiles in only four directions that are:

· UP

· Left

· Down

· Right

We cannot move a tile diagonally.

One thing we can do is that instead of moving the tile to the empty space, we can move the empty space in the four mentioned directions i.e., swapping the tile with the empty space.

So, what will be our next move from the initial state?

Technically we can move the empty space to 3 directions right now that are Up, left and right as obviously down is not a valid move. So, we can do:

Figure 3 Tree for the first step

Now, we don’t know which path we should continue.

Should we go towards the first path?

Should we go towards all the paths?

A* algorithm

Search algorithms are algorithms designed to search for or retrieve elements from a data structure, where they are stored. They are essential to access desired elements in a data structure and retrieve them when a need arises. A vital aspect of search algorithms is Path Finding, which is used to find paths that can be taken to traverse from one point to another, by finding the most optimum route.

It is a searching algorithm that is used to find the shortest path between an initial and a final point.

It is a handy algorithm that is often used for map traversal to find the shortest path to be taken. A* was initially designed as a graph traversal problem, to help build a robot that can find its own course. It still remains a widely popular algorithm for graph traversal.

It searches for shorter paths first, thus making it an optimal and complete algorithm. An optimal algorithm will find the least cost outcome for a problem, while a complete algorithm finds all the possible outcomes of a problem.

Another aspect that makes A* so powerful is the use of weighted graphs in its implementation. A weighted graph uses numbers to represent the cost of taking each path or course of action. This means that the algorithms can take the path with the least cost, and find the best route in terms of distance and time.

A weighted graph

The concept of heuristic

In normal search techniques such as linear search, binary search and the breadth first search, the algorithm doesn’t know about what they are searching for neither they know where to search for it. They follow their algorithm completely in a structured order always.

The thing is while these techniques do find the solution but only after they have done their whole exhaustive method.

This is where heuristic search comes into play. The heuristic function acts as a tour guide and keeps on telling the algorithm where to go next. This is informed search technique. They are also called Weak search techniques 😉.

In our case we will take the heuristic function as the sum of two things:

1. The cost of reaching from one state to another state. (G-Score)

2. The cost of reaching from to the goal state from the second state. (H-Score)

The G-score can be calculated by finding the Euclidean or the Manhattan distance between the two states.

For example, if the initial state is

And the first path that we can find is

It’s Euclidean distance with the final state is:

The Euclidean distance formula

Which comes to be 9.27

Similarly, for

the distance is 13.1149

And for

the distance is 12.1665

Now, the second heuristic function is the number of tiles that are still misplaced after the step and that is quite easy to count:

Figure 4 3 misplaced tiles

Figure 5 5 misplaced tiles

Figure 6 5 misplaced tiles

Thus after getting these two values, we can easily determine that the next step should be:

Figure 7 3 misplaced tiles and 9.27 distance

Similarly taking this as the current node the three possible values can be:

Figure 8 Second Step

After calculating both heuristic functions you will find out that the best move in this step is:

Figure 9 best move for second step

Let us now visualise from the initial state to the final state:

I hope you learned something from the blog, if you wish to learn more about A* algorithm and how to solve * puzzle using it you refer to these links:

[1] A* algorithm and concepts you should now

[2] Microsoft PowerPoint — AI-UNIT3-version7

[3] Trace for A*