# Queen’s Attack II Simple Solution – HackerRank

This is a simple and clear solution to the Queen’s  Attack 2 problem in HackerRank. It take just three steps as given below:

1. determine all the cells the queen can attack without obstacles – queenCells
2. determine all the cells blocked by the obstacles – pawnCells
3. return queenCells – pawnCells

That’s it! But seriously, what make this challenge a bit tasking is not only that there are obstacles, but we don’t know how many of them.

For simplicity, I have decided to use the name ‘pawns’ for ‘obstacles’.

To solve this problem, we would need three helper functions:

1. getCellsQueenCanAttack() – The queen can attack diagonal and orthogonal. For orthogonal, the number of cells is 2n -2 for diagonals the number of cells is given by 2n – 2 – |x – y| – |x + y – n – 1|. Just add the two and you’ll already pass tests for cases with no obstacles.
2. getRelativeLocation(queenX, queenY, pawnX, pawnY): this function returns one of the position of the pawn relative to the queen. U for up, D for down, L for left, R for right, UL for upper left, DL for down left etc
3. getCellsBlockedByPawns() – this function will use the relative position of the pawn to determine how many cells lies between the pawn and the edge of the board.

The original chess board setup is shown below:

The board showing the CellsQueenCanAttack (cells the queen can attack). Note that the queen cannot attack herself.

The board showing only the pawns(obstacles) and the cells blocked by them is shown below:

You can see from the figures above that the result in this case is 14 – 4 = 10

#### Helper Function Descriptions

So let’s just look at the three helper functions:

getCellsQueenCanAttack(queenX, queenY, boardSize)

This function is given below. I already explained formula to you earlier. Here, n is the board size and the queen is at position (queenX, queenY).

```def getCellsQueenCanAttack(queenX, queenY, boardSize):
orthognals =  2 * boardSize - 2
diagonals = 2 * boardSize - 2 - abs(queenX - queenY) - abs(queenX + queenY - boardSize - 1)
return orthognals + diagonals
```

getRelativeLocation(queenX, queenY, pawnX, pawnY):

This function for a single pawn, returns a value indicating the relative position of the pawn to the queen.

if both are in the same column (ie pawnY = queenY), then it could be ‘U’ or ‘D’ depending on the which is greater between queenX and pawnX. The same logic applies for all other positions. Watch the video for a detailed explanation:

```def getRelativeLocation(queenX, queenY, pawnX, pawnY):
if pawnY == queenY and pawnX < queenX:
return 'L'
if pawnY == queenY and pawnX > queenX:
return 'R'
if queenX == pawnX and pawnY > queenY:
return 'U'
if queenX == pawnX and pawnY < queenY:
return 'D'
if abs(queenX - pawnX) == abs(queenY - pawnY): #filter out irrelevant pawns
if pawnY > queenY and pawnX < queenX:
return 'UL'
if pawnY > queenY and pawnX > queenX:
return 'UR'
if pawnY < queenY and pawnX > queenX:
return 'DR'
if pawnY < queenY and pawnX < queenX:
return 'DL'
```

Note that some pawns are irrelevant. These are pawns that fall outside the diagonals and orthogonals of the queen.

getCellsBlockedByPawns(queenX, queenY, pawns)

This is the function that does more logic that previous two. So basically what it does is this: for each pawn, get its relative location, then determine how many cells lie between this pawn and the edge of the board. For each cell, add the cell position (x, y) to a set or tuples. This means there will be no repeated counts of the same cell.

At the end just return the count of  the set. This function is given below

```def getCellsBlockedByPawns(queenX, queenY, pawns):
blockedCells = set()
for pawn in pawns:
x = pawn[1]
y = pawn[0]
position = getRelativeLocation(queenX, queenY, x, y)
if position == 'U':
for i in range(y, n+1):
if position == 'D':
for i in range(y, 0, -1):
if position == 'L':
for i in range(x, 0, -1):
if position == 'R':
for i in range(x, n+1):
if position == 'UL':
while y <= n and x > 0:
x -= 1
y += 1
if position == 'UR':
while y <= n and x <= n:
x += 1
y += 1
if position == 'DR':
while y > 0 and x <= n:
x += 1
y -= 1
if position == 'DL':
while y > 0 and x > 0:
x -= 1
y -= 1
return len(blockedCells)
```

#### QueenAttack() Function

Finally we need to complete the QueenAttack  as shown below.

```def queensAttack(boardSize, k, queenY, queenX, pawns):
if len(pawns) == 0:
return getCellsQueenCanAttack(queenX, queenY, boardSize)
else:
queenCells = getCellsQueenCanAttack(queenX, queenY, boardSize)
pawnCells = getCellsBlockedByPawns(queenX, queenY, pawns)
return queenCells - pawnCells
```

From the code, we first check if there are pawns(obstacles), if not, we simply return the number of cells queen can attack without obstacles. If however, there are obstacles, we calculated cell blocked by the obstacles. The we subtract.

Hope this has helped you. I also recommend watching the video and feel free to reach me if you need more clarification.

Queen’s Attack II complete code in Github – https://github.com/KindsonTheGenius/QueenAttack2

#### kindsonthegenius

Kindson Munonye is currently completing his doctoral program in Software Engineering in Budapest University of Technology and Economics

View all posts by kindsonthegenius →