Long ago, Alexander Spivak posed the following problem:
The problem. What is the least number of knights that can be placed on a chessboard such that all empty squares are attacked and none of the knights is attacked?
It is not too difficult to find numerous 16-knight configurations possessing the desired properties. Here is a pretty random one:
It would seem that reducing the number of knights by one shouldn’t be too difficult, but you won’t think so after you try it. After lots of attempts, Spivak conjectured that no configurations with less than 16 knights exist. I decided to find out whether he was right or not.
Since this is a discrete problem, there are two ways to tackle it, namely "think for a while" and "do a brute-force search". The second option seemed better at first glance.
Brute-force search time estimate
Before I start writing a program, I usually estimate the running time, and fortunately I didn’t forget to do it this time.
Let’s assume that my computer can test a single configuration in 100 nanoseconds. We will need to place (in the worst case) 15 knights. Estimating the average number of choices that occur when placing a knight is complicated, but let’s assume among friends that it’s 30. Simple calculation gives us whooping 45 million years, which is definitely too much.
However, that trivial algorithm checks each configuration 15! times, and we can get rid of this issue by means of a simple trick. If we do it, the estimated time is reduced to merely 18 minutes, which seems pretty good, but… I was a massive idiot and thought this algorithm was too slow, so I implemented a completely different one (which is better, but not by wide margin). In order to explain it, I should firstly tell you what zones are.
What are zones?
The top-left corner is either occupied by a knight of attacked by a knight. That’s why there is at least one knight in the squares highlighted in the image below:
I called these three squares Zone 1. Similarly, we can construct 11 more zones, and each of them should contain at least one knight:
This gives the lower bound of 12, and, more importantly, I can now explain my algorithm.
It is actually quite simple: place a knight in every zone, then place three more knights arbitrarily. I implemented it as a Delphi console application, which can be downloaded from here and here. I initially wanted to paste the code right in the article, but then thought that WordPress would probably go crazy after seeing lots of special characters.
The results were amazing. It turned out that the answer is not 16, not 15, but 14, as illustrated below:
Probably the most boring way to generalise the problem is to change the board size. The more interesting way is to make the board infinite, and ask for the minimal density. The trivial lower bound is 1/9 (every knight attacks 8 squares), and the best upper bound I could come up with is 1/5 (fill every fifth row). Can you improve upon those bounds? If yes, the "comments" section is just for you.