0
I am trying to implement a Breadth First Search algorithm for 8puzzle. I am somehow not able to get in the `is(RequiredState(see))` condition where my search terminates. My program gets stuck in an infinite loop. I have put the repeating states in a state to prevent getting stuck in a loop, but somehow my program still gets stuck in a loop.

board.java

        public class board {
            public
                int[] square = new int[9];
            board()
            {
                for(int i=0;i<9;i++)
                {
                    square[i]=8-i;
                    square[8] = 0;


                }
            }
            int findBlankPos()
            {
                for(int i=0;i<square.length;i++)
                {
                    if(square[i]==0)
                    {
                        return i;
                    }
                }
                return 9;
            }
            static int size()
            {
                return 9;
            }
            void moveBlankUp(int blankpos)
            {
                square[blankpos] = square[blankpos-3];
                square[blankpos-3] = 0;
            }
            void moveBlankDown(int blankpos)
            {
                square[blankpos] = square[blankpos+3];
                square[blankpos+3] = 0;
            }
            void moveBlankRight(int blankpos)
            {
                square[blankpos] = square[blankpos+1];
                square[blankpos+1] = 0;
            }
            void moveBlankLeft(int blankpos)
            {
                square[blankpos] = square[blankpos-1];
                square[blankpos-1] = 0;
            }
            boolean canMoveUp(int blankpos)
            {
                if((blankpos==0)||(blankpos==1)||(blankpos==2))
                    return false;
                else
                    return true;
            }
            boolean canMoveDown(int blankpos)
            {
                if((blankpos==6)||(blankpos==7)||(blankpos==8))
                    return false;
                else
                    return true;
            }
            boolean canMoveRight(int blankpos)
            {
                if((blankpos==2)||(blankpos==5)||(blankpos==8))
                    return false;
                else
                    return true;
            }
            boolean canMoveLeft(int blankpos)
            {
                if((blankpos==0)||(blankpos==3)||(blankpos==6))
                    return false;
                else
                    return true;
            }
            void display()
            {
                for(int i=0;i<square.length;i++)
                {
                    if((i)%3==0)
                    {
                        System.out.println();
                    }
                    System.out.print(square[i] + " ");
                }
            }
            Integer getAt(int pos)
            {
                return square[pos];
            }
            void setAt(int pos,int value)
            {
                square[pos] = value;
            }
        }

puzzle.java

    import java.awt.List;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Set;


    public class puzzle {
        public static void main(String[] args)
        {
            board b = new board();
            Set<board> set = new HashSet<board>();
            b.display();
            Queue<board> queue = new LinkedList<board>();
            queue.add(b);
            /*b.setAt(4,0);
            b.setAt(8,4);
            b.display();
            System.out.println();
            AddChildrentoQueue(queue,b);*/

            //System.out.println(queue.);
            int itr=0;
            while(!queue.isEmpty())
            {
                itr++;
                System.out.println(itr);
                board see = queue.peek();
                //System.out.println(count);
                if(!(set.contains(see)))
                {
                    set.add(see);
                    //see.display();
                    //System.out.println();
                    if(isRequiredState(see))
                    {
                        queue.peek().display();
                        System.out.println("End it with a Bang");
                        break;
                    }
                        AddChildrentoQueue(queue,queue.peek());
                        //System.out.println(queue.size());
                        if(itr==1)
                            break;

                }
                queue.remove();
            }
            //System.out.println(isRequiredState(b));

        }

        private static boolean isRequiredState(board peek) {
            // TODO Auto-generated method stub
            String state="";
            for(int i=0;i<peek.size();i++)
            {
                String temp = (String)peek.getAt(i).toString();
                //System.out.println(temp);
                state = state + temp;
            }
            //System.out.println(state);
            if(state.equals("123456780"))
            {
                return true;
            }
            return false;
        }

        private static void AddChildrentoQueue(Queue<board> queue, board b) {
            // TODO Auto-generated method stub
            board d;
            if(b.canMoveUp(b.findBlankPos()))
            {
                d = getClone(b);
                d.moveBlankUp(b.findBlankPos());
                d.display();
                System.out.println();
                queue.add(d);
            }
            if(b.canMoveDown(b.findBlankPos()))
            {
                d = getClone(b);
                d.moveBlankDown(b.findBlankPos());
                d.display();
                System.out.println();
                queue.add(d);
            }
            if(b.canMoveRight(b.findBlankPos()))
            {
                d = getClone(b);
                d.moveBlankRight(b.findBlankPos());
                d.display();
                System.out.println();
                queue.add(d);
            }
            if(b.canMoveLeft(b.findBlankPos()))
            {
                d = getClone(b);
                d.moveBlankLeft(b.findBlankPos());
                d.display();
                System.out.println();
                queue.add(d);
            }


        }
        static board getClone(board b)
        {
            board c = new board();
            for(int i=0;i<c.size();i++)
            {
                c.setAt(i,b.getAt(i));
            }
            return c;
        }


    }

So this is how i finally solved my problem .As i worked on the problem i found out that when i compared that whether the element checked is in the set or not,it actually compared the address values but not the objects as was required and that is why i was unable to come out of the infinite loop because every time a new address was generated.Hence instead of comparing the objects using a set,I created a set of strings that compared the configuration of the object stored as strings and put in a set.Thanks a lot for making me find the problem guyz..cheers!!!

