N皇后使用堆棧，找不到bug

Question

我試圖完成我的家庭作業項目，並尋求幫助找到一個錯誤。我正在使用回溯算法來查找N皇后問題的所有解決方案。我主要關心的是我的衝突方法 - 它在堆棧類中。其目的是檢測傳遞的Queen對象（衝突方法的參數1）是否與板上的任何其他女王/王后在同一行，列或對角線上。傳遞給衝突方法的queen對象存儲在Queen類中，並且在Point類的實例的幫助下記錄它的位置。我的代碼在我創建的Queen類中使用了兩個方法，public int getRow（）和public int getColumn（）。兩者都返回一個int。第二個參數是一個名爲board的二維數組（或數組）。皇后已經在棋盤上用這個布爾值表示真值。布爾值爲false表示板上有空的方塊。

Solution.n是對另一個類中的靜態int變量的引用。它的值表示板的邊緣。示例...對於8皇后問題，我們創建一個大小爲8的二維數組。Solution.n遞減1以等於二維數組的最後一個索引。

下面是代碼：

public boolean conflict(Queen x, boolean [][] board) //conflict method 
{ 
    if(checkColumn(x, board) == false) 
     return true; //conflict 
    else if(checkRow(x, board) == false) 
     return true; //conflict 
    else if(checkDiagonal(x, board) == false) 
     return true; //conflict 
    else 
     return false; //no conflict on board 
} 



private boolean checkColumn(Queen x, boolean [][] board)//returns true when column is safe 
{ 
    int col = x.getColumn(); 
    for(int row = 0; row <= Solution.n; row++) 
    { 
     if(board[row][col] == true) //queen is in this column 
     { 
      return false; 
     } 
    } 
    return true; 
} 

private boolean checkRow(Queen x, boolean [][] board) //returns true when row is safe 
{ 
    int row = x.getRow(); 
    for(int col = 0; col <= Solution.n; col++) 
    { 
     if(board[row][col] == true) //queen is in this row 
     { 
      return false; 
     } 
    } 
    return true; 
} 

private boolean checkDiagonal(Queen location, boolean [][] board) //returns true when diagonal is safe 
{ 
    int row, col; 
    row = location.getRow() - 1; 
    col = location.getColumn() - 1; 
    while(row >=0 && col >= 0) //iterate down-left 
    { 
     if(board[row][col] == true) //queen found? 
     { 
      return false; 
     } 
     row--; 
     col--; 
    } 
    row = location.getRow() - 1; 
    col = location.getColumn() + 1; 
    while(row != -1 && col <= Solution.n) //iterate down-right 
    { 
     if(board[row][col] == true) //queen found? 
     { 

      return false; 
     } 
     row--; 
     col++; 
    } 
    row = location.getRow() + 1; 
    col = location.getColumn() + 1; 
    while(row <= Solution.n && col <= Solution.n) //iterate up-right 
    { 
     if(board[row][col] == true) //queen found? 
     { 
      return false; 
     } 
     row++; 
     col++; 
    } 
    row = location.getRow() +1; 
    col = location.getColumn()-1; 
    while(row <= Solution.n && col != -1) //iterate up-left 
    { 
     if(board[row][col] == true) //queen found? 
     { 
      return false; 
     } 
     row++; 
     col--; 
    } 
    return true; 
} 

我相信這個片段的代碼包含一個錯誤，但如果我錯了，然後我爲浪費你的時間道歉：P

你的幫助將是不勝感激。謝謝！ ：D

Answer 1

你有幾個小錯誤 - 例如，你有從0到Solution.n（含）的循環，而他們應該去Solution.n-1。然而，大多數錯誤可以通過選擇更合適的數據結構來消除。

想想看：你並不需要一個完整的N X N董事會決定女王的位置：

• 有每行一個女王，所以女王的數量是其行。
• 每列有一個皇后，所以你需要一個boolean[N]數組來知道哪些行被採取。
• 每個上升對角線有一個女王，所以你需要一個boolean[2N-1]的數組來知道哪些上升的對角線被拍攝。

• 每個降對角線有一個女王，所以你需要一個boolean[2N-1]的數組來知道哪些降對角線被採用。

  boolean [] columns = new boolean [N]; boolean [] ascending = new boolean [2 * N-1]; boolean [] descending = new boolean [2 * N-1];

在這一點上，你已經得到了你所需要的：而不是一個方形boolean[N][N]陣列的你需要的boolean三個線性陣列。這可以讓你更快地做你的支票：

int c = x.getColumn(); 
int r = x.getRow(); 
boolean conflict = columns[c] 
       || ascending[r+c] 
       || descending[N-r+c]; 

就是這樣 - 不需要循環！現在你可以使用這三個數組代替你的回溯算法，而不是方形板。

Answer 2

這個答案不會解決你的問題，因爲我不相信你的錯誤是在你的代碼粘貼，但這裏是你的代碼，寫的有點接近我怎麼可能會這樣寫的：

// returns true when column is safe 
private boolean checkColumn(Queen x, boolean [][] board) 
{ 
    int col = x.getColumn(); 
    for(int row = 0; row <= Solution.n; row++) 
    { 
     if(board[row][col]){ return false; } 
    } 
    return true; 
} 

// returns true when row is safe 
private boolean checkRow(Queen x, boolean [][] board) 
{ 
    int row = x.getRow(); 
    for(int col = 0; col <= Solution.n; col++) 
    { 
     if(board[row][col]){ return false; } 
    } 
    return true; 
} 

// returns true if the position is valid given the board size 
// (as defined by Solution) 
private boolean validPosition(int row, int col) 
{ 
    if(0 > row || row > Solution.n){ return false; } 
    if(0 > col || col > Solution.n){ return false; } 
    return true; 
} 

// returns true when diagonal is safe 
private boolean checkDiagonal(Queen x, boolean [][] board) 
{ 
    int row, col; 

    // Down Left 
    row = x.getRow();       // "Start" on current position 
    col = x.getColumn(); 
    while(true) 
    { 
     row--; col--;       // Take a step in the direction 
     if(!validPosition(row, col)){ break; } // Stop if we've left the board 
     if(board[row][col]){ return false; } // Check whether it's occupied 
    } 

    // Down Right 
    row = x.getRow(); 
    col = x.getColumn(); 
    while(true) 
    { 
     row--; col++; 
     if(!validPosition(row, col)){ break; } 
     if(board[row][col]){ return false; } 
    } 

    // Up Right 
    row = x.getRow(); 
    col = x.getColumn(); 
    while(true) 
    { 
     row++; col++; 
     if(!validPosition(row, col)){ break; } 
     if(board[row][col]){ return false; } 
    } 

    // Up Left 
    row = x.getRow(); 
    col = x.getColumn(); 
    while(true) 
    { 
     row++; col--; 
     if(!validPosition(row, col)){ break; } 
     if(board[row][col]){ return false; } 
    } 
    return true; 
} 

public boolean conflict(Queen x, boolean [][] board) //conflict method 
{ 
    if  ( checkColumn(x, board) == false){ return true; } 
    else if( checkRow(x, board) == false){ return true; } 
    else if(checkDiagonal(x, board) == false){ return true; } 
    else          { return false; } 
} 

}

它簡化了很多邏輯，增加了幫助函數validPosition()，並清理了一些測試和循環。