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.