31
$\begingroup$

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?

oidal

$\endgroup$
  • 2
    $\begingroup$ Welcome to Puzzling! This is a great question - I've fixed up the grammar and phrasing a bit for you. Let me know if I've accidentally changed what you meant. c: $\endgroup$ – Deusovi Jul 17 '16 at 12:28
  • $\begingroup$ It's great to see new-comers writing such good question, welcome to puzzling.SE ^_^ $\endgroup$ – ABcDexter Jul 17 '16 at 12:38
  • $\begingroup$ Wonderful question... One of the best puzzles I have seen coming from a newcomer $\endgroup$ – Sid Jul 17 '16 at 13:54
  • 1
    $\begingroup$ I found this image from this answer in TeX.SE $\endgroup$ – sampathsris Jul 18 '16 at 4:24
21
$\begingroup$

I can do it in 8:

enter image description here

And of course, this is the optimum, since each knight attacks 8 squares and we need to cover at least 64.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Kudos, by the way found a general solution that every NxN chess-board in form of a Torus can be dominated with N Knights... was proving my hypothesis O:) $\endgroup$ – ABcDexter Jul 17 '16 at 13:02
  • 1
    $\begingroup$ @ABcDexter: Can you show a proof? That's really interesting. $\endgroup$ – Deusovi Jul 17 '16 at 13:03
  • $\begingroup$ Ok, but you have to wait as my buggy program is showing it for N upto 8, i seriously need to check it for higher values of N. (can't follow hypothesis solely based on a code and intuition) $\endgroup$ – ABcDexter Jul 17 '16 at 13:09
  • $\begingroup$ And I think i am wrong, which would make me sad :/ but again, Truth(and Logic) alone triumphs... $\endgroup$ – ABcDexter Jul 17 '16 at 13:11
  • 8
    $\begingroup$ You need at least ceil(N²/8) knights for an NxN board, which is bigger than N if N > 8. The way this arrangement happens to cover every square is very fascinating, I must add. $\endgroup$ – ffao Jul 17 '16 at 15:51
2
$\begingroup$

I was looking for a possible duplicate of this problem, then I found

this interesting question.,

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

| improve this answer | |
$\endgroup$
2
$\begingroup$

The original problem

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:

Squares to attack

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:

Initial green knight

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:

Placing the pink knight

By similar reasoning, one knight must cover the remaining two squares adjacent to G, here colored red:

Placing the red knight

At this point we have 8 uncovered squares and there is exactly one square that attacks them all, here colored yellow:

Placing the yellow knight

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:

All 8 knights

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

Generalizing to NxN

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:

Placing G, P, and R onto 10x10

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:

Placing Y

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:

Translated by (5,5)

From this we can see there is only one more place to put a knight (labeled B) that will not doubly-attack anything:

Placing B

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for great visual solution. $\endgroup$ – Earlien Jul 30 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.