자바 : 8 명의 퀸즈 깊이 우선 검색 사용

Question

8 개의 여왕에 대한 깊이 우선 검색을 구현했으며 빈 보드에서는 잘 작동하지만 모든 초기 상태를 받아들이도록 수정해야합니다. 나는 그것을 수정했지만 오류가 발생합니다. 이 문제를 해결하는 방법을 모르겠습니다.

Exception in thread "main" java.lang.StackOverflowError 

그것은 어떤 초기 상태에서는 작동하지 않습니다 여기에

public class depth { 
    public static int count1=0; 
    public static void eightQueen(int N, int[][] board, int i, int j, boolean found) { 

     long startTime = System.nanoTime();//time start 

     if (!found) { 

      if (IsValid(board, i, j)) {//check if the position is valid 
       board[i][j] = 1; 

       System.out.println("[Queen added at (" + i + "," + j + ")"); 
       count1++; 
       PrintBoard(board); 


       if (i == N - 1) {//check if its the last queen 
        found = true; 
        PrintBoard(board); 
        double endTime = System.nanoTime();//end the method time 

        double duration = (endTime - startTime)*Math.pow(10.0, -9.0); 
        System.out.print("total Time"+"= "+duration+"\n"); 
       } 
       //call the next step 
       eightQueen(N, board, i + 1, 0, found); 
      } else { 

       //if the position is not valid & if reach the last row we backtracking 
       while (j >= N - 1) { 
        int[] a = Backmethod(board, i, j); 
        i = a[0]; 
        j = a[1]; 

        System.out.println("back at (" + i + "," + j + ")"); 
        PrintBoard(board); 
       } 
       //we do the next call 
       eightQueen(N, board, i, j + 1, false); 
      } 
     } 
    } 

    public static int[] Backmethod(int[][] board, int i, int j) { 
     int[] a = new int[2]; 
     for (int x = i; x >= 0; x--) { 
      for (int y = j; y >= 0; y--) { 
       //search for the last queen 
       if (board[x][y] != 0) { 
        //deletes the last queen and returns the position 
        board[x][y] = 0; 
        a[0] = x; 
        a[1] = y; 
        return a; 
       } 
      } 
     } 
     return a; 
    } 

    public static boolean IsValid(int[][] board, int i, int j) { 

     int x; 
     //check the queens in column 
     for (x = 0; x < board.length; x++) { 
      if (board[i][x] != 0) { 
       return false; 
      } 
     } 
     //check the queens in row 
     for (x = 0; x < board.length; x++) { 
      if (board[x][j] != 0) { 
       return false; 
      } 
     } 
     //check the queens in the diagonals 
     if (!SafeDiag(board, i, j)) { 
      return false; 
     } 
     return true; 
    } 

    public static boolean SafeDiag(int[][] board, int i, int j) { 

     int xx = i; 
     int yy = j; 
     while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) { 
      if (board[xx][yy] != 0) { 
       return false; 
      } 
      yy++; 
      xx++; 
     } 
     xx = i; 
     yy = j; 
     while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) { 
      if (board[xx][yy] != 0) { 
       return false; 
      } 
      yy--; 
      xx--; 
     } 
     xx = i; 
     yy = j; 
     while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) { 
      if (board[xx][yy] != 0) { 
       return false; 
      } 
      yy--; 
      xx++; 
     } 
     xx = i; 
     yy = j; 
     while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) { 
      if (board[xx][yy] != 0) { 
       return false; 
      } 
      yy++; 
      xx--; 
     } 
     return true; 
    } 

    public static void PrintBoard(int[][] board) { 
     System.out.print(" "); 
     for (int j = 0; j < board.length; j++) { 
      System.out.print(j); 
     } 
     System.out.print("\n"); 
     for (int i = 0; i < board.length; i++) { 
      System.out.print(i); 
      for (int j = 0; j < board.length; j++) { 
       if (board[i][j] == 0) { 
        System.out.print(" "); 
       } else { 
        System.out.print("Q"); 
       } 
      } 
      System.out.print("\n"); 
     } 
    } 

    public static void main(String[] args) { 


     //we create a board 
     int[][] board = new int[8][8]; 
     board [0][0]=1; 
     board [1][1]=1; 
     board [2][2]=1; 
     board [3][3]=1; 
     board [4][4]=1; 
     board [5][5]=1; 
     board [6][6]=1; 
     board [7][7]=1; 


     eightQueen(8, board, 0, 0, false); 
     System.out.println("the solution as pair"); 
     for(int i=0;i<board.length;i++){ 
      for(int j=0;j<board.length;j++) 
       if(board[i][j]!=0) 

       System.out.println(" ("+i+" ,"+j +")"); 
     } 
     System.out.println("the number of node stored in memory "+count1);  
    } 
} 

오류입니다 :

여기 내 코드입니다. 문제가있는 곳을 모르겠습니다. 솔루션을 찾지 못하면 "솔루션 없음"을 인쇄해야합니다.

Answer 1

이 코드는 같은 함수가 재귀 적으로 계속 호출되는 데드 록을 발생시킵니다. 방법 : eightQueen은 위치 (i, j)가 유효한지 검사합니다. 귀하의 경우 i와 j의 첫 번째 값은 각각 (0,0)입니다.

j가 7에 도달 할 때까지 j를 증가시킨 다음 첫 번째 여왕 위치 (0,0)를 반환합니다. else 루프는 i를 증가시키지 않으며 모든 사용 가능한 위치는 안전하지 않으므로 무한 루프가됩니다.

코드를 다시 방문해야합니다.

Answer 2

eightQueen 메서드는 무한정 호출됩니다.