11
$\begingroup$

What is the least number of queens you need to place on the main diagonal of a 8x8 chess board such that every square is under attack?

$\endgroup$
6
  • 1
    $\begingroup$ Is "main diagonal" synonymous to "main diagonals" and include A1-H8 and A8-H1? If not, which diagonal should we focus on? $\endgroup$ Sep 30 '21 at 13:04
  • 2
    $\begingroup$ Main diagonal usually refers to A1-H8, while A8-H1 is the anti-diagonal (or vice versa, I'm not sure) $\endgroup$
    – justhalf
    Sep 30 '21 at 13:24
  • $\begingroup$ @justhalf thanks for clarifying that for us! I couldn't find it quickly on the web and was multi-tasking 🙃 $\endgroup$ Sep 30 '21 at 13:30
  • $\begingroup$ it's just the one main diagonal A8-H1. $\endgroup$ Sep 30 '21 at 14:40
  • $\begingroup$ Based on the tag wiki for combinatorics, this is not the best tag to use for your question as you only want the best combination (i.e. least number of queens) not an enumeration of all combinations? If so the optimization tag that was added by somebody else is sufficient. Please do edit to remove any tags you no longer need. $\endgroup$ Sep 30 '21 at 20:05
12
$\begingroup$

Suppose we start with a full diagonal (A1-H8), and then see which queens we can remove.

Removing any one queen is obviously fine. The other 7 queens cover all the other rows and columns, leaving only the removed queen's own square which is covered diagonally.

If we remove two queens,

things are fine if the queens are an even distance apart, but not if they are an odd distance apart. An example of the latter is when you remove adjacent queens such as A1 and B2, and these cause the companion squares A2 and B1 to be uncovered. An example of the former is when you remove A1 and C3 - the companion squares A3 and C1 are covered diagonally by the queen that lies halfway between the two removed ones at B2.

If we remove more than two queens,

every pair of removed queens must be an even distance apart, as explained before. Furthermore, there must still be a queen on the spot halfway between the removed pair of queens.
It then quickly becomes obvious that the only way to remove more than 2 queens is when you remove 3 queens that are a distance of 2 and 4 (and 2+4) apart, for example B2+D4+H8:
(lichess link)
5-queen solution

$\endgroup$
6
  • 1
    $\begingroup$ Very nice answer! Love the elaboration on patterns for removing an increasing number of queens :) (Do you think it generalizes to larger chessboards with, e.g., 2+4+8?) $\endgroup$
    – Avi
    Sep 30 '21 at 13:25
  • $\begingroup$ That is correct and well done! The other two answers are also correct. There is an interesting generalisation of this problem to larger grids, but it's not that simple. $\endgroup$ Sep 30 '21 at 14:44
  • $\begingroup$ @Avi The main arguments still hold for larger boards and will narrow down the search for good arrangements, but the number of combinations will likely explode super-exponentially like they usually do, making it hard to find the optimal solution. You can for example do 2+4+2, but who knows if that is useful as part of a larger arrangement. $\endgroup$ Sep 30 '21 at 14:52
  • 1
    $\begingroup$ Here are the minimum values for $n \times n$ boards with $n\in\{2,\dots,50\}$: 2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 17, 18, 18, 19, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 30, 31, 32, 33, 34, 35, 36, 37, 37, 38, 39, 40 $\endgroup$
    – RobPratt
    Sep 30 '21 at 19:01
  • 1
    $\begingroup$ I see that we are neighbors on Al's leaderboard. $\endgroup$
    – RobPratt
    Sep 30 '21 at 20:12
5
$\begingroup$

Lowest I was able to get it to (so far) was 5:

5 queens. They are on a8, c6, d5, e4, and g2

Initial logic to this solution:

Trying to cover a1 first, then e4, then just hitting off the remaining squares one by one

$\endgroup$
4
$\begingroup$

(almost...)

enter image description here

enter image description here

enter image description here

enter image description here

$\endgroup$
5
  • $\begingroup$ What is the second block supposed to represent? $\endgroup$
    – justhalf
    Sep 30 '21 at 13:32
  • $\begingroup$ @justhalf rot13(rirel gjb nqwnprag ebjf zhfg unir ng yrnfg bar dhrra) $\endgroup$
    – athin
    Sep 30 '21 at 13:33
  • 1
    $\begingroup$ Ah, ok. So the numbers do not represent the queens. I initially thought the numbers represent the queens, not vice versa. Ok. $\endgroup$
    – justhalf
    Sep 30 '21 at 13:36
  • $\begingroup$ Ah yes, actually the numbers represented the cells which one should attack, and the colors tell that they are the candidates to attack them. The queens should be on the main diagonal thus won't be valid on numbers :) $\endgroup$
    – athin
    Sep 30 '21 at 13:39
  • $\begingroup$ Yea, I just wasn't sure whether the main diagonals on chessboard would be the same as in other grids, since in chess number 1 starts from the bottom. $\endgroup$
    – justhalf
    Sep 30 '21 at 13:41

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.