April 98 Question 2

This is a first inefficient way of solving the problem..

  boolean valid_position(boolean[][] board, int row, int column)
  {
   if (board[i][j])
     return false;
   else {
     int i,j;
     // check each square in the column
     j = column;
     for (i = 0; i < board.length; i++) {
       if (board[i][j])
         return false;
     }
     // check each square in the row
     i = row;
     for (j = 0; j < board[i].length; j++) {
       if (board[i][j])
         return false;
     }
     //check diagonals
     int incr_i, incr_j;

     // left half of diagonal of negative slope
     incr_i = -1;
     incr_j = -1;
     i = row + incr_i; 
     j = column + incr_j;
     while ( i < board.length && j < board[i].length && i>=0 && j>=0)
     {
       if (board[i][j]) return false;
       i += incr_i;
       j += incr_j;     
     }    
     // left half of diagonal of positive slope
     incr_i = 1;
     i = row + incr_i;
     j = column + incr_j;
     while ( i < board.length && j < board[i].length && i>=0 && j>=0)
     {
       if (board[i][j]) return false;
       i += incr_i;
       j += incr_j;
     } 
     // right half of diagonal of negative slope
     incr_j = 1;
     i = row + incr_i;
     j = column + incr_j;
     while ( i < board.length && j < board[i].length && i>=0 && j>=0)
     {
       if (board[i][j]) return false;
       i += incr_i;
       j += incr_j;
     }
     // right half of diagonal of positive slope
     incr_i = -1;
     i = row + incr_i;
     j = column + incr_j;
     while ( i < board.length && j < board[i].length && i>=0 && j>=0)
     {
       if (board[i][j]) return false;
       i += incr_i;
       j += incr_j;
     }     
   }// end else
  } // end valid_position

Notice how the i & j assignments as well as the while loop are repeated throughout the method in order to check all halves of all diagonals.. This is very redundant. See this solution for better implementation.

Back to April 98 Final
On to Revised Question 2