Search code examples
javaarrays2dchess

Runtime error when counting the number of diagonals Queen can attack from a specific position on chessboard in java


I have an n*n chessboard, where 0<n<=100000.

The queen can be placed anywhere on the board.

Is there a method/formula to calculate the number of diagonals the queen can visit from the specified position?

I tried to calculate it using an if-else loop, I got the right answer for a shorter 2d chessboard, but for an array of lengths like 100000, I got a runtime error.

My code:

         if(rowQ<n-1 && colQ<n-1) {         //n:size of array
            int row=rowQ;                   //rowQ and colQ: row and column 
            int col=colQ;                   //of the queen.
            while(row<n-1 && col<n-1) {     //Capture: number of squares
                row++;                      //queen can visit.
                col++;
                capture++;                   
                
            }
            
        }
        if(rowQ>0 && colQ>0) {
            int row=rowQ;
            int col=colQ;
            while(row>0 && col>0) {
                row--;
                col--;
                capture++;
                
            }
                
        }
        if(rowQ>0 && colQ<n-1){
            int row = rowQ;
            int col = colQ;
            while(row>0 && col < n-1){
                row--;
                col++;
                capture++;
            }
            
        }
        if(rowQ<n-1 && colQ>0){
            int row = rowQ;
            int col = colQ;
            while(row<n-1 && col >0){
                row++;
                col--;
                capture++;
            
            }
        }
                    

Solution

  • There's no need to count out the squares one-by-one. The queen's location and n are all you need to know.

    Taking row 0 as "up", row n-1 as "down", column 0 as "left" and column n-1 as "right", a queen at rowQ, colQ can travel a maximum of:

    • rowQ rows up,
    • n-rowQ-1 rows down
    • colQ columns left
    • n-colQ-1 columns right

    For diagonal travel, the closest edge in the direction of travel determines how many diagonal squares can be reached:

    • In the "up-left" direction, the lesser of rowQ or colQ
    • In the "down-left" direction, the lesser of n-rowQ-1 or colQ
    • In the "up-right" direction, the lesser of rowQ or n-colQ-1
    • In the "down-right" direction, the lesser n-rowQ-1 an n-colQ-1

    Add up all four and you have you result.