10
$\begingroup$

How many queens does it take at minimum to occupy an empty chess board, so that whichever vacant and non-threatened square you put a knight on, the knight won't have a square to go to that is not threatened?

$\endgroup$
4
  • $\begingroup$ Like, a trapped knight? $\endgroup$ Feb 14 at 22:46
  • 1
    $\begingroup$ Is it right that the board is a standard chess board (8x8)? $\endgroup$
    – Bubbler
    Feb 14 at 22:49
  • $\begingroup$ @Bubbler That's right. $\endgroup$ Feb 14 at 23:53
  • $\begingroup$ @newQOpenGLWidget That's right. $\endgroup$ Feb 14 at 23:55
16
$\begingroup$

I think it's three.

I'm going to just copy the answer that hexonomino gave in this post

enter image description here

Reasoning:

The trick to this question is that the queen simply has to pick a color (white or black) and target make sure that every white or black square (but not both) are threatened. When a knight moves, it must alternate between white-black-white-black. So if the knight starts on a black square, it must move to a white square. However, given that all the white squares are threatened, the knight has nowhere to go. I don't think there's a solution that is possible with just two queens. Also, note that the queens must be protecting each other - the square that a queen is occupying must also be threatened, otherwise, the knight can just capture the queen and it would not be trapped.

More reasoning as to the number of queens:

I don't really have a mathematical proof (I'm not a mathematician), but it becomes pretty obvious that the queens cannot threaten all white squares, much less defend themselves. There are two constraints inherently presented when we consider this puzzle: 1) The queens must all be on a white or black square in order to maximize diagonals, and 2) Whatever square another queen is on must be able to be protected by another queen. With simply two queens, you cannot threaten all squares of a single color while protecting the other queens.

$\endgroup$
3
  • 2
    $\begingroup$ For a mathematical proof that fewer queens cannot work, one could probably start by showing that the queens must be on the same row, column or diagonal in order to protect each other (which is not entirely trivial — on a sufficiently small board other arrangements could work too), and then show that no arrangement where they do lie on the same row, column or diagonal can trap a knight in every vacant non-threatened square. But honestly, it'd probably be easier to just write a program to check all 64 × 64 = 4096 possible arrangements. $\endgroup$ Feb 15 at 10:48
  • $\begingroup$ @IlmariKaronen 64 x 63 / 2: they can't be in the same square, and we don't distinguish them $\endgroup$ Feb 15 at 21:56
  • $\begingroup$ @user3482749: …and there are actually even fewer truly distinct arrangements, since (there being no pawns involved) rotating or mirroring the arrangement won't change whether it works or not. But 4096 is a simple upper bound, and still low enough to enumerate by brute force. (252 = 64 × 63 / 16 should be a lower bound, but it won't be tight since some arrangements are mirror and/or centrally symmetric. I'd guesstimate the actual number of distinct arrangements up to symmetry to be around 300 or so.) $\endgroup$ Feb 16 at 10:32

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.