Last Updated: 22 May, 2022

King Placement

Moderate

Solve now

Problem statement

This is a typical chess game where your opponent first places a random number of Knights, Rooks, Bishop, and Queens on an ‘N*N’ chessboard, and then you have to place your king safely on the chessboard such that it should not be under attack by any piece.

Given an ‘N*N’ chessboard with ‘K’ number of Knights, ‘R’ number of Rooks, ‘B’ number of Bishops, and ‘Q’ number of queens. Your task is to find out the number of squares on the chessboard such that your King is not checked by any of your opponent's pieces.

NOTE: If you don't know how to play chess and how chess pieces move, please refer to the below link (you can concentrate only on how the above-mentioned pieces move).

HOW TO PLAY CHESS

EXAMPLE :

Refer to the explanation of Sample Input 1 for better understanding.

Input Format :

The first line will contain the integer 'T', the number of test cases.

The first line of each test case consists of integer  'N', the length of the given chessboard.

The next line contains ‘K’, no. of Knights. Next, ‘K’ lines provide 2 space-separated integers denoting the row and the column of the Knights ‘(i,j)’

The next line contains ‘R’, no. of Rooks. Next, ‘R’ lines provide 2 space-separated integers denoting the row and the column of the Rooks ‘(i,j)’

The next line contains ‘B’, no. of Bishops. Next, ‘B’ lines provide 2 space-separated integers denoting the row and the column of the Bishops ‘(i,j)’

The next line contains ‘Q’, no. of Queens. Next, ‘Q’ lines provide 2 space-separated integers denoting the row and the column of the Queens ‘(i,j)’

Output format :

For each test case, print the number of squares where King can be placed safely.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
2 <= 'N' <= 100
0 <= 'K' + ‘R’ + ‘B’ + ‘Q’ <= ‘N * N’
0 <= ‘i’, ‘j’ <= ‘N - 1’
It is guaranteed that sum of ‘N’ over all test cases is <= 1000
Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea of this approach is to place the king at each cell that is not occupied and check if it is getting attacked by any chess piece.

So we would iterate on each cell of the chessboard and if let’s suppose we are currently at cell (i, j) then

If there is a rook or queen in this row or column and there is no other chess piece in between, we can’t place the king here.
If there is a queen or bishop in the same main diagonal or opposite diagonal of the chessboard and there is no other chess piece in between, we can’t place the king here.
If there is a knight at ‘L-shape’ from this cell, we can’t place the king here.

If all the above conditions are false then we can place the king here safely.

Algorithm:

// The function will check if there is a knight attacking the given cell.

Bool attackedByKnight(i, j)

If ‘(i-2,j-1)’ is inside the chessboard and a knight is present there return ‘true’
If ‘(i-2,j+1)’ is inside the chessboard and a knight is present there return ‘true’
If ‘(i+2,j-1)’ is inside the chessboard and a knight is present there return ‘true’
If ‘(i+2,j+1)’ is inside the chessboard and a knight is present there return ‘true’
If ‘(i-1,j-2)’ is inside the chessboard and a knight is present there return ‘true’
If ‘(i+1,j-2)’ is inside the chessboard and a knight is present there return ‘true’
If ‘(i-1,j+2)’ is inside the chessboard and a knight is present there return ‘true’
If ‘(i+1,j+2)’ is inside the chessboard and a knight is present there return ‘true’
Return ‘false’

Bool attackedFromLeft(i, j)

Initialize variables ‘x’ and ‘y’ with initial values ‘i’ and ‘j-1’ respectively.
Run a while loop until ‘(x, y)’ is inside the chessboard
- If cell ‘(x, y)’ is empty then decrement ‘y’ by one.
- Else If cell ‘(x, y)’ have a rook or queen then return ‘true’
- Else return ‘false’
Return ‘false’

Bool attackedFromRight(i, j)

Initialize variables ‘x’ and ‘y’ with initial values ‘i’ and ‘j+1’ respectively.
Run a while loop until ‘(x, y)’ is inside the chessboard
- If cell ‘(x, y)’ is empty then increment ‘y’ by one.
- Else If cell ‘(x, y)’ have a rook or queen then return ‘true’
- Else return ‘false’
Return ‘false’

Bool attackedFromUp(i, j)

