7
$\begingroup$

Given an 8x8 chessboard, your goal is to "cover" each space on the board. A space is "covered" if there is a piece on it, or if a piece on the board can be moved to that space in one move.

If you have $n$ Queens, what is the minimum number of added Knights you have to have to do this?

Can we solve this for $n = 1, 2, 3, 4$ ? For $n = 5$ the answer is zero of course.

Each Queen covers at most 29 new squares and each Knight covers at most 9. So we know that we need at least $4, 2, 0, 0$ Knights $n = 1, 2, 3, 4$ . However, we also know we need at least one Knight for $n < 5$.

$\endgroup$
  • $\begingroup$ I assume $n$ is the number of queens? $\endgroup$ – Aza Jun 6 '14 at 13:33
  • $\begingroup$ @Emrakul Yes, exactly. $\endgroup$ – Lembik Jun 6 '14 at 13:34
7
$\begingroup$

enter image description here

You provided a lower bound. These were done by hand or by referencing other answers and should provide an upper bound. I would love to see which ones can be reduced further. I am fairly confident in 0 and 3 queens but less so on 1 and 2. 4 and 5 queens of course have already been pointed out on this site.

While I thought this was self explanitory in conjunction with the question i want to be clear: Kn stands for knights, Q stands for queens, Maroon squares are ones convered by the queens, Orange squares are ones covered by the knights.

I've made a large mistake on this question. I forgot to take into account the fact that queens cannot jump over knights to attack squares accross from them. The next figure does better:

enter image description here

$\endgroup$
  • $\begingroup$ Ah now I understand -_- in Dutch the K is for King. And the P is for horse/knight (paard) $\endgroup$ – martijnn2008 Jun 6 '14 at 20:43
  • $\begingroup$ Sorry, the question is about knights and I did not know that. $\endgroup$ – kaine Jun 6 '14 at 20:50
  • $\begingroup$ Why did this answer get a down vote? $\endgroup$ – Lembik Jun 6 '14 at 20:55
  • 1
    $\begingroup$ Also, it wouldn't be too hard to check all of the QQQNNN positions with a computer to check whether the minimum number of knights for three queens is 4; there are just (64C3)*(61C3) ~= 1.5 billion of them, well within an afternoon's computing time on even a midrange machine with a not-too-optimized algorithm. I don't have the time today but may poke at this if I get a chance over the weekend. $\endgroup$ – Steven Stadnicki Jun 6 '14 at 22:36
  • 1
    $\begingroup$ Why don't use the symbol instead of a letter? ♘♞ $\endgroup$ – martijnn2008 Jun 6 '14 at 23:52
4
$\begingroup$

kaine's position for zero queens is optimal. $\:$ Proof:

Consider a 2-by-2 corner block such as {a1,a2,b1,b2}. $\:$ Clearly, a knight that occupies any of those squares doesn't attack any of those squares. $\:$ Since the only squares from which a knight can attack a1 are b3 and c2, a knight that attacks a1 doesn't attack any of the other three squares in the 2-by-2 corner block. $\:$ Since a knight changes the color of its square with each of its moves, a knight that attacks b2 doesn't attack a2 or b1. $\:$ By the previous three sentences, that 2-by-2 corner block can't be covered by less than three knights. $\:$ By how knights move, a knight that is not in the lower-left quadrant of the chess board (a1's 4-by-4 corner block) cannot help cover that 2-by-2 corner block. $\:$ Thus, if that 2-by-2 corner block is covered then there are at least three knights in the lower-left quadrant of the chess-board. $\:$ By rotational symmetry, that applies to each 2-by-2 block and the corresponding quadrant. $\:$ Thus, if the entire board is covered then there are at least three knights in each quadrant. $\:$ Since there are four quadrants and the quadrants are disjoint, 12 knights are necessary to cover the board. $\:$ Therefore kaine's position for zero queens is optimal.



Now, for stuff involving computation:

I show how to reduce the search space significantly below what was described by Steven Stadnicki,
and give the code for two Python 3 programs to brute-force the two-queen and three-queen cases.
The programs' outputs indicate that kaine's positions for two and three queens are optimal.


Consider the 8 squares {a3,a6,c1,c8,f1,f8,h3,h6}. $\:$ (That set is preserved by rotation and reflection.) $\:$ Clearly, a knight which occupies any of those squares doesn't attack any of those squares. $\:$ Since knights change color on each of their moves, a knight can't attack two squares whose nearest corners of the board share exactly one side. $\:$ By looking at the knight's move, it also can't attack two squares that [are on a diagonal and exactly two apart on that diagonal] or [have more than three rows or columns between them]. $\:$ By the previous three sentences, a single knight covers at most one of those eight squares. $\:$ In particular, if the board could be covered by QQQNNN then at least five of those squares must be covered by queens. $\:$ Furthermore, the entire problem is preserved by rotation and reflection. $\:$ Thus, one only needs to check positions of the queens that cover at least five of those 8 squares
and are "canonical" with respect to rotation and reflection. $\:$ (There are exactly 4406 such positions.)
For any position of the queens and zero or more knights, one can pick any given square that's
not yet covered, and only have to deal with positions that have a knight covering that square.
As a final optimization, I apply the previous sentence to the not-yet-been-covered square
that would minimize the number of covering-squares if there were no queens on the board.

Next, to make the coding somewhat easier, I observe that a knight can go from square_a to square_b if and only if a knight can go from square_b to square_a, and that queens "might as well" not block each other's movement, since one could just have the blocking piece move to the intended square.
The code itself is located at http://pastebin.com/DaWta3T8, since I can't figure out how to format large code blocks. $\:$ It took well over an hour to write, runs in under 20 seconds on my desktop computer, and outputs False, which indicates that kaine's position for 3 queens is optimal. $\:$ Similarly, this modified code takes about 20 seconds to run and indicates that kaine's position for 2 queens is also optimal.

$\endgroup$
  • 1
    $\begingroup$ So the fact that 4 and 5 are optimal is well known so only 1 queen has potential room for improvement? $\endgroup$ – kaine Jun 16 '14 at 12:52
  • $\begingroup$ Right. ${}{}\;$ $\endgroup$ – user1579 Jun 16 '14 at 16:40
  • $\begingroup$ Any thoughts on the optimality of the 1 queen version? $\endgroup$ – Lembik Jul 8 '14 at 16:41
  • $\begingroup$ @Lembik I doubt there the 1 queen option can be improved eiher. I wrote my own program before he wrote this answer which checked for 3 different initial queen locations and no improved ones were found. $\endgroup$ – kaine Jul 16 '14 at 19:06

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.