Queen’s Attack

Given a square chess board with one queen and a number of obstacles placed on it.

Problem : Determine how many squares the queen can attack?

Given conditions:

• The Queen can be standing at any square of given n x n chess board.
• The rows are numbered from 1 to n, going from bottom to top. The columns are numbered from 1 to n, going from left to right.
• Each square is referenced by a tuple, (r, c), describing the row, r, and columns, c, where the square is located.
• Queen’s position is (qR, qC). In a single move the queen can attack any square in any of the 8 directions (left, right, up, down, and the 4 diagonals).

In the diagram below the green circles denote all the cells and the queen can attack from (4,4):

 

• There can be obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. Number of obstacles is determined by the value of k. For example, an obstacle at location (3,5) in the diagram above prevents the queen from attacking cells (3,5), (2,6), and (1,7): 

   

• Given the queen’s position and all the locations of the obstacles, find the number of squares the queen can attack from her position (qR, qC).

Examples-1:

In the above scenario, it’s a 4 x 4 chessboard, queen’s position is (4,4), and there are no obstacles (k=0).

The answer is 9. The queen can attack 9 squares.

In the above scenario, it’s a 5 x 5 chessboard, the queen’s position is (4,3), with k=3 obstacles. 

Position of the obstacles are as below.

{
    {4, 2},
    {5, 5},
    {2, 3}
}

The answer is 10. The queen can attack 10 squares.

Solution:

I came across this problem in RackerRank. Initially I solved the problem by creating a “n x n” int array, with all elements 0. Queen’s position (qR, qC), I set the value to 1. For all the obstacle cells I set the value to -1. I wrote the logic, calculation was perfect. But my program passed only few test cases. There were many test cases with much bigger value of n. Let’s say for n=100000, if we create n x n matrix, it gives out of memory in my local computer. And it RackerRank it simply says “Test cases failed”. So, I tried different approach. The below algorithm worked, and this time all the test cases passed.

1. Create 8 Lists for 8 different directions the Queen can attack.
2. Iterate through all the obstacles. For each, identify if it falls in the path of any of the 8 directions. If yes, then add the points in the appropriate List.
3. In all the 8 Lists, find the cells which are closest to the queen.
4. Calculate all possible cells which the queen can attack.

You can check the code or download it from my GitHub account. It’s a java maven project.

https://github.com/jahidakhtargit/problem-solving