This project was done as a part of academic study in subject "Artificial Intelligence" . I have attached the java source code of 8-puzzle solver. You can download it for free. This project was done in collaboration with my colleague 'Pushkar Shakya'. I have mentioned below few details including Introduction, Methodology, Algorithm used in this project that I learned after our thorough research.
8-puzzle is a very interesting and a well known problem in the field of Artificial Intelligence. It always has been an important subject in articles, books and become a part of course material in many universities. The 8-puzzle is also known as the sliding-block puzzle or tile-puzzle and is meant for a single user. 8-puzzle consists of 8 square tiles numbered 1 through 8 and one blank space on a 3 by 3 board. Moves of the puzzle are made by sliding an adjacent tile into the position occupied by the blank space, which has the effect of exchanging the positions of the tile and blank space. Only tiles that are horizontally or vertically adjacent (not diagonally adjacent) may be moved into the blank space. The objective of the game is to start from an initial configuration and end up in a configuration which the tiles are placed in ascending number order as shown in: figure 1 below.
Figure 1 Goal state of the 8-puzzle
HOW TO PLAY
The game can be played using the arrow keys. Up arrow slides a tile up into the empty space, left arrow slides a tile left into the empty space and so on. You can choose to solve it automatically by program. It will display the animation sliding the tiles and solve the 8 puzzle in least possible moves using AI.
METHODOLOGY
According to the authors Russel and Norvig in their book titled Artificial Intelligence: A Modern Approach, the average solution for a randomly generated 8-puzzle instance is about 22 steps. This figure is obtained by estimating the branching factor which is about 3 (when the empty tile is in the middle, there are four possible moves; when it is in a corner there are two; and when it is along an edge there are three). This means that an exhaustive search to depth 22 would look at about 322 ~ 3.1 x 1010 states. By keeping track of repeated states, it is possible to cut this down by a factor of about 170,000, because there are only 9!/2 = 181,440 distinct states that are reachable.
ALGORITHM
After a preliminary investigation of the heuristic search strategies we were able to figure out that A* algorithm is the best for the 8-puzzle problem. A* is the most widely used form of best first search algorithm which is an instance of Tree-Search or Graph-Search where a best node is expanded on the basis of an evaluation function f(n). Here, the evaluation function of each node is calculated as a sum of two functions g(n) and h(n) where, g(n) refers to the cost to reach the node n while h(n) is the cost to get from node n to the goal. A* algorithm is both optimal and complete. It is optimal in that sense h(n) is admissible and is never overestimated
to reach the goal and it is complete in that sense it guarantees to reach a solution whenever there is one.
The following pseudo code describes the A* algorithm:
function
A*(start,goal)
closedset := the empty set // The set of nodes
already evaluated.
openset := set containing the initial
node // The set of tentative nodes to be evaluated.
g_score[start] := 0 // Distance from
start along optimal path.
h_score[start] :=
heuristic_estimate_of_distance(start, goal)
f_score[start] := h_score[start] // Estimated total distance from
start to goal through y.
while
openset is not empty
x := the node in openset having the
lowest f_score[] value
if x = goal
return
reconstruct_path(came_from[goal])
remove x from openset
add x to closedset
foreach y in neighbor_nodes(x)
if y in closedset
continue
tentative_g_score := g_score[x] +
dist_between(x,y)
if y not in openset
add y to openset
tentative_is_better := true
elseif tentative_g_score <
g_score[y]
tentative_is_better := true
else
tentative_is_better := false
if tentative_is_better = true
came_from[y] := x
g_score[y] :=
tentative_g_score
h_score[y] :=
heuristic_estimate_of_distance(y, goal)
f_score[y] := g_score[y] +
h_score[y]
return failure
function reconstruct_path(current_node)
if came_from[current_node] is set
p =
reconstruct_path(came_from[current_node])
return (p + current_node)
else
return current_node
|
REFERENCE
1. Rich and Knight, Artificial Intelligence.
2. Russell and Norvig, Artificial Intelligence: A Modern approach,
3. A* search algorithm - Wikipedia, the free encyclopedia
4. Description and a solution strategy for the 8-puzzle from http://www.8puzzle.com/
5. G. Novak, CS 381K: Heuristic Search: 8 Puzzle, 26 Sep 07
6. An appealing Java applet from www.permadi.com/java/puzzle8/
Download the source code here : 8-Puzzle Solver (Java)
