# 8-puzzle code executes infinitely.



## ashwin (Oct 25, 2012)

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. <br>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. I also gave this input 





> `{0,5,7,6,8,1,2,4,3}`


. It took about `10 seconds` and gave a result with *26 moves*. But the applet gave a result with *`24 moves`* in `0.0001 seconds` with `A*`. I do not understand what is wrong with the code because it looks perfect. I have been trying to figure this out for the past two days. I had first posted this on StackOverflow. Did not get any reply there.<br>


----------
*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`. The `compareTo()`
   function is implemented in the `EightPuzzle` class.
 - The input to the program can be changed by changing the value of `p1d` in the `main()`          function of `proj1` 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*<br>
While debugging I noticed that as nodes are expanded, the new nodes, after sometime, all have a heuristic - *`f_n`* as *`11`* or *`12`*. They never seem to decrease. So after sometime all the states in the `PriorityQueue(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?
*EDIT2*
This is the snippet(in p*roj1-astar()*) where the infinite looping happening. *openset* is the PriorityQueue containing unexpanded nodes and *closedset* is the LinkedList containing expanded nodes.<br>






```
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);
                                }              
                        }
                   
                }
```


*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 goal position
                // calculate how many positions it needs to move to get into that position
                {
                        int gn = 0;
                        int row = 0;
                        int col = 0;
                        for(int i = 0; i < list.length; i++)
                        {
                                if(list[i] != 0)
                                {
                                        row = list[i] / 3;
                                        col = list[i] % 3;
                                        row = Math.abs(row - (i / 3));
                                        col = Math.abs(col - (i % 3));
                                        gn += row;
                                        gn += col;
                                }
                               
                        }
                        return gn;
                }
        
                public String toString()
                {
                        String x = "";
                        for(int i = 0; i < this.puzzle.length; i++){
                                x += puzzle[i] + " ";
                                if((i + 1) % 3 == 0)
                                        x += "\n";
                        }
                        return x;
                }
                public int compareTo(Object input) {
                       
                       
                        if (this.f_n < ((EightPuzzle) input).getF_n())
                                return -1;
                        else if (this.f_n > ((EightPuzzle) input).getF_n())
                                return 1;
                        return 0;
                }
               
                public boolean equals(EightPuzzle test){
                        if(this.f_n != test.getF_n())
                                return false;
                        for(int i = 0 ; i < this.puzzle.length; i++)
                        {
                                if(this.puzzle[i] != test.puzzle[i])
                                        return false;
                        }
                        return true;
                }
                public boolean mapEquals(EightPuzzle test){
                        for(int i = 0 ; i < this.puzzle.length; i++)
                        {
                                if(this.puzzle[i] != test.puzzle[i])
                                        return false;
                        }
                        return true;
                }
        
        }
```

proj1
-----


```
import java.util.*;
    
    public class proj1 {
    
            /**
             * @param args
             */
           
            public static void main(String[] args) {
                   
                   
                    int[] p1d = {1, 4, 2, 3, 0, 5, 6, 7, 8};
                    int hueristic = 2;
                    EightPuzzle start = new EightPuzzle(p1d, hueristic, 0);
                    int[] win = { 0, 1, 2,
                                              3, 4, 5,
                                              6, 7, 8};
                    EightPuzzle goal = new EightPuzzle(win, hueristic, 0);
                   
                    astar(start, goal);
    
                   
    
            }
           
            public static void astar(EightPuzzle start, EightPuzzle goal)
            {
                    if(start.inversions() % 2 == 1)
                    {
                            System.out.println("Unsolvable");
                            return;
                    }
    //              function A*(start,goal)
    //           closedset := the empty set                 // The set of nodes already evaluated.
                    LinkedList<EightPuzzle> closedset = new LinkedList<EightPuzzle>();
    //           openset := set containing the initial node // The set of tentative nodes to be evaluated. priority queue
                    PriorityQueue<EightPuzzle> openset = new PriorityQueue<EightPuzzle>();
    
                    openset.add(start);
                   
    
                    while(openset.size() > 0){
    //               x := the node in openset having the lowest f_score[] value
                            EightPuzzle x = openset.peek();
    
    //               if x = goal
                            if(x.mapEquals(goal))
                            {
    //                   return reconstruct_path(came_from, came_from[goal])
                                     Stack<EightPuzzle> toDisplay = reconstruct(x);
                                     System.out.println("Printing solution... ");
                                     System.out.println(start.toString());
                                     print(toDisplay);
                                     return;
                                     
                            }
    //               remove x from openset
    //               add x to closedset
                            closedset.add(openset.poll());
                            LinkedList <EightPuzzle> neighbor = x.getChildren();
    //               foreach y in neighbor_nodes(x)                
                            while(neighbor.size() > 0)
                            {
                                    EightPuzzle y = neighbor.removeFirst();
    //                   if y in closedset
                                    if(closedset.contains(y)){
    //                       continue
                                            continue;
                                    }
    //                   tentative_g_score := g_score[x] + dist_between(x,y)
    //      
    //                   if y not in openset
                                    if(!closedset.contains(y)){
    //                       add y to openset
                                            openset.add(y);
    //                      
                                    }
    //                 
                            }
    //               
                    }
            }
    
            public static void print(Stack<EightPuzzle> x)
            {
                    while(!x.isEmpty())
                    {
                            EightPuzzle temp = x.pop();
                            System.out.println(temp.toString());
                    }
            }
    
            public static Stack<EightPuzzle> reconstruct(EightPuzzle winner)
            {
                    Stack<EightPuzzle> correctOutput = new Stack<EightPuzzle>();
                   
                    while(winner.getParent() != null)
                    {
                    correctOutput.add(winner);
                    winner = winner.getParent();
                    }
    
                    return correctOutput;
            }
           
            }
