Maximum number of kings on the chessboard subject to some rules

chessboardcombinatoricscontest-mathrecreational-mathematics

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?

Best Answer

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.

Related Solutions

[Math] Kings on a chessboard

If haven't done the calculations, but can tell you how they can be done for the general problem of placing $k$ kings on a $p\times q$ board.

Let $I=\{1,\ldots,p\}$ represent a column of the board. For simplicity, assume that $p\le q$. Let $\cal{C}$ be the set of subsets of $I$ so that no pair $x,x+1\in C$ for any $C\in\cal{C}$: these sets represent permitted placements of kings in a column.

Now we define a matrix $A$ with elements $A_{ij}$ for $i,j\in\cal{C}$: you may enumerate the sets in $\cal{C}$ any way you like. We define the elements $$ A_{ij}=\left\{\begin{array}{l l} 0&\text{if there are $x\in i$, $y\in j$ with $|x-y|\le1$}\\ x^{|j|}&\text{otherwise, where $|j|$ is the number of elements in $j$} \end{array}\right. $$ so $A_{ij}$ represents the addition of a column with kings in the $j$ positions after having had a column with kings in the $i$ positions.

If we let $e=\{\}\in\cal{C}$ represent the initial state, i.e. no kings to the left of the board, and successively add $q$ columns, we get $$ e\cdot A^q\cdot 1=\sum_{k} a_kx^k $$ where the $1$ represents the vector $(1,\ldots,1)$ and $a_k$ is the number of ways to place $k$ kings on the $p\times q$ board.

This is fairly ok to compute for arbitrary $k$ and $q$, but quickly gets tough is $p$ increases. That's why selecting $p\le q$ is an advantage if the board is rectangular but not square.

[Math] Place maximum Rooks on a chessboard

For most positions of the holes there seems to be room for 10 rooks.

If the holes are in the same row (not on the edge, not touching each other, and with at least two rows above and below it), then place 7 rooks as

      R
  R
R o R o R
      R
  R

There are then 3 rows and 3 columns left without anything in them yet; put the last 3 rooks there.

If the holes are in different rows and columns (but not on the edge of the board), place 6 rooks as

  R
R o R
  R o R
    R

There will be 4 rows and 4 columns yet unused; place the 4 last rooks there.

These solutions are clearly optimal for their hole placements, because each maximal horizontal or vertical run of available cells on the board contains a rook.

If the holes are too close to the edges (or to each other) for this to work, there's room for fewer rooks. Writing down exact rules for those cases seems to be tedious but doable.

If you just want an algorithm to find the maximum number of rooks rather than actually place them, one way that seems to work is to count the number of different horizontal hole-less runs of cells on the board, and the number of different vertical hole-less runs of cells on the board. The minimum of these two numbers is obviuously an upper bound on the rooks, and it can always be achieved (this I can only show with a tedious case analysis).

Best Answer

Related Solutions

[Math] Kings on a chessboard

[Math] Place maximum Rooks on a chessboard

Related Question