Initialize variables ‘x’ and ‘y’ with initial values ‘i-1’ and ‘j’ respectively.
Run a while loop until ‘(x, y)’ is inside the chessboard
- If cell ‘(x, y)’ is empty then decrement ‘x’ by one.
- Else If cell ‘(x, y)’ have a rook or queen then return ‘true’
- Else return ‘false’
Return ‘false’

Bool attackedFromDown(i, j)

Initialize variables ‘x’ and ‘y’ with initial values ‘i+1’ and ‘j’ respectively.
Run a while loop until ‘(x, y)’ is inside the chessboard
- If cell ‘(x, y)’ is empty then increment ‘x’ by one.
- Else If cell ‘(x, y)’ have a rook or queen then return ‘true’
- Else return ‘false’
Return ‘false’

Bool attackedFromMainDiagonalUp(i, j)

Initialize variables ‘x’ and ‘y’ with initial values ‘i-1’ and ‘j-1’ respectively.
Run a while loop until ‘(x, y)’ is inside the chessboard
- If cell ‘(x, y)’ is empty then decrement ‘x’ and ‘y’ by one.
- Else If cell ‘(x, y)’ have a bishop or queen then return ‘true’
- Else return ‘false’
Return ‘false’

Bool attackedFromMainDiagonalDown(i, j)

Initialize variables ‘x’ and ‘y’ with initial values ‘i+1’ and ‘j+1’ respectively.
Run a while loop until ‘(x, y)’ is inside the chessboard
- If cell ‘(x, y)’ is empty then increment ‘x’ and ‘y’ by one.
- Else If cell ‘(x, y)’ have a bishop or queen then return ‘true’
- Else return ‘false’
Return ‘false’

Bool attackedFromOtherDiagonalUp(i, j)

Initialize variables ‘x’ and ‘y’ with initial values ‘i-1’ and ‘j+1’ respectively.
Run a while loop until ‘(x, y)’ is inside the chessboard
- If cell ‘(x, y)’ is empty then decrement ‘x’ by one and increment ‘y’ by one.
- Else If cell ‘(x, y)’ have a bishop or queen then return ‘true’
- Else return ‘false’
Return ‘false’

Bool attackedFromOtherDiagonalDown(i, j)

Initialize variables ‘x’ and ‘y’ with initial values ‘i+1’ and ‘j-1’ respectively.
Run a while loop until ‘(x, y)’ is inside the chessboard
- If cell ‘(x, y)’ is empty then increment ‘x’ by one and decrement ‘y’ by one.
- Else If cell ‘(x, y)’ have a bishop or queen then return ‘true’
- Else return ‘false’
Return ‘false’

Bool attackedByAny(i, j)

If ‘attackedByKnight(i, j)’ is true then return ‘true’
If ‘attackedFromLeft(i, j)’ is true then return ‘true’
If ‘attackedFromRight(i, j)’ is true then return ‘true’
If ‘attackedFromUp(i, j)’ is true then return ‘true’
If ‘attackedFromDown(i, j)’ is true then return ‘true’
If ‘attackedFromMainDiagonalUp(i, j)’ is true then return ‘true’
If ‘attackedFromMainDiagonalDown(i, j)’ is true then return ‘true’
If ‘attackedFromOtherDiagonalUp(i, j)’ is true then return ‘true’
If ‘attackedFromOtherDiagonalDown(i, j)’ is true then return ‘true’
Return ‘false’

// The function will return the count of safe positions to place the king on the chessboard.

Int kingPlacement(N, K, R, B, Q, pointsK[], pointsR[], pointsB[], pointsQ[])

Initialize variable name ‘ans’ with initial value zero.
Initialize 2D character array ‘matrix’ of size ‘N * N’ with initial value ‘.’ denoting every cell is empty.
Run a loop from 0 to ‘K-1’ with a variable ‘i’
- Mark ‘pointK[i]’ as character K in ‘matrix’.
Run a loop from 0 to ‘R-1’ with a variable ‘i’
- Mark ‘pointR[i]’ as character R in ‘matrix’.
Run a loop from 0 to ‘B-1’ with a variable ‘i’
- Mark ‘pointB[i]’ as character B in ‘matrix’.
Run a loop from 0 to ‘Q-1’ with a variable ‘i’
- Mark ‘pointQ[i]’ as character Q in ‘matrix’.
Run a loop from 0 to ‘N-1’ with a variable ‘i’
- Run a loop from 0 to ‘N-1’ with a variable ‘j’
  - If ‘matrix[i][j]’ is empty and ‘attackedByAny(i, j)’ is false then increment ‘ans’ by one.