```


----------



## temp02 (Oct 26, 2012)

You can debug the code or stick some log/printlns and see in what state/place does it get stuck.

Also you have the complete source code of that applet available on that very same page, you can compare how are the algorithms implemented between the two solutions/projects. I mean, you weren't expecting that others study and fix code (that's not even yours) when you don't even try to, at least, print a list of states/transitions.


----------



## ashwin (Oct 27, 2012)

temp02 said:


> You can debug the code or stick some log/printlns and see in what state/place does it get stuck.
> 
> Also you have the complete source code of that applet available on that very same page, you can compare how are the algorithms implemented between the two solutions/projects. I mean, you weren't expecting that others study and fix code (that's not even yours) when you don't even try to, at least, print a list of states/transitions.


Please see the two edits. I have also posted a link to the eight-puzzle game at the top.


----------



## Aquinus (Oct 27, 2012)

This looks weird.


```
//                   if y not in openset
                if (!closedset.contains(y)) {
                    //                       add y to openset
                    openset.add(y);
                }
```

Comment says openset and code says closedset. 

Some data structure usage is kind of weird. You may want to just use the script to understand what is going on then re-write it. Keeping the good things about it and tossing/replacing the bad.


----------



## ashwin (Oct 27, 2012)

Aquinus said:


> This looks weird.
> 
> 
> ```
> ...


See, the logic is what ever has not been examined(i.e not in *closedset*) has to be examined; hence added to *openset*. And which data structure do you think is not appropriate here? Since this is an A* implementation, I feel *PriorityQueue* is the best choice for *openset*. The *closedset* can contain the elements in any order. So do you want me to try any other data structure, if you feel that *LinkedList* is not appropriate for it?


----------



## Kreij (Oct 27, 2012)

Without running this in a debugger or seeing actual values as the code executes, this is a bit hard to do in one's head. lol

Given that the first code snippet you posted is where the infinite loop is occurring, it looks one of the two while loops is never returning a false value and exiting.

The While(neighbor.size() > 0) loop doesn't look like the problem as you are removing the head of the list and never putting anything back into it in the loop.

This would cause me to look at the openset.size() value as the code is running. If a situation occurs where after you remove the head of the list (with the openset.poll() call) another node is always being added by the openset.add() call inside the nested while loop, the size of openset would never reach zero and thus loop forever.

I could, of course, be totally confused and wrong.


----------



## ashwin (Oct 27, 2012)

Kreij said:


> Without running this in a debugger or seeing actual values as the code executes, this is a bit hard to do in one's head. lol
> 
> Given that the first code snippet you posted is where the infinite loop is occurring, it looks one of the two while loops is never returning a false value and exiting.
> 
> ...


Thanks for at least going through the code and trying to understand it. you are right about the fact that when ever a node is removed(with the openset.poll() call), a new node is added. *BUT* a new node is only added only if 
	
	



```
if(!closedset.contains(y))
```
 is true. So after some point of time, all the nodes would have been visited and present in *closedset* and none of the nodes would be added to *openset*. One another thing, since we are using an admissible *heuristic* of *manhattan distance*, the solution should be found long before visiting all the nodes i.e this 
	
	



```
if(x.mapEquals(goal))
```
 should execute.


----------



## Kreij (Oct 27, 2012)

I agree that at some point all the nodes _should_ be removed from openset, but is that actually occurring?
It would be easy enough to test by outputting the size of openset each time the loop runs.


