2014-01-30 33 views
-2

我實現了深度優先搜索8皇后,它適用於空板,但我需要修改它以接受任何初始狀態。我修改了它,但它給出了一個錯誤。我不知道如何解決這個問題。java:使用深度優先搜索的8個皇后

這裏是我的代碼:

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

以下是錯誤:

Exception in thread "main" java.lang.StackOverflowError 

它不會對任何初始狀態工作。我不知道問題出在哪裏,如果找不到解決方案,我需要它打印「無解」。

+0

沒有人會坐在這裏,儘管所有這些代碼爲你步。這就是上帝創造調試者的原因。如果你有一個堆棧溢出,那麼你的遞歸方法沒有退出條件,並且它永遠調用它自己。 – OldProgrammer

+0

我使用調試器我知道錯誤,但我不知道如何解決這個問題 – john

+0

注意到在關閉投票隊列中遇到這個問題:即使這是首先發布,我投票關閉這一個,因爲第二個有一個接受的答案。 –

回答

1

此代碼導致死鎖,其中相同的函數不斷調用遞歸調用。方法:eightQueen檢查位置(i,j)是否有效。在你的情況下,我和j的第一個值分別是(0,0)。

它增加j直到達到7,然後返回第一個皇后位置(0,0)。 else循環永遠不會增加i,並且所有可用的位置都是不安全的,因此它以無限循環結束。

您需要重新訪問代碼。

+0

我不知道如何糾正這個問題,你能幫我嗎? – john

+0

您的代碼需要至少一個可用位置。在你的測試場景中,所有8個初始位置都需要更改,因爲第一個女王沒有任何位置。目前的代碼將適用於所有條件,如{1,1,1,1,1,1,1,0} – user2881767

+0

你能幫我編輯代碼打印,如果沒有任何解決方法放女王,謝謝。 – john

1

方法eightQueen無限期地自我調用。

+0

感謝您的回覆,如何更正此問題。 – john