4
$\begingroup$

Suppose there's an infinite chessboard with black and white queens, such that no black queen attacks a white queen. Also, the black queens and white queens have the same density $d$ (over large square areas, say). What's the maximum $d$?

I can see how to get $d = 1/8$: put black queens on $(4i, 2j)$ (for all integers $i$, $j$) and white queens on $(4i + 2, 2j + 1)$. Roughly speaking, the black and white queens stay a knight's move away from each other. I suspect that's the best.

Note that this is different from the problem where no queen can attack any other queen; here it's OK for a black queen to attack another black queen.

$\endgroup$
2
  • $\begingroup$ How do you get $1/8$? in the (one-colored) 8 queens and extensions it is easy to see there can only be one queen on each row, so this number is highly suspect. $\endgroup$
    – vonbrand
    Feb 23, 2014 at 19:20
  • 2
    $\begingroup$ "Nonattacking" is a little misleading here: usually that means none of the queens can attack each other, but here it means that they can't attack the other color. I'll try to clarify that and add an example. $\endgroup$
    – Hew Wolff
    Feb 23, 2014 at 20:20

2 Answers 2

Reset to default
2
$\begingroup$

Martin vB's answer not only gets $d = \frac{3}{49}$ instead of $d = \frac{3}{7}$ but doesn't even work, AFAICT. Here's his pattern drawn out:

..............
......W......W
.....W......W.
....W......W..
..B......B....
.B......B.....
B......B......
..............
......W......W
.....W.!....W.
....W...!..W..
..B......B....
.B......B.....
B......B......

The !s indicate where a black queen threatens a white queen in this pattern.

However, observing that we need an extra column, not an extra row, we could use the same general principle to come up with something like this that does work:

....W.W.....W.W.
.....W.......W..
....W.W.....W.W.
B.B.....B.B.....
.B.......B......
B.B.....B.B.....
....W.W.....W.W.
.....W.......W..
....W.W.....W.W.
B.B.....B.B.....
.B.......B......
B.B.....B.B.....

The density here is a paltry $\frac{5}{48} \approx 0.104$, so it's not as good as your original

B...B...B...B...
..W...W...W...W.
B...B...B...B...
..W...W...W...W.
B...B...B...B...
..W...W...W...W.

which has a density of $\frac{6}{48} = 0.125$.

If you permit solutions that aren't "the same density everywhere", you can also get $d = 0.125$ with something like

B...............
BB..............
BBB.............
BBBB............
BBBBB...........
BBBBBB..........
BBBBBBB.........
........WWWWWWWW
.........WWWWWWW
..........WWWWWW
...........WWWWW
............WWWW
.............WWW
..............WW
...............W

(drawn out to infinity in each direction, so that one-eighth of the plane is all black and the opposite eighth is all white). I don't think you can do better than $d = \frac{1}{8} = 0.125$ by this variation, though.

If you are willing to redraw the pattern as the square gets bigger, tending to a continuous solution in the unit square, you can achieve at least $d = \frac{7}{48} \approx 0.1458$. Here's an example solution that gives you exactly $d = \frac{7}{48}$ on a 12x12 grid — but it does not tile, so there's no way to fill the plane with it.

...WW......W
...WW.....WW
...WW....WWW
...W.....WWW
.........WWW
.........WW.
.BB.........
BBB.........
BBB.....B...
BB.....BB...
B.....BBB...
.....BBBB...
$\endgroup$
1
  • $\begingroup$ This problem, the "peaceable queens problem", is discussed by N.J.A. Sloane in the Notices of the AMS (ams.org/journals/notices/201809/rnoti-p1062.pdf). See also oeis.org/A250000, where the configuration with density 7/48 appears. $\endgroup$
    – Benoit Jubin
    Mar 20, 2019 at 0:08
0
$\begingroup$

Can easily improve to d = 3/7: put black queens on (i, i) (for all integers i where 3 > i - 1 (mod 7) and white queens on (i, i+1) (for all integers i where 3 < i (mod 7).

That is, place 3 black queens on the major diagonal, followed by 3 white queens one to the right of the major diagonal, followed by a blank row, and repeat. A similar strategy permits d to approach 1/2 if you let the "large square area" become "large" enough.

$\endgroup$
1
  • $\begingroup$ I'm not quite following the part about the blank row, but this looks like a nice way to fill a (roughly) 7-by-7 rectangle, then tile the plane with a grid of these rectangles. That sounds like a density around $3/49$ rather than $3/7$. $\endgroup$
    – Hew Wolff
    May 29, 2014 at 2:25

You must log in to answer this question.

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