Java:八皇后算法错误

Question

我在这里看到了一篇与此类似的帖子，但我的略有不同。

我编写了 displayBoard 方法，但最后一列没有返回 Queen。

是因为皇后的值为 1 并且正在丢弃数字吗？

它一直告诉我有一个 ArrayOutOfBoundsException: -1

我知道数组按 0 计数，但我仍然无法让它工作

---

public class Queens 
{
    public static final int BOARD_SIZE = 8;

    public static final int EMPTY = 0;

    public static final int QUEEN = 1;

    private int board[][];

public Queens()
{
  board = new int[BOARD_SIZE][BOARD_SIZE];
}

public void clearBoard()
{
    board = new int[BOARD_SIZE][BOARD_SIZE];
}

public void displayBoard () {
    int counter = 0;
    for (int i = 0; i < BOARD_SIZE; i++) 
    {
        for (int j = 0 ; j < BOARD_SIZE; j++) 
        {
            if (board[i][j] == QUEEN ) 
            {
                System.out.print("| X |");
                counter++;
            }
            else 
            {              
                System.out.print("| 0 |");
            }
        }
        System.out.println();
    }
}

public boolean placeQueens(int column) {

if (column >= BOARD_SIZE) {
    return true;  // base case
}
else {
  boolean queenPlaced = false;
  int row = 1;  // number of square in column

  while ( !queenPlaced && (row <= BOARD_SIZE)  )  {
    // if square can be attacked
      if (isUnderAttack(row, column)) {
      ++row;  // consider next square in column
      } // end if
      else {  // place queen and consider next column
      setQueen(row, column);
      queenPlaced = placeQueens(column+1);
      // if no queen is possible in the next column,
      if (!queenPlaced) {
          // backtrack:  remove queen placed earliers
          // and try next square in column
          removeQueen(row, column);
          ++row;
      } // end if
      } // end if
  } // end while
  return queenPlaced;
} // end if
} // end placeQueens

private void setQueen(int row, int column) {
board[row-1][column-1] = QUEEN;
} // end setQueen

private void removeQueen(int row, int column) {
   board[row-1][column-1] = EMPTY;
} // end setQueen

private boolean isUnderAttack(int row, int column) {
// check column
for (int i=0; i<row-1; i++){
    if (board[i][column-1]==1){
        return true;
    }
}
// check row
for (int i=0; i<column-1; i++) {
    if (board[row-1][i] == 1){
        return true;
    }
}

// check lower diagnal
int lower_dir_row = row-2;
int lower_dir_column = column-2;
while (lower_dir_row>=0 && lower_dir_column>=0){
        if (board[lower_dir_row][lower_dir_column]==1){
            return true;
        } else {
            lower_dir_row = lower_dir_row -1;
            lower_dir_column = lower_dir_column -1;
        }
    }


 // check upper diagnal
int upper_dir_row = row;
int upper_dir_column = column-2;
while (upper_dir_row<BOARD_SIZE && upper_dir_column>=0){
    if(board[upper_dir_row][upper_dir_column] ==1){
        return true;
    }else{
        upper_dir_row = upper_dir_row +1;
        upper_dir_column = upper_dir_column -1;
    }
}
return false;

} // end isUnderAttack

public static void main(String[] s) 
{
    Queens q = new Queens();
    q.placeQueens(0);
    q.displayBoard();
}

} // end Queens

Answer 1

您需要更改 placeQueens() 方法中的 while 循环

while ( !queenPlaced && (row <= BOARD_SIZE)  )  {...}

while 循环应该是 < 以确保您永远不会尝试访问索引 BOARD_SIZE 处的板。一旦行 == BOARD_SIZE 您尝试访问该板，这将抛出您所看到的索引越界异常。改为如下内容

while ( !queenPlaced && (row < BOARD_SIZE)  )  {...}

此外，在 setQueen(...) 和 removeQueen(...) 函数中，您从不进行边界检查，并假设您可以使用传入的参数访问板。在设置或删除棋盘数组中的皇后之前，您需要确保这两个值都小于 BOARD_SIZE。

private void setQueen(int row, int column) {
    if(row - 1 < BOARD_SIZE && column - 1 < BOARD_SIZE)
        board[row-1][column-1] = QUEEN;
} // end setQueen

private void removeQueen(int row, int column) {
   if(row - 1 < BOARD_SIZE && column - 1 < BOARD_SIZE)
       board[row-1][column-1] = EMPTY;
} // end setQueen

最后，由于您正在应用自己的offest 1，因此您应该将 main 中的调用更改为(Credit @Ian Mc)

q.placeQueens(1);

但是，如果您想简化程序，则不应应用偏移量，因为这通常会引入用户错误。 为了使您的程序无偏移地运行，您应该执行以下操作

(1) 在 isUnderAttack 方法中添加检查，以确保您在通过仅检查 0 及更大值的简单检查访问面板中的有效行和列之前查看它们

private boolean isUnderAttack(int row, int column) {
// check column
for (int i=0; i<row-1; i++){
    /* add a check to ensure the column offset index is valid */
    if (column - 1 >= 0 && board[i][column-1]==1){
        return true;
    }
}
// check row
for (int i=0; i<column-1; i++) {
    /* add a check to ensure the row offset index is valid */
    if (row - 1 >= 0 && board[row-1][i] == 1){
        return true;
    }
}

(2) 然后从删除和设置皇后方法中删除偏移量

private void setQueen(int row, int column) {
    if(row < BOARD_SIZE && column < BOARD_SIZE)
        board[row][column] = QUEEN;
} // end setQueen

private void removeQueen(int row, int column) {
   if(row < BOARD_SIZE && column < BOARD_SIZE)
       board[row][column] = EMPTY;
} // end setQueen

(3) 确保在 placeQueens(...) 方法内从 0 循环到 BOARD_SIZE - 1

while ( !queenPlaced && (row < BOARD_SIZE)  )  {

(4) 最后从索引 0 开始

q.placeQueens(0);

输出

| 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |
| 0 || 0 || 0 || 0 || 0 || 0 || X || X |
| 0 || 0 || 0 || 0 || 0 || X || 0 || 0 |
| 0 || 0 || 0 || 0 || X || 0 || 0 || 0 |
| 0 || 0 || 0 || X || 0 || 0 || 0 || 0 |
| 0 || 0 || X || 0 || 0 || 0 || 0 || 0 |
| 0 || X || 0 || 0 || 0 || 0 || 0 || 0 |
| X || 0 || 0 || 0 || 0 || 0 || 0 || 0 |