처음 탐색 알고리즘이 무한 루프에 갇히다

Question

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


    } 

그래서이게 내가 마침내 내 문제를 해결 한 것입니다. 문제를 해결 한 결과, 요소가 설정되어 있는지 여부를 비교할 때, 실제로 주소 값을 비교하지만 필요한 개체가 아니기 때문에 새로운 주소가 생성 될 때마다 무한 루프가 나올 수 없었습니다. 개체를 세트를 사용하여 비교하는 대신에, 세트를 만들었습니다. 문자열로 저장된 객체의 구성을 비교하고 set.Thanks에 넣어 내게 문제가 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; 
    } 


} 

Answer 1

, 그래서 여기 equals()는 의견에서 지적 된과 일치하는 hashCode()을 구현하지 않고 해시 데이터 구조를 사용하여 문제는 당신이 hashCode()로 사용할 수있는 것을 제안이다 : 보드 등의 세포를 고려 0으로= i < = 8 위 왼쪽에서 오른쪽 하단까지.

@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() 및 hashCode()을 구현하는 것이 있는지 확인하십시오, 당신은 지속적으로 그것을 대략 -> 논리 의미입니다

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

을 의미한다.