Click here to Skip to main content
15,867,453 members
Articles / Game Development

8/15 Puzzle using A* (A Star) Algorithm, C#

Rate me:
Please Sign up or sign in to vote.
4.65/5 (14 votes)
14 Jul 2013CPOL7 min read 113.5K   6.9K   17   17
8/15 puzzle using A* (A Star) algorithm.

Introduction

A* Algorithm

A* (“A Star”) algorithm is an informed search strategy – strategy that uses problem specific knowledge, deriving from the problem itself.

In other words, it is a best-first search algorithm that evaluates the next possible path based on the total estimated cost. It always looks for the cheapest path among the possible paths and tries to reach towards the goal.

Background

So how does A* knows which one is the cheapest path? Let’s take an example to see this.

Given the below map, a person has to travel from Delhi to Hyderabad. We know the actual distance that a person has to cover from one city to another (numbers in green color).

So travel distance from Delhi -> Mumbai is 12, Delhi -> Lucknow is 7, Mumbai -> Hyderabad is 8, Lucknow -> Kolkata is 6, and Kolkata -> Hyderabad is 9.

City Example

In real world, probably you would know the total distance that you might have to travel to reach Hyderabad, from all possible paths and you will choose the one where you see the minimum distance you have to cover. This is pretty easy when person has information about all the sates – from start to the final destination.

The challenge comes into the picture when you have no idea about the next destination unless you actually reach there i.e. when you have to actually discover the path from one point to another point and you don’t know the state unless you are in the state. This type of search is known as uniformed search – there is no other information other than the problem definition itself.

For example, you don’t know that there is a path from Mumbai to Hyderabad unless you reach at Mumbai.

Now, say along with the actual distance between Delhi and Mumbai, we also know the straight line distance of each city to Hyderabad – shortest path: always less or equal to the actual distance from current city to Hyderabad (known as Heuristic for A* algorithm).

For easy notation – we will call actual distance from one city to another as g.

And straight line distance from Hyderabad to any other city as h.

As you have noticed, heuristic cost h is not overestimating the cost g (h <= g; a very important thing for A* to converge).

Now we will say distance of moving from one city to another city is sum of actual distance (g) and straight line distance (h):

f = g + h.

This distance (f) is used by the algorithm to determine the cheapest path. So, a path which has lower value of f would be preferred over the one with higher value of f.

Now, using the above distance formula, we can figure out how A* is going to search the optimal path from Delhi to Hyderabad.

Straight line distance to Hyderabad:

  • Delhi: 20 , Mumbai: 12 , Lucknow: 16 , Kolkata: 8 , Hyderabad: 0
  • f(Delhi -> Mumbai) = 20 + 12 = 32
  • f(Delhi -> Lucknow) = 20 + 7 = 27

Image 2

Since Delhi to Lucknow has lower value of f, next path to expand is Lucknow to Kolkata.

f(Lucknow -> Kolkata) = 27 + 16 + 6 = 49.

Now we have two open states (Delhi -> Mumbai) and (Lucknow -> Kolkata). One with lowest value of f will be explored further (32 - Delhi -> Mumbai).

f(Mumbai -> Hyderabad) = 32 + 12 + 8 = 52

Next path to examine is (Delhi -> Lucknow -> Kolkata).

f(Kolkata -> Hyderabad): 49 + 8 + 9 = 66

Now that it has reached to the destination, and it has cheapest path among possible one is one from Delhi -> Mumbai -> Hyderabad. It will backtrack and declare this path as an optimal path.

One thing worth mentioning here is it does not expand all possible paths to the destination.

It always expands those one that seems optimal. For example, if there would have been a path from Kolkata -> Bhubaneswar -> Hyderabad and total cost reaching to Kolkata -> Bhubaneswar > 52, A* won’t even bother to examine the path at all. It knows that there exist a path to the final destination with f value = 52 and f value to Bhubaneswar is more than 52.

8/15 Puzzle

So how does 8/15 puzzle can be solved using this path finding algorithm?

Let's talk about 8 puzzle – simple sliding tiles on a 3x3 grid. You are allowed to move along with empty block, one step at a time. The puzzle is said to be solved, when it has sequential arrangement of the numbers.

So you have a start state (some random arrangement), and then a final state to reach.

Image 3

<shape id="Picture_x0020_12" style="width: 408.75pt; height: 211.5pt; visibility: visible;" type="#_x0000_t75" o:spid="_x0000_i1025"><imagedata src="file:///C:\Users\tiwarisu\AppData\Local\Temp\msohtmlclip1\01\clip_image003.png">

This is how you start solving the puzzle:

  1. Get the first state, which is your start state.
  2. Get all the possible states in which puzzle can be.
  3. Add these new states in open state list
  4. Add processed sate in the closed list
  5. Pick the next state which has the lowest cost in the open list
  6. Start repeating the steps from 1 to 6 unless you are into the final state, or no more states to examine (in this case, no solution exists).
  7. Once you have the final state, backtrack to the start node and that would be the optimal path to find the solution.

