2
$\begingroup$

I conjecture that the maximum number of black queens -- queens placed on black squares -- not threatening each other that can be placed on an $n\times n$ chessboard cannot exceed $\frac{2n}{3}$. I have not programmed this question, but have a 'lower half triangle' proof for $n=8$ (reducible to one case) and it seems that there is a similar exhaustive proof for $n=12$ (involving $79$ cases). A better approach is needed for (dis)proving this conjecture, would first like to know whether this is a known result.

Note: if this conjecture holds, it implies at once that the ratio of the numbers $B, W$ of black and white queens on an n x n chessboard (with $B + W = n$) is between $1/2$ and $2$. (On a $8\times 8$ chessboard always $B = W = 4$, on a $12\times 12$ chessboard a 'knight placement' easily yields an example of $B = 8, W = 4$.)

Source: https://mathematica.gr/forum/viewtopic.php?f=183&t=71094

$\endgroup$

1 Answer 1

6
$\begingroup$

Your conjecture is false. Consider $n=25$. You claim there can be at most $\frac{2n}{3}\approx 16.6667$ black queens. Here is a configuration with $17$ black queens.

Assuming the top left box is black:

enter image description here

Here is the C++ code I used to find a counter example.

$\endgroup$
9
  • 2
    $\begingroup$ The first counterexample is at $n=10$: Seven queens $\endgroup$ Mar 6, 2022 at 11:53
  • $\begingroup$ @DanielMathias I am assuming the top left corner is black. Is there a counter example for $n<25$? $\endgroup$ Mar 6, 2022 at 12:07
  • 1
    $\begingroup$ For even $n$, the board is symmetrical: One major diagonal is black. Just flip the solution in the link. $\endgroup$ Mar 6, 2022 at 12:10
  • $\begingroup$ Counterexamples exist for all $n>9$. Eight queens on 11x11 (White diagonals, the solution can be shifted vertically for black diagonals.) $\endgroup$ Mar 6, 2022 at 12:20
  • $\begingroup$ @DanielMathias Ahh I see the bug in my code. i assumed that you can put a queen on each line starting from the first. The first such example is n=25, but there are examples that skip lines that my code didn’t search. I’ll edit my answer $\endgroup$ Mar 6, 2022 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .