Share this post

Submit to DeliciousSubmit to DiggSubmit to FacebookSubmit to Google BookmarksSubmit to StumbleuponSubmit to TechnoratiSubmit to TwitterSubmit to LinkedIn
   

The 8-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing and the player tries to get the tile numbers in some order to finish the puzzle.

This program is solving 8-puzzle with A* algorithm that uses manhattan distances heuristic and shows the answer in a nice graphical way and it's very good for educational purposes.

The code is very simple to develop in C# language.

First I want to share some details about the source code of the program and how it is written, then I will speak about how the program works.

To download the source code and see the details about the program click read more.

 

1 - Source Code:

If you download the source code from here and look at the solution(it is written in visual studio 2010 ) you can see that the solution contains two projects:

1. Astar :

Astar is a console application that can solve n-puzzle programs and serves as the mind of the program. Here actually I wrote it first and then added the visual part to it later.

Ok now let's go into some details about it. It has 6 classes :

Heap: A min heap that sorts the states with their f score ( the root has always lowest f score ) and it's used for our A* fring (open set) to always get the best node efficiently.

State: A state is the condition of a system in a moment in time. Actually, the system goes from a state to another one with its actions. In A* algorithm, we calculate an f score for every state.

f=g+h, where h is the approximate distance from the current state to the goal and g is the exact distance we traveled from the first state to current state, you can see it as an int attribute in the class.

In our program, the state is a two dimension array that shows where every tile is. There is also an attribute called last action ( shows which action has been done last to reach this state ) - Kseted ( shows that is this state a valid state or not ) - g ( that shows the Manhattan distance between this state to goal ) - parent ( that stores the parent state of current state )

Actions: the actions we can do to a state like moving it to right-left-down-up ( if possible )

Problem: represents currently solving problem its first state its goal and some functions to help to solve the problem.

Astar: this is where all of the computations done actually it's the class that implements A* algorithm and solves the given problem.

2. Astarvisual: its the graphical interface of the program.

2 -Using The Program:

Using the program is very easy. You only set the first state and goal with drag and drop. Drag the tiles and drop them in the place you want them, "-" represents the empty cell. Then click solve. 

After the program solves the problem it will show you the best solution.

Here are some screenshots of the program. Click to see the actual size :

    

And it's a video that shows how the program can be used. If you can't see it download it here.

   
  
© geek brothers