Spivak’s Problem

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:

16 knights on a chessboard

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:

Zone 1

I called these three squares Zone 1. Similarly, we can construct 11 more zones, and each of them should contain at least one knight:

All 12 zones

This gives the lower bound of 12, and, more importantly, I can now explain my algorithm.

The 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.

Results

The results were amazing. It turned out that the answer is not 16, not 15, but 14, as illustrated below:

14-knight configuration

Generalising…

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.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

11 Responses to Spivak’s Problem

  1. apgoucher says:

    I can decrease the upper bound to 1/6 by tiling with the 6-by-4 unit cell “2o2$3b2o!”.

    Like

  2. Stuart Gascoigne says:

    I can show that your lower bound of 1/9 is unattainable.
    How can I include pictures in a comment??

    Like

    • Alexey Nigin says:

      Upload them to arbitrary site, then use the standard HTML tag:

      <img src="http://yoursite.com/image.png" />

      The last slash is optional, but WordPress seems to like it.

      Like

      • stuart gascoigne says:

        If the lower bound of 1/9 is attainable, then this is equivalent to tiling the plane with the non-contiguous tile formed by the knight and the 8 cells that it attacks.

        Firstly show that 2 knights cannot occupy adjacent cells (see fig 1). Consider the cell numbered 1. It attacks the cells 2-9. It cannot contain a knight because it would attack cells that are already attacked by the other knights, so it must itself be attacked. A knight placed on any of the cells 2-9 will either be attacked by the 2 knights or will attack a cell already attacked, with the exception of cell 6. So we place a knight in call 6 and now have fig 2. Now consider the cell numbered 10. This time all the cells which attack it are either attacked themselves or will attack cells that are already attacked. This shows that 2 knights cannot occupy adjacent cells.
        Now place a knight as in fig 3, and consider cell 1. By the first result it cannot be a knight. Of the cells that attack it, only numbers 5 & 8 are permissible. Choosing cell 5 (cell 8 is symmetrically equivalent) we get fig 4. Now consider cell 10. It cannot be a knight as it would attack cells already attacked. Any knight that would attack it would also attack cells already attacked.
        So we have proved that the knights and the cells they attack cannot tile the place without overlap and so the lower bound must be strictly larger then 1/9.

        Like

  3. Stuart Gascoigne says:

    The upper bound can be decreased to 1/7.5 by tiling with this 6×10 unit cell
    O O O O O O
    O O O O O O
    K O O O O K
    K O O O O K
    O O O O O O
    O O O O O O
    O O O O O O
    O O K K O O
    O O K K O O
    O O O O O O
    This is my 4th attempt to post this comment. WordPress doesn’t like something about it…

    Like

  4. Stuart Gascoigne says:

    The upper bound can also be decreased to 1/7.5 by tiling with this 5×12 unit cell
    O O O O O
    O O K O O
    O O K O O
    O O K O O
    O O K O O
    O O O O O
    O O O O O
    O K O O O
    O K O O O
    O K O O O
    O K O O O
    O O O O O
    My fifth attempt to post this comment…

    Like

  5. Stuart Gascoigne says:

    The upper bound can be decreased to 1/7.666 by tiling with this 23-cell non-rectangular unit cell. Place the “peg” on the right into the slot on the left, and the peg on the top into the slot on the bottom. The @ characters are background. Clearly it would look a lot prettier when turned into a proper graphic.

    @@@@@@@@@@
    @ O O@@@O @@@
    @@ O O O O O O@@
    @ O K O O O O O K@
    @ O O K @O O O@@
    @@@@@@@@@@

    If you want it as a rectangular unit cell, then it requires 23 copies of the above to give this 23×23 grid where every line, column and diagonal contains 3 knights –

    K O O O O O O O O O O K O O O O O K O O O O O
    O K O O O O O K O O O O O O O O O O K O O O O
    O O K O O O O O K O O O O O K O O O O O O O O
    O O O O O O O O O K O O O O O K O O O O O K O
    O O O O O K O O O O O O O O O O K O O O O O K
    K O O O O O K O O O O O K O O O O O O O O O O
    O O O O O O O K O O O O O K O O O O O K O O O
    O O O K O O O O O O O O O O K O O O O O K O O
    O O O O K O O O O O K O O O O O O O O O O K O
    O O O O O K O O O O O K O O O O O K O O O O O
    O K O O O O O O O O O O K O O O O O K O O O O
    O O K O O O O O K O O O O O O O O O O K O O O
    O O O K O O O O O K O O O O O K O O O O O O O
    O O O O O O O O O O K O O O O O K O O O O O K
    K O O O O O K O O O O O O O O O O K O O O O O
    O K O O O O O K O O O O O K O O O O O O O O O
    O O O O O O O O K O O O O O K O O O O O K O O
    O O O O K O O O O O O O O O O K O O O O O K O
    O O O O O K O O O O O K O O O O O O O O O O K
    O O O O O O K O O O O O K O O O O O K O O O O
    O O K O O O O O O O O O O K O O O O O K O O O
    O O O K O O O O O K O O O O O O O O O O K O O
    O O O O K O O O O O K O O O O O K O O O O O O

    I have run an exhaustive computer search to show that any rectangular unit cell which improves on this must have an area greater than 105. This doesn’t rule out a smaller non-rectangular unit cell.

    Like

  6. Stuart Gascoigne says:

    You still seem to have comment censoring switched on……

    Like

    • Alexey Nigin says:

      Yes, and it will unfortunately always be the case. WordPress has quite a few options to make the spam filtration more strict, but strangely not a single one to make it less strict.

      As for your new result, it is very awesome.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s