I am looking for a solution to 8-puzzle problem using the A* Algorithm
. I found this project on the internet. Please see the files - proj1
and EightPuzzle
. The proj1 contains the entry point for the program(the main()
function) and EightPuzzle describes a particular state of the puzzle. Each state is an object of the 8-puzzle.
I feel that there is nothing wrong in the logic. But it loops forever for these two inputs that I have tried : {8,2,7,5,1,6,3,0,4}
and {3,1,6,8,4,5,7,2,0}
. Both of them are valid input states. What is wrong with the code?
Note
- For better viewing copy the code in a Notepad++ or some other text editor(which has the capability to recognize java source file) because there are lot of comments in the code.
- Since A* requires a heuristic, they have provided the option of using
manhattan distance and a heuristic that calculates the number of
misplaced tiles. And to ensure that the best heuristic is executed
first, they have implemented a
PriorityQueue
. ThecompareTo()
function is implemented in theEightPuzzle
class. - The input to the program can be changed by changing the value of
p1d
in themain()
function ofproj1
class. - The reason I am telling that there exists solution for the two my above inputs is because the applet here solves them. Please ensure that you select 8-puzzle from the options in the applet.
EDIT1
I gave this input{0,5,7,6,8,1,2,4,3}
. It took about10 seconds
and gave a result with 26 moves. But the applet gave a result with24 moves
in0.0001 seconds
withA*
.
EDIT2
While debugging I noticed that as nodes are expanded, the new nodes, after sometime, all have a heuristic -f_n
as11
or12
. They never seem to decrease. So after sometime all the states in thePriorityQueue(openset)
have a heuristic of 11 or 12. So there is not much to choose from, to which node to expand. As the least is 11 and the highest is 12. Is this normal?
EDIT3
This is the snippet(in proj1-astar()) where the infinite looping happening. openset is the PriorityQueue containing unexpanded nodes and closedset is the LinkedList containing expanded nodes.
while(openset.size() > 0){
EightPuzzle x = openset.peek();
if(x.mapEquals(goal))
{
Stack<EightPuzzle> toDisplay = reconstruct(x);
System.out.println("Printing solution... ");
System.out.println(start.toString());
print(toDisplay);
return;
}
closedset.add(openset.poll());
LinkedList <EightPuzzle> neighbor = x.getChildren();
while(neighbor.size() > 0)
{
EightPuzzle y = neighbor.removeFirst();
if(closedset.contains(y)){
continue;
}
if(!closedset.contains(y)){
openset.add(y);
}
}
}
EDIT4
I have got the cause of this infinite loop. See my answer. But it takes about 25-30 seconds to execute, which is quite a long time. A* should do much faster than this. the applet does this in 0.003 seconds. I will award the bounty for improving the performance.
For quick reference I have pasted the the two classes without the comments :
EightPuzzle
import java.util.*;
public class EightPuzzle implements Comparable <Object> {
int[] puzzle = new int[9];
int h_n= 0;
int hueristic_type = 0;
int g_n = 0;
int f_n = 0;
EightPuzzle parent = null;
public EightPuzzle(int[] p, int h_type, int cost)
{
this.puzzle = p;
this.hueristic_type = h_type;
this.h_n = (h_type == 1) ? h1(p) : h2(p);
this.g_n = cost;
this.f_n = h_n + g_n;
}
public int getF_n()
{
return f_n;
}
public void setParent(EightPuzzle input)
{
this.parent = input;
}
public EightPuzzle getParent()
{
return this.parent;
}
public int inversions()
{
/*
* Definition: For any other configuration besides the goal,
* whenever a tile with a greater number on it precedes a
* tile with a smaller number, the two tiles are said to be inverted
*/
int inversion = 0;
for(int i = 0; i < this.puzzle.length; i++ )
{
for(int j = 0; j < i; j++)
{
if(this.puzzle[i] != 0 && this.puzzle[j] != 0)
{
if(this.puzzle[i] < this.puzzle[j])
inversion++;
}
}
}
return inversion;
}
public int h1(int[] list)
// h1 = the number of misplaced tiles
{
int gn = 0;
for(int i = 0; i < list.length; i++)
{
if(list[i] != i && list[i] != 0)
gn++;
}
return gn;
}
public LinkedList<EightPuzzle> getChildren()
{
LinkedList<EightPuzzle> children = new LinkedList<EightPuzzle>();
int loc = 0;
int temparray[] = new int[this.puzzle.length];
EightPuzzle rightP, upP, downP, leftP;
while(this.puzzle[loc] != 0)
{
loc++;
}
if(loc % 3 == 0){
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 1];
temparray[loc + 1] = 0;
rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
rightP.setParent(this);
children.add(rightP);
}else if(loc % 3 == 1){
//add one child swaps with right
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 1];
temparray[loc + 1] = 0;
rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
rightP.setParent(this);
children.add(rightP);
//add one child swaps with left
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 1];
temparray[loc - 1] = 0;
leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
leftP.setParent(this);
children.add(leftP);
}else if(loc % 3 == 2){
// add one child swaps with left
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 1];
temparray[loc - 1] = 0;
leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
leftP.setParent(this);
children.add(leftP);
}
if(loc / 3 == 0){
//add one child swaps with lower
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 3];
temparray[loc + 3] = 0;
downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
downP.setParent(this);
children.add(downP);
}else if(loc / 3 == 1 ){
//add one child, swap with upper
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 3];
temparray[loc - 3] = 0;
upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
upP.setParent(this);
children.add(upP);
//add one child, swap with lower
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 3];
temparray[loc + 3] = 0;
downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
downP.setParent(this);
children.add(downP);
}else if (loc / 3 == 2 ){
//add one child, swap with upper
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 3];
temparray[loc - 3] = 0;
upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
upP.setParent(this);
children.add(upP);
}
return children;
}
public int h2(int[] list)
// h2 = the sum of the distances of the tiles from their goal positions
// for each item find its g