Java: ошибка алгоритма восьми королев

Question

Я видел пост, похожий на этот, но мой немного отличается.

Я написал метод displayBoard, но последний столбец не возвращает Королеву.

Это потому, чтокоролева имеет значение 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

q.placeQueens(0); // here is the Error 

Поскольку вы собираетесь установить Королеву

int row = 1;
.
.
.          
setQueen(row, column);  // The program will enter with row 1 and column 0

И

private void setQueen(int row, int column) { 
    board[row-1][column-1] = QUEEN; // Here comes with row=1 and column 0
} 

Протестировано с

q.placeQueens(1); 

И показывает

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

Предлагаю вам посмотреть полезные советы по отладке Java ( Eclipse или IntelliJ ).

Answer 2

Вам необходимо изменить цикл while в вашем методе placeQueens ()

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

Цикл while должен быть <, чтобы гарантировать, что вы никогда не будете пытаться получить доступ к своей доске по индексу BOARD_SIZE.Как только строка == BOARD_SIZE, вы пытаетесь получить доступ к доске, которая выбрасывает индекс за исключением исключения, которое вы видите.Измените его на следующее </p>

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

Наконец, поскольку вы применяете свое собственное предложение 1, вы должны изменить вызов в своем основномto (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) Убедитесь, что вы зациклились от 0 до BOARD_SIZE - 1 внутри метода placeQueens (...)

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 |