Knight Stuffing III

Number the chessboard as shown above. To make it easier to see how knights can attack each other, we're going to break the diagram apart so that squares that can attack each other are connected. (In more technical terms, make a graph diagram with nodes representing each of the spaces and edges connecting where knights can make a move.)

If the two knights threaten each other, they will be two connected numbers on the chart shown. Since the entirety of the graph is connected, if every space was filled such that there are equal number of black and white knights there would be no way for them to avoid threatening each other. Therefore at least some of the spaces must be empty.

Because we want to place a maximum number of knights, we want to place as few "empty spaces" as possible so the knights can be filled in without threatening each other (that is, without being connected by a line). After all the empty spaces are placed we then want all the remaining spaces to be completely filled with knights. Since we can't have opposite colors attacking each other, any connected spaces filled with knights must all be the same color.

An "empty space" will no longer be used on the graph, so all connections to a number that is empty can be removed. (In graph theory terms, we are deleting the node.) Removing spaces can cause the graph to split into "subgraphs" that aren't connected; because they aren't connected, their colors can be different. For example, the graph below shows 6 of the original spaces removed, leaving a subgraph of size 2 (2-11) and a subgraph of size 8 (1-3-6-7-10-12-15-16).

Since the black and white knights must be of equal number, we must remove an even number of spaces (in the graph, nodes). Let's start by trying trying the fewest removals possible: suppose we deleted only 2 nodes. Unfortunately, the only way to do this and break the diagram into subgraphs is by deleting either the pair 6-11 or the pair 7-10. (The former is shown below.)

In both cases we have subgraphs of size 1. 1. and 12. Since each subgraph can only be filled with all of a particular color, there is no way to meet the condition that black and white knights must be of equal number. Therefore it is impossible to solve the problem by deleting only 2 nodes.

There are multiple ways to solve the problem by deleting 4 nodes. For example, deleting 2, 3, 14, and 15 leaves subgraphs both of size 6, so there can be an equal number of white and black knights. Going back to the original numbering on the board, a possible knight configuration is shown here:

Therefore the maximum number of knights possible is $16 - 4 = 12 .$

The tiling below shows the placement of 6 black knights. The grey tiles represent the tiles that these knights threaten or would be threatened by. The white knights can be placed in the remaining 6 tiles.