An 8×8 chessboard is in the shape of a torus. (This means that the board "wraps around" - you can go left from a2 and come out on h2, for instance. It also works vertically - you can go up from f8 and come out on f1.) What is the minimum number of knights you can place on the board so every square is attacked, even ones with pieces on them?
I can do it in 8:
And of course, this is the optimum, since each knight attacks 8 squares and we need to cover at least 64.
I was looking for a possible duplicate of this problem, then I found
but it doesn't imply that your question is less fascinating.
I'd answer by saying that the worst best case should be:
14
as is evident from this article.
Also, I'm currently writing a program for the best case scenario, hope will do t without bugs :)
p.s.
I've always been intrigued by Torus, especially because of K-map :D
Although there is an existing solution, it's a bit chaotic-looking to my eye, and lacks explanation of how it was created. I'd like to show a more regular solution, observe that in some sense there are no choices to be made when solving this puzzle, and also consider boards of other sizes.
First, since
a knight on a white square can only attack black squares, and vice-versa, we can simplify the problem by only attacking the 32 black squares, as the solution for the black squares can just be duplicated for the white squares.
Thus, we're trying to cover these gray squares:
Initially, all squares are equivalent due to translational symmetry on a torus, so there is effectively no choice about where to place the first knight. I will place it in the center and color the squares it covers green:
From here, if we are going to achieve a perfect cover with no doubly-attacked squares, then whatever knight attacks the square to the right of G must not attack any green square. By rotational symmetry, we again have effectively only once place to put the next knight, here colored pink:
By similar reasoning, one knight must cover the remaining two squares adjacent to G, here colored red:
At this point we have 8 uncovered squares and there is exactly one square that attacks them all, here colored yellow:
The knights on G, P, R, and Y perfectly cover all 32 black squares. Up to rotational and translational symmetry, this is the only such arrangement, as every piece's placement was forced.
For completeness, here is a placement of all 8 knights that is regular and symmetric:
The existing solution is of course equivalent modulo translations of the black and white squares separately. (And of course we could also rotate either or both to reverse the "slope" of each line.)
A comment speculated about generalization to NxN. Let's apply the same reasoning as above to the 10x10 case. If we are to achieve a perfect cover, then we again have no choice about the first three knights, here labeled G, P, and R:
If we now focus on covering the squares next to P (which is symmetric with R at this stage), the next placement (labeled Y) is also forced:
This arrangement is a somewhat difficult to process visually because the uncovered squares are mostly near the edges. Let's translate the entire board by 5 squares in each direction:
From this we can see there is only one more place to put a knight (labeled B) that will not doubly-attack anything:
This final arrangement makes it clear that a perfect cover of 10x10 is impossible. We had no meaningful choices up to this point, and are now stuck.
Generalizing, any perfect cover consists of diagonal stripes of knights. The width of that stripe is 4 black squares (or 8 squares total). Consequently, a perfect cover of an NxN torus is possible if and only if N is divisible by 8.