----------



## ashwin (Oct 27, 2012)

Kreij said:


> I agree that at some point all the nodes _should_ be removed from openset, but is that actually occurring?
> It would be easy enough to test by outputting the size of openset each time the loop runs.


Size of *openset* - 430224 and counting. I don't know how this is possible because the maximum number of permutations required are* 9!=362880*. I am not able to find out where the mistake is. It is perfect : 


An element checked whether it is the goal state.


If not it is added to the *closedset* and expanded.

The expanded nodes are checked to see if they are present in *closedset*. If not they are added to *openset*
The above steps go on till *openset* is empty or till the goal state has been found.


----------



## Kreij (Oct 27, 2012)

If openset is larger than the max possible node permutations, then the code must be putting duplicate nodes in openset for some reason.
*Why* is the question. 

It may be that your code is technically correct, but one of the underlying types (like PriorityQueue) is returning values that are not expected due to the way its behavior is coded.
Wouldn't be the first time I've seen something like that.


----------



## ashwin (Oct 27, 2012)

Found out the problem with some help from @Kreij. This is the condition that is used to check if a node is present in *closedset*

```
if(!closedset.contains(y))
```
A linkedlist(closedset) executes the contains() by calling the equals() of the class, in this case *EightPuzzle*. The equals function in EightPuzzle is defined as follows 

```
public boolean equals(EightPuzzle test){
        	
                if(this.f_n != ((EightPuzzle)test).getF_n())
                       return false;
        	//System.out.println("in equals");
                for(int i = 0 ; i < this.puzzle.length; i++)
                {
                        if(this.puzzle[i] != ((EightPuzzle)test).puzzle[i])
                                return false;
                }
                return true;
        }
```
But this function was never called because if you want to override the equals() of *Object* class the correct signature should be
	
	



```
public boolean equals(Object test)
```
. 
One more change required - comment the first two lines of the *equals()*

I got the answer. But the code still takes 25-30 seconds for some inputs. This is not expected with A*. If someone has an idea, how to improve the performance. please do tell me. Thanks


----------



## Aquinus (Oct 27, 2012)

I just read through some of this code and some of it is pretty poor style. I'm re-writing parts of it to see if it makes a difference on performance. I will upload what I end up with when I'm done. You really got me thinking about this now, thanks a lot. I program at work and now I'm (still) programming in my free time. Doh! 

By the way

```
int[] p1d = {0,5,7,6,8,1,2,4,3};
```
takes 10 seconds to run on my 3820 @ 4.5ghz.


----------



## Aquinus (Oct 27, 2012)

Alright, I finished re-factoring your code and here is what I came up with. I was able to cut runtime in half from 10 seconds to 5 seconds on my rig. Let me know how it works for you. I attached a zip with the .java files. I think I could potentially make it go faster but I didn't want to commit too much more time to this and half the speed is a nice boost. Cheers, hope this helps.


----------



## ashwin (Oct 28, 2012)

Aquinus said:


> Alright, I finished re-factoring your code and here is what I came up with. I was able to cut runtime in half from 10 seconds to 5 seconds on my rig. Let me know how it works for you. I attached a zip with the .java files. I think I could potentially make it go faster but I didn't want to commit too much more time to this and half the speed is a nice boost. Cheers, hope this helps.


Are you getting any output for *{8,2,7,5,1,6,3,0,4}*?


----------



## ashwin (Oct 28, 2012)

Aquinus said:


> Alright, I finished re-factoring your code and here is what I came up with. I was able to cut runtime in half from 10 seconds to 5 seconds on my rig. Let me know how it works for you. I attached a zip with the .java files. I think I could potentially make it go faster but I didn't want to commit too much more time to this and half the speed is a nice boost. Cheers, hope this helps.


Your solution works! make these changes. Just change comment the first two line of *equals* and yo did not change the 
	
	



```
public void equals(EightPuzzle test)
```
 to 
	
	



```
public void equals(Object test)
```
Now it executes withing 1 second for all the inputs. Superb optimization. Thanks
But I would like to get things clarified.
You have made the following changes : 


in *astar() you changed 
	
	




		Code:
	

EightPuzzle x = openset.seek();

 to
	
	




		Code:
	

 EightPuzzle x = openset.poll();

* .This way you could removed the burden of first *peeking* and then *polling*.
 

in *astar()* you converted  
	
	



```
if(closedset.contains(y)){
                                         continue;
                               }
                               if(!closedset.contains(y)){
                                        openset.add(y);
                              }
```
to
	
	



