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?
$\begingroup$
$\endgroup$
6
asked Sep 30, 2021 at 12:25
-
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$– TacoCommented Sep 30, 2021 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$– justhalfCommented Sep 30, 2021 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$– TacoCommented Sep 30, 2021 at 13:30
-
$\begingroup$ it's just the one main diagonal A8-H1. $\endgroup$– Dmitry KamenetskyCommented Sep 30, 2021 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$– PuzzlingFerretCommented Sep 30, 2021 at 20:05
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
6
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)
answered Sep 30, 2021 at 13:17
-
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$– AviCommented Sep 30, 2021 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$ Commented Sep 30, 2021 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$ Commented Sep 30, 2021 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$– RobPrattCommented Sep 30, 2021 at 19:01
-
1$\begingroup$ I see that we are neighbors on Al's leaderboard. $\endgroup$– RobPrattCommented Sep 30, 2021 at 20:12
$\begingroup$
$\endgroup$
Lowest I was able to get it to (so far) was 5:
Initial logic to this solution:
Trying to cover a1 first, then e4, then just hitting off the remaining squares one by one
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What is the second block supposed to represent? $\endgroup$– justhalfCommented Sep 30, 2021 at 13:32
-
$\begingroup$ @justhalf rot13(rirel gjb nqwnprag ebjf zhfg unir ng yrnfg bar dhrra) $\endgroup$– athinCommented Sep 30, 2021 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$– justhalfCommented Sep 30, 2021 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$– athinCommented Sep 30, 2021 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$– justhalfCommented Sep 30, 2021 at 13:41