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.

# 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