0
$\begingroup$

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:

  1. There is at most one king in any cell of the board.
  2. 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?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

If the number of rows and columns are multiples of $3$, you can break the board into $3 \times 3$ squares, put eight kings around the edge of each square and leave the central square empty. This gets $\frac 89$ filling fraction. This is the best you can do because each empty cell can receive at most eight kings. I am pretty sure that just cutting off rows is as good as you can do for the cases where one or both dimensions are $2 \bmod 3$. You can't for $1 \bmod 3$ because you lose some of the central squares. Here are my best shots for $12 \times 9$ and $10 \times 7$. Kings are in the red cells. enter image description here

$\endgroup$
3
  • $\begingroup$ Thanks but can there be a generalized representation for the above? $\endgroup$
    – Sumeet ten Doeschate
    Commented Dec 4, 2018 at 20:06
  • $\begingroup$ Yes, the number of blanks in a column of length $n$ that has blanks is $\lceil \frac n3 \rceil$, so the total number of blanks in $m \times n$ is $\lceil \frac m3 \rceil \cdot \lceil \frac n3 \rceil$ $\endgroup$
    – Ross Millikan
    Commented Dec 4, 2018 at 20:21
  • $\begingroup$ Thanks the problem is solved by the above formula with m and n not equal to 3 $\endgroup$
    – Sumeet ten Doeschate
    Commented Dec 4, 2018 at 20:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .