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


    }

所以这就是我最终解决问题的方式。当我处理这个问题时，我发现当我比较检查的元素是否在集合中时，它实际上比较的是地址值而不是所需的对象，并且这就是为什么我无法摆脱无限循环的原因，因为每次生成一个新地址时。因此，我没有使用一组比较对象，而是创建了一组字符串来比较存储为字符串的对象的配置并放入一套。非常感谢你让我找到问题guyz ..干杯！！！

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


}
4

1 回答 1

0

在评论中指出了使用散列数据结构而不实现与 ahashCode()一致的问题equals()，所以这里有一个建议您可以用作 a hashCode()：将板的单元格视为数字，其中 0 <= i <= 8 from左上角到右下角。

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

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

您最终会得到一个int有点粗略的结果，但仍然明智地从与您的关注点相关的电路板状态中得出，并且肯定与equals()检查被比较的两个电路板的所有单元格是否保持相同值一致。确保如果你实现equals()and hashCode()，你会始终如一地执行它，这大致意味着

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

->逻辑含义在哪里。

于 2013-04-05T20:19:22.597 回答