The chess king moves one square in any direction (horizontally, vertically, or diagonally). The goal is to place as many king as possible on an r×c board subject to the following two conditions:
- There is at most one king in any cell of the board.
- Each king has at least one possible move into a free cell on the board.
I tried to solve it by placing the kings on the corners of the chess board and adding them with the squares it will occupy in the middle of the board using alternating pattern based on the floor of the number of kings placed into the remaining rows and the number of remaining columns they can be kept. I have taken into account that for a particular row and column the transpose of the chessboard will also give the same max number of kings.
However i am getting wrong answer for some cases. Please let me know if my above approach is correct or is there any generalized formula which can be derived from the above?