combinatoricspuzzle
In how many ways can we place two opposite kings on an empty
chessboard in accordance with the rules of chess?
I have drawn an diagram presenting two scenarios – when the first king takes away 4 squares (label A) and some scenarios when it takes 6 squares (label B). However, the squares taken away started to overlap. How would you solve this problem?
HINT: A corner square has $3$ neighbors; an edge square that is not in a corner has $5$ neighbors; and every non-edge square has $8$ neighbors. That means that if one king is in a corner, there are $mn-4$ possible locations for the other, and if one king is on an edge but not in a corner, there are $mn-6$ possible locations for the other. If one king is on any non-edge square, how many possible locations are there for the other king?
Now imagine a graph with a vertex for each square of the board and an edge between two vertices if and only if they are not adjacent. The number of edges in this graph is the number of ways to place two non-adjacent kings on an $m\times n$ board. The $4$ vertices corresponding to the corner squares will each have degree $mn-4$: each of them will be connected by an edge to $mn-4$ other vertices. What is the sum of the degrees of the vertices? How many times does that sum count each edge? How many edges are there?
If you’re not familiar with graphs, you don’t need them, but if you are, they make the argument exceptionally easy. Without them you have to realize that if you assign to each square the number of acceptable placements with one king in that square and then sum these numbers, you’re counting every acceptable placement twice.
You can instead use the same basic approach to count pairs of adjacent squares and subtract that number from the total number of ways to put two kings on an $m\times n$ board.
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.
Best Answer
You are on the right track.
In total: $$4\cdot 60+24\cdot 58+36\cdot 55. $$
Alternatively: There are $64\cdot 63$ ways to place the kings without respecting the rules (except that they are on different squares). Subtract invalid positions: There are $7\cdot 8$ positions with the black king directly to the east of the white king; the same holds for west, north, and south. And there are $7\cdot 7$ positins with the black king south-east of the white king; the same for south-west, north-west, north-est.
Hence: $${64\cdot 63}-4\cdot 56-4\cdot 49. $$