```
if (closedset.contains(y)) {
                   continue;
               }
               openset.add(y);
```
This removed the burden of calling contains two times. Instead you called it only once.

*BUT* in *public LinkedList getChildren()* of *EightPuzzle* you just kept one EightPuzzle variable called *unified* instead of *up,right,down,left*. And you changed the *if* statements to *do while*. Did you make these two change to save memory or does it also make the execution faster? If yes how did these two changes make the execution faster?
4)


----------



## Aquinus (Oct 28, 2012)

ashwin said:


> Your solution works! make these changes. Just change comment the first two line of *equals* and yo did not change the
> 
> 
> 
> ...



the getChildren changes actually wasn't the biggest boost. The biggest boost was changing the PriorityQueue and LinkedList checks to isEmpty() instead of size(). isEmpty runs in constant time because it only has to check to see if something is there. .size() runs in linear time because it has to go through every element in the collection. That change actually resulted in the majority of the performance boost.

Yes, I used only one variables and removed a number of extra clone statements. That was less of a performance measure and more of a "reduce this code by half" move. It's less readable but I believe less resources are used here even if performance isn't impacted by this change. Also keep in mind that your old "size()" checks also were nested so instead of actually running in linear time it would be much closer to exponential time.

Changing openset.seek and poll() to just poll makes sense because there is never an instance where you don't end up taking an item off of the queue. Also peek makes a copy so it actually does more than just give you the value so it takes longer to run.

This is the biggest boost here is.

```
while (!openset.isEmpty()) {
// And
while (!neighbor.isEmpty()) {
```
Instead of

```
while (openset.size() > 0) {
// And
while (neighbor.size() > 0) {
```

I made some style changes that have nothing to do with performance in some places. It's not like the files were exceedingly huge so I just re-factored it as a whole.

Why did you do this?

```
public void equals(Object test)
```
The first thing it needs expects the object to be an EightPuzzle object because it calls a method on it. mapEquals can be changed safely, but equals can not.


----------



## ashwin (Oct 28, 2012)

Aquinus said:


> the getChildren changes actually wasn't the biggest boost. The biggest boost was changing the PriorityQueue and LinkedList checks to isEmpty() instead of size(). isEmpty runs in constant time because it only has to check to see if something is there. .size() runs in linear time because it has to go through every element in the collection. That change actually resulted in the majority of the performance boost.
> 
> Yes, I used only one variables and removed a number of extra clone statements. That was less of a performance measure and more of a "reduce this code by half" move. It's less readable but I believe less resources are used here even if performance isn't impacted by this change. Also keep in mind that your old "size()" checks also were nested so instead of actually running in linear time it would be much closer to exponential time.
> 
> ...


Okay, now I understood. size() was actually iterating through the whole list and as the list got bigger and bigger, the size() took more time. 

```
public void equals(EightPuzzle test)
```
 is never called. You can check it by printing something inside the function. Only after I changed it to 
	
	



```
public void equals(Object test)
```
, the function was being called. I think the reason is when you do 
	
	



```
public void equals(EightPuzzle test)
```
, you are not overriding the 
	
	



```
public void equals(Object test)
```
  because the signature does not match. Hence when contains() is executed, the default equals function is called, which I think compares the two values by calling *hashcode()* and we have not overridden hashcode() also.


----------



## Aquinus (Oct 28, 2012)

ashwin said:


> Okay, now I understood. size() was actually iterating through the whole list and as the list got bigger and bigger, the size() took more time.



Bingo, you go from linear time to constant time. Huge performance benefits for large data sets.


ashwin said:


> is never called. You can check it by printing something inside the function. Only after I changed it to
> Code:
> public void equals(Object test)
> , the function was being called. I think the reason is when you do
> ...


Ahh, right. The object class should be smart enough to use all of the object attributes, but you may want to override it since it could most likely be executed faster. That makes sense, I missed that one. I only spent a little while looking through and editing code.


----------



## ashwin (Oct 28, 2012)

Aquinus said:


> I only spent a little while looking through and editing code.


..and you solved the problem. Wonder what you would have done had you spent more time. LOL


----------



## Aquinus (Oct 28, 2012)

ashwin said:


> ..and you solved the problem. Wonder what you would have done had you spent more time. LOL



I'm a system admin and developer at work. I write code just about every day. You get good at something you do a lot


----------



## 3870x2 (Oct 29, 2012)

Aquinus said:


> I'm a system admin and developer at work. I write code just about every day. You get good at something you do a lot



Intel analyst / database administrator here, I just seem to get more stupid.

Maybe its because I have to use .net...


----------

