27
$\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's the minimum number of knights you can place on the board so every square is attacked, even ones with pieces on them?

$\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
18
$\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.

$\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
  • $\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
1
$\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

$\endgroup$

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.