Java: Eight Queens algorithm error

Question

I saw a post here similar to this, but mine is slightly different.

I wrote the displayBoard method, but the last column doesn't return a Queen.

Is it because the queen has a value of 1 and is throwing off the numbers?

It keeps telling me I have an ArrayOutOfBoundsException: -1

I know that arrays count by 0 yet I still couldn't get this to work

---

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

You need to change the while loop in your placeQueens() method

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

The while loop should be < to ensure that you never attempt to access your board at index BOARD_SIZE. Once the row == BOARD_SIZE you attempt to access the board which will throw the index out of bounds exception you are seeing. Change it to the following

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

Furthermore, in your setQueen(...) and removeQueen(...) functions, you never do a bounds check and assume you can access the board with the passed in parameters. you need to ensure that both values are less than BOARD_SIZE before setting or removing the queen in your board array.

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

Finally, since you are applying your own offest of 1 you should change the call in your main to (Credit @Ian Mc)

q.placeQueens(1);

However if you want to simplify your program you should not apply an offset as that will often introduce user bugs. Here is what you should do to make your program work with no offset

(1) Add checks inside your isUnderAttack method to ensure you are looking at valid rows and columns in your board before accessing them with a simple check that only checks 0 and greater values

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) Then remove the offset from your remove and set queen methods

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) Ensure you loop from 0 to BOARD_SIZE - 1 inside placeQueens(...) method

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

(4) Finally start at index 0

q.placeQueens(0);

Output

| 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 |

Answer 2

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

Because you are going to set a Queen

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

And

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

Tested with

q.placeQueens(1); 

And is showing

| 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 |

I suggest you lookup some helpful java debugging tips (Eclipse or IntelliJ).