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 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 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 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 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 at 18:56

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.