So what should be the g and h cost for this problem?

Since each time you just move one tile by one block – you can say actual move cost (g) is 1 from moving one state to another.

For 8 puzzle, total states that grid could be is !9/2 = 181,440. So you really need an optimal way to determine you are reaching towards the goal and without exploring unnecessary states.

There are two common h cost (it is known as Heuristic cost):

  1. Number of misplaced tiles – you can count the number of tiles which are misplaced, for a particular sate. When you are into final sate, h = 0.
  2. Sum of distances of the tiles from their actual positions (Manhattan distance) – sum of horizontal and vertical distances, for each tile.

2nd heuristic converges faster than the first one.

For implementation –

  1. You need to maintain the parent information to maintain the tree so that it can be backtracked.
  2. Also, you need to maintain a list of open and closed nodes so that you won’t examine the one which have been examined earlier and avoid falling in loop.
  3. You probably want to maintain the open nodes using Min Priority Queue data structure so that you can get the next state to examine quickly. It can be done without Min Priority Queue as well – but that would be too slow.
  4. You also need Hash tables to quickly find closed / open nodes.

I have implemented this in C#. you need .NET 4.0 installed on your machine to run the application

You can shuffle the arrangements and change the heuristic from the menu. On average, it’s taking ~44 seconds (using misplaced tiles heuristic) to tell if no solution exists for the arrangement (i.e. no way this puzzle can be solved).
One of my friends told me that it’s taking ~9 seconds to converge in this case, so I assume I have a pathetic system.

And last thing – I didn’t lie when I added 15 puzzle in the list. Same code can be used. In fact, you just need to change the grid from 3x3 to 4x4. But this is too slow for 15 puzzle. 15 puzzle can be in 10^13 states, which is too slow for A* algorithm to handle. There exists a better version of it; I will talk, when I have it.

Revised code:

I have optimized code to use indexed min priority queue. This is to speed-up the lookup and removal of the state from the min priority queue.

This code is taking ~3.85 seconds to converge if there is no solution for the puzzle, which is ~11 times faster than previous version.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer CLSA Ltd
Hong Kong Hong Kong
A software developer, working as a Trading Algorithm developer in CLSA. I have been in software industry since November, 2007. I have experience in .NET technologies, C#, C, Java, trading algorithms, machine learning and AI.

Comments and Discussions

 
QuestionNot working!!!!!! Pin
eliav maman 12329-Dec-18 11:02
eliav maman 12329-Dec-18 11:02 
AnswerRe: Not working!!!!!! Pin
Sudhir Tiwari18-Jan-22 19:58
Sudhir Tiwari18-Jan-22 19:58 
QuestionHwo to solve this one? Pin
Son Nguyen27-Oct-17 5:08
Son Nguyen27-Oct-17 5:08 
Generalhello Tiwari Pin
alcitect9-Nov-15 21:26
alcitect9-Nov-15 21:26 
GeneralRe: hello Tiwari Pin
Sudhir Tiwari20-Dec-15 0:50
Sudhir Tiwari20-Dec-15 0:50 
GeneralRe: hello Tiwari Pin
alcitect15-Feb-16 7:17
alcitect15-Feb-16 7:17 
Questioncheck for solvable Pin
Member 1041037421-Nov-13 9:54
Member 1041037421-Nov-13 9:54 
AnswerRe: check for solvable Pin
Respati Jenar Rahardy21-Nov-13 17:14
Respati Jenar Rahardy21-Nov-13 17:14 
QuestionModify to 15 Pin
ivelinu11-Nov-13 2:26
ivelinu11-Nov-13 2:26 
AnswerRe: Modify to 15 Pin
Sudhir Tiwari20-Nov-13 1:13
Sudhir Tiwari20-Nov-13 1:13 
GeneralRe: Modify to 15 Pin
ivelinu20-Nov-13 3:08
ivelinu20-Nov-13 3:08 
QuestionDiscussion 8/15 Puzzle using A* (A Star) Algorithm in Visual C# Pin
Respati Jenar Rahardy31-Oct-13 15:22
Respati Jenar Rahardy31-Oct-13 15:22 
AnswerRe: Discussion 8/15 Puzzle using A* (A Star) Algorithm in Visual C# Pin
Sudhir Tiwari20-Nov-13 1:06
Sudhir Tiwari20-Nov-13 1:06 
AnswerRe: Discussion 8/15 Puzzle using A* (A Star) Algorithm in Visual C# Pin
Sudhir Tiwari18-Jan-22 20:13
Sudhir Tiwari18-Jan-22 20:13 
Suggestionthanls Pin
era ahmadian16-Aug-13 9:12
era ahmadian16-Aug-13 9:12 
GeneralMy vote of 4 Pin
Boksa198717-Jul-13 21:19
Boksa198717-Jul-13 21:19 
GeneralMy vote of 5 Pin
Member 373058713-Jul-13 22:59
Member 373058713-Jul-13 22:59 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.