Two kings not in adjacent square How many ways are there to place two identical kings on an 8 x 8 chessboard so that the kings are not in adjacent squares? on an n x m chessboard?
Edit: I inserted the 'two' before 'identical'

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.