Return ‘ans’

Solve now

02 Approach

The idea is to first iterate on the chessboard and mark all the attacked cells and then we again iterate on the chessboard and count the number of cells which remain unmarked.

The attacked cells can be marked using an ordinary iterative approach.

So in this approach based on the chess piece we are currently on we will keep marking all the cells in its attack range until we escape the chessboard or another chess piece is already present there.

Algorithm:

// Mark cells attacked by Knight

Void markAttackedByKnight(i, j, chessboard[][])

If ‘(i-2,j-1)’ is inside the chessboard and is empty then mark ‘chessboard[i-2][j-1]’ as character K.
If ‘(i-2,j+1)’ is inside the chessboard and is empty ’ then mark ‘chessboard[i-2][j+1]’ as character K.
If ‘(i+2,j-1)’ is inside the chessboard and is empty then mark ‘chessboard[i+2][j-1]’ as character K.
If ‘(i+2,j+1)’ is inside the chessboard and is empty then mark ‘chessboard[i+2][j+1]’ as character K.
If ‘(i-1,j-2)’ is inside the chessboard and is empty then mark ‘chessboard[i-1][j-2]’ as character K.
If ‘(i+1,j-2)’ is inside the chessboard and is empty then mark ‘chessboard[i+1][j-2]’ as ‘character K.
If ‘(i-1,j+2)’ is inside the chessboard and is empty then mark ‘chessboard[i-1][j+2]’ as character K.
If ‘(i+1,j+2)’ is inside the chessboard and is empty then mark ‘chessboard[i+1][j+2]’ as character K.
Return

Void markUp(i, j, chessboard[][], chessPiece)

Run a while loop until ‘(i, j)’ is inside the chessboard and is empty
- Mark ‘chessboard[i][j]’ as character chessPiece.
- Decrement ‘i’ by one.
return

Void markDown(i, j, chessboard[][])

Run a while loop until ‘(i, j)’ is inside the chessboard and is empty
- Mark ‘chessboard[i][j]’ as character chessPiece.
- Increment ‘i’ by one.
return

Void markLeft(i, j, chessboard[][])

Run a while loop until ‘(i, j)’ is inside the chessboard and is empty
- Mark ‘chessboard[i][j]’ as character chessPiece.
- Decrement ‘j’ by one.
return

Void markRight(i, j, chessboard[][])

Run a while loop until ‘(i, j)’ is inside the chessboard and is empty
- Mark ‘chessboard[i][j]’ as character chessPiece.
- Increment ‘j’ by one.
return

Void markAttackedByRook(i, j, chessboard[][])

Call ‘markUp(i-1, j)’
Call ‘markDown(i+1, j)’
Call ‘markLeft(i, j-1)’
Call ‘markRight(i, j+1)’

// Similar functions can be created for all chess pieces and called when encountered.

// The function will return the count of safe positions to place the king on the chessboard.

Int kingPlacement(N, K, R, B, Q, pointsK[], pointsR[], pointsB[], pointsQ[])

Initialize variable name ‘ans’ with initial value zero.
Initialize 2D character array ‘chessboard’ of size ‘N * N’ with initial value ‘.’ denoting every cell is empty.
Run a loop from 0 to ‘K-1’ with a variable ‘i’
- Mark ‘pointK[i]’ as character K in ‘chessboard’.
Run a loop from 0 to ‘R-1’ with a variable ‘i’
- Mark ‘pointR[i]’ as character R in ‘chessboard’.
Run a loop from 0 to ‘B-1’ with a variable ‘i’
- Mark ‘pointB[i]’ as character B in ‘chessboard’.
Run a loop from 0 to ‘Q-1’ with a variable ‘i’
- Mark ‘pointQ[i]’ as character Q in ‘chessboard’.
Run a loop from 0 to ‘N-1’ with a variable ‘i’
- Run a loop from 0 to ‘N-1’ with a variable ‘j’
  - If ‘chessboard[i][j]’ is not empty then call the corresponding chess piece mark function.
Run a loop from 0 to ‘N-1’ with a variable ‘i’
- Run a loop from 0 to ‘N-1’ with a variable ‘j’
  - If ‘chessboard[i][j]’ is empty then increment ‘ans’ by one.
Return ‘ans’

Solve now