import java.awt.List;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;


public class puzzle {
    public static void main(String[] args)
    {
        board b = new board();
        Set<String> set = new HashSet<String>();
        b.display();
        Queue<board> queue = new LinkedList<board>();
        queue.add(b);
        /*b.setAt(4,0);
        b.setAt(8,4);
        b.display();
        System.out.println();
        AddChildrentoQueue(queue,b);*/

        //System.out.println(queue.);
        //int itr=0;
        while(!queue.isEmpty())
        {
            //itr++;
            board see = queue.peek();
            String check = getSequence(queue.peek());
            //System.out.println(itr);
            //System.out.println(check);
            if(!(set.contains(check)))
            {
                set.add(check);
                //see.display();
                //System.out.println();
                if(isRequiredState(see))
                {
                    queue.peek().display();
                    System.out.println("End it with a Bang");
                    break;
                }
                    AddChildrentoQueue(queue,queue.peek());
                    //System.out.println(queue.size());
            }
            queue.remove();
        }
        //System.out.println(isRequiredState(b));

    }

    private static boolean isRequiredState(board peek) {
        // TODO Auto-generated method stub
        String state = getSequence(peek);
        //System.out.println(state);
        if(state.equals("123456780"))
        {
            return true;
        }
        return false;
    }


    private static String getSequence(board peek) {
        // TODO Auto-generated method stub
        String state="";
        for(int i=0;i<peek.size();i++)
        {
            String temp = (String)peek.getAt(i).toString();
            //System.out.println(temp);
            state = state + temp;
        }
        return state;
    }

    private static void AddChildrentoQueue(Queue<board> queue, board b) {
        // TODO Auto-generated method stub
        board d;
        if(b.canMoveUp(b.findBlankPos()))
        {
            d = getClone(b);
            d.moveBlankUp(b.findBlankPos());
            d.display();
            System.out.println();
            queue.add(d);
        }
        if(b.canMoveDown(b.findBlankPos()))
        {
            d = getClone(b);
            d.moveBlankDown(b.findBlankPos());
            d.display();
            System.out.println();
            queue.add(d);
        }
        if(b.canMoveRight(b.findBlankPos()))
        {
            d = getClone(b);
            d.moveBlankRight(b.findBlankPos());
            d.display();
            System.out.println();
            queue.add(d);
        }
        if(b.canMoveLeft(b.findBlankPos()))
        {
            d = getClone(b);
            d.moveBlankLeft(b.findBlankPos());
            d.display();
            System.out.println();
            queue.add(d);
        }


    }
    static board getClone(board b)
    {
        board c = new board();
        for(int i=0;i<c.size();i++)
        {
            c.setAt(i,b.getAt(i));
        }
        return c;
    }


}
user2249875
  • 1
  • 2
  • 4
    Why not use a debugger and find out for yourself what it is that's going wrong? – NPE Apr 05 '13 at 16:50
  • 1
    Just a few simple things: all classes should begin with an uppercase letter, methods and constructors should usually not use the default access modifier, `public` should probably be used instead. – John Apr 05 '13 at 16:55
  • 1
    Without looking at the code, I assume you're never marking cells as visited. Think about why this is necessary. – G. Bach Apr 05 '13 at 17:43
  • @G.Bach-I am putting all the new cells in a set.And when i reach a new cell,i check whether it is in the set or not.If it is in the set i remove it from the queue directly without taking its children as they have been checked before.Moreover ..only when it is a new cell i take that into account. – user2249875 Apr 05 '13 at 18:08
  • @user2249875 Yes you are adding them to a set, but when you put new children into the queue, you use clones, i.e. new objects. They most likely don't hash to the same value since you haven't implemented `hashCode()` for `board`, so the check whether a board is already in the hashset doesn't tell you whether a semantically equivalent board is already in the set, but only whether the specific board you're checking for is already in the set. This will not suffice if you keep generating new instances of `board` that have the same content but don't hash the same. – G. Bach Apr 05 '13 at 20:05
  • See how the [default hashCode()](http://stackoverflow.com/a/4179011/1086871) that `Object` has works. – G. Bach Apr 05 '13 at 20:07

1 Answers1

0

The problem with using a hashing data structure without implementing a hashCode() that is consistent with equals() was pointed out in the comments, so here's a suggestion what you could use as a hashCode(): consider the cells of the board as number with 0 <= i <= 8 from top left to bottom right.

@Override
public int hashCode() {
    int hashCode = 0;

    for(int i = 0; i < square.size; i++) {
        hashcode += (square[i] << (3 + i % 2)*i);
    }
}

You'll end up with an int that somewhat crudely, but still sensibly derives from the state of the board that is relevant to your concerns, and certainly consistent with an equals() that checks whether all cells of the two boards being compared hold the same value. Make sure that if you do implement equals() and hashCode(), you do it consistently, which roughly means

A.equals(B) -> A.hashCode() == B.hashCode()

where -> is the logical implication.

G. Bach
  • 3,869
  • 2
  • 25
  • 46