Numerical and Symbolic Studies of the Peaceable Queens Problem
By Yukun Yao and Doron Zeilberger
.pdf
[Appeared in Experimental Mathematics v. 31 (2022), issue 1, 269-279]
First Written: Feb. 14, 2019.
Last Update of this web-page: May 21, 2019.
One of the fascinating problems mentioned in
a recent beautiful article
(Oct. 2018 issue of the Notices of the American Mathematical Society), by guru Neil Sloane,
is that of the maximal number of placing the same number of white queens and black queens on
an n by n chess board so that no queen attacks any queen of the opposite color. Benoit Jubin
found the lower-bound of [7/48 n2], that is conjectured to be the right value.
Here we don't quite prove it completely, but we do show that if one restricts attention
to configurations similar to his
construction,
consisting of the interiors of two pentagons, then it is optimal.
Added April 28, 2019: Don Knuth informed us that Jubin's construction goes back to
Stephen Ainley in 1977, see
Don Knuth's note
Added May 21, 2019: It can be found in Fig. 28(A) (p. 33) in Stephen Ainley's
delightful puzzle book.
Added May 15, 2019, watch this
great video on this problem, by
guru Neil Sloane.
Maple package
Sample Input and Output
-
If you want to see why the Jubin construction is optimal among all similar configurations where
the White Queens are located in two pentagons
input file,
yields the
output file,
-
If you want to see the same thing, but using lprint rather than print
input file,
yields the
output file,
-
If you want to see the optimal configuration with only a left-pentagon
(note that unlike the Jubin cofiguration, where the sides are all rational, now they are algebraic numbers.)
input file,
yields the
output file
According to this the best left-pentagon is
[[0, 0], [.4175485908, .4175485908], [.4175485908, .5251812616], [.1076326708,.5251812616], [0, .4175485908], [0, 0]]
giving density 0.1263228870. Not as good as 7/48, but better than 1/9.
Pictures
-
To see the Jubin configuration for a 240 by 240 chess-board, obtained by typing
PlotWB(Jubin(240),240);
in the Maple package PeaceableQueens.txt, you will get this
picture
-
If you type
AvParaTrapPw(1/4,1/3,1/2,1/4,1/6);
in the Maple package PeaceableQueens.txt, you will get this
picture
-
If you type
PlotWB(GenRect([0,0],40,40),120);
in the Maple package PeaceableQueens.txt, you will get this
picture
-
If you type
PlotWB(GenRect([0,0],30,30) union GenRect([60,0],30,30),120);
in the Maple package PeaceableQueens.txt, you will get this
picture
-
If you type
PlotWB(GenRect([0,0],22,22) union GenRect([40,0],22,22) union GenRect([80,0],22,22),120);
in the Maple package PeaceableQueens.txt, you will get this
picture
-
If you type
PlotWB(GenLeftTri([0,0],30) union GenLeftTri([40,0],30,30) union GenLeftTri([80,0],30,30),120);
in the Maple package PeaceableQueens.txt, you will get this
picture
Yukun Yao's Home Page
Articles of Doron Zeilberger
Doron Zeilberger's Home Page
