A number of queens, knights and pawns have been placed on a chessboard. Find out how many of the unoccupied squares on the board are not under attack from either a queen or a knight (or both). Such squares are called safe squares. Pawns only serve to block maneuvers of queens. They can not perform attacks themselves.

This configuration of queens, knights and pawns leaves six safe squares on the chessboard.

For those who are not familiar with the rules of the game of chess, we recall that a knight can move to any unoccupied square that is on the opposite corner of a $$2 \times 3$$ rectangle from its current position. A queen can attack in any of the eight horizontal, vertical and diagonal directions from her current position. Note that the movement of a queen can be blocked by any other piece on the board, while a knight's movement can not be blocked by other pieces.

The black knight may attack any of eight squares that are marked by a black dot. The white knight is limited in attacking only the two squares marked by a white dot.

A queen can attack all squares in the horizontal, vertical and diagonal directions, marked by a black dot.

Assignment

Determine the number of safe squares on a chessboard containing some queens, knights and pawns.

This is done by writing the following three functions that each take three arguments that describe the configuration of the chessboard: i) the number of rows $$r \in \mathbb{N}$$ (int) of the chessboard ($$r \geq 2$$), ii) the number of columns $$c \in \mathbb{N}$$ (int) of the chessboard ($$c \geq 2$$) and iii) a sequence ( list or tuple) containing the positions of the pieces on the chessboard. The position of a piece is given by a sequence ( list or tuple) containing three elements. The first element is a string (str) that describes the kind of chess piece (Q represents a queen, K a knight and P a pawn). The second and third elements respectively indicate the row (int) and column (int) where the piece is placed. Rows and columns are numbered from zero, as with the chessboard in the above figures.

A function chessboard that returns a grid representation of the chessboard. The grid is represented as a sequence (list) of the rows of the chessboard (listed from top to bottom). Each rows is itself represented as a sequence (list) of strings (str) that describe the chess pieces on each square of the row (listed from left to right). A queen is represented by an uppercase letter Q, a knight by an uppercase letter K, a pawn by an uppercase letter P, and a square without a chess piece by the empty string.
A function unsafe_squares that returns the same grid representation of the given chessboard as the function chessboard, where unoccupied squares are marked with an asterisk (*) if they are under attack from either a queen or a knight (or both).
A function safe_squares that returns the number of safe squares (int) on the given chessboard.

Example

        >>> chessboard(4, 4, (('K', 0, 1), ('Q', 0, 3), ('P', 1, 2), ('Q', 1, 3)))
[['', 'K', '', 'Q'], ['', '', 'P', 'Q'], ['', '', '', ''], ['', '', '', '']]
>>> chessboard(2, 3, (('Q', 0, 1), ('K', 0, 0)))
[['K', 'Q', ''], ['', '', '']]
>>> chessboard(8, 8, (('Q', 4, 3), ))
[['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', 'Q', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', '']]
>>> chessboard(8, 8, (('K', 4, 3), ('K', 7, 7)))
[['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', 'K', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', 'K']]

>>> unsafe_squares(4, 4, (('K', 0, 1), ('Q', 0, 3), ('P', 1, 2), ('Q', 1, 3)))
[['', 'K', '*', 'Q'], ['', '', 'P', 'Q'], ['*', '', '*', '*'], ['', '*', '', '*']]
>>> unsafe_squares(2, 3, (('Q', 0, 1), ('K', 0, 0)))
[['K', 'Q', '*'], ['*', '*', '*']]
>>> unsafe_squares(8, 8, (('Q', 4, 3), ))
[['', '', '', '*', '', '', '', '*'], ['*', '', '', '*', '', '', '*', ''], ['', '*', '', '*', '', '*', '', ''], ['', '', '*', '*', '*', '', '', ''], ['*', '*', '*', 'Q', '*', '*', '*', '*'], ['', '', '*', '*', '*', '', '', ''], ['', '*', '', '*', '', '*', '', ''], ['*', '', '', '*', '', '', '*', '']]
>>> unsafe_squares(8, 8, (('K', 4, 3), ('K', 7, 7)))
[['', '', '', '', '', '', '', ''], ['', '', '', '', '', '', '', ''], ['', '', '*', '', '*', '', '', ''], ['', '*', '', '', '', '*', '', ''], ['', '', '', 'K', '', '', '', ''], ['', '*', '', '', '', '*', '*', ''], ['', '', '*', '', '*', '*', '', ''], ['', '', '', '', '', '', '', 'K']]

>>> safe_squares(4, 4, (('K', 0, 1), ('Q', 0, 3), ('P', 1, 2), ('Q', 1, 3)))
6
>>> safe_squares(2, 3, (('Q', 0, 1), ('K', 0, 0)))
0
>>> safe_squares(8, 8, (('Q', 4, 3), ))
36
>>> safe_squares(8, 8, (('K', 4, 3), ('K', 7, 7)))
52