Numerical and Symbolic Studies of the Peaceable Queens Problem

Yukun Yao  Doron Zeilberger

February 14, 2019

Abstract

We discuss, and make partial progress on, the peaceable queens problem, the protagonist of OEIS sequence A250000. Symbolically, we prove that Jubin’s construction of two pentagons is at least a local optimum. Numerically, we find the exact numerical optimums for some specific configurations. Our method can be easily applied to more complicated configurations with more parameters.

Accompanying Maple package

This article is accompanied by a Maple package, PeaceableQueens.txt, available from the url

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/peaceable.html,

where readers can also find an input and an output file, and nice pictures.

Introduction

One of the fascinating problems described in the recent article [Sl2], about the great On-Line Encyclopedia of Integer Sequences, is the peaceable queens problem. It was chosen, by popular vote, to be assigned the milestone ‘quarter-million’ A-number, A250000.

The question is the following:

What is the maximal number, m, such that it is possible to place m white queens and m black queens on an n × n chess board, so that no queen attacks a queen of the opposite color.

Currently only thirteen terms are known:

n : 1 2 3 4 5 6 7 8 9 10 11 12 13
a(n) : 0 0 1 2 4 5 7 9 12 14 17 21 24

In this paper, we’d like to consider this peaceable queens problem as a continuous question by normalizing the chess board to be the unit square U := [0, 1]^{2} = {(x, y) | 0 ≤ x, y ≤ 1}. Let W ⊆ U be the region where white queens are located. Then the non-attacking region B of W can be defined as

B = {(x, y) ∈ U|∀(u, v) ∈ W, x ≠ u, y ≠ v, x + y ≠ u + v, y − x ≠ v − u}.

So the continuous version of the peaceable queens problem is to find

max_{W ∈2^{U}}(min(Area(W), Area(B))).

Considering that the queen is able to move any number of squares vertically, horizontally and diagonally, it is reasonable to let W be a convex polygon or a disjoint union of convex polygons whose boundary consists of vertical, horizontal and slope ±1 line segments, otherwise in many cases we can increase the area of white queens without decreasing the area of black queens.

In this paper, we use a list L of lists [ [a_{1}, b_{1}] , [a_{2}, b_{2}] , …, [a_{n}, b_{n}] ] to denote the n-gon whose vertices are the n pairs in the list L and whose sides are the straight line segments connecting [a_{i}, b_{i}] and [a_{i+1}, b_{i+1}], (1 ≤ i ≤ n − 1), and [a_{n}, b_{n}] and [a_{1}, b_{1}].

This paper is organized as follows. At first we look at Jubin’s construction and prove it is a local optimum. Though there is no rigorous proof, we conjecture and reasonably believe that it is indeed a global optimum at least for “the continuous chess board”, after numerous experiments with one, two and more components. Then we consider the optimal case under more restrictions, or under certain configurations, e.g., only one component or two identical squares or two identical triangles, etc. In some cases, the exact optimal parameters and areas can be obtained.

Jubin’s Construction

As mentioned in [Sl2] (and [Sl1], sequence A250000), it is conjectured that Benoit Jubin’s construction given in Fig. 5 of [Sl2], see also here:

http://sites.math.rutgers.edu/~zeilberg/tokhniot/peaceable/P1.html

or Figure 1, is optimal for n ≥ 10. Its value is ⌊\frac{7n^{2}}{48} ⌋.

While we are, at present, unable to prove this, we did manage to prove that when one generalizes Jubin’s construction and replaces the sides of the two pentagons with arbitrary parameters (of course subject to the obvious constraints), then Jubin’s construction is indeed (asymptotically) optimal, i.e. in the limit as n goes to infinity.

Theorem. Normalizing the chess board to be the unit square {(x, y) | 0 ≤ x, y ≤ 1}, if you place the white queens in the union of the interiors of the following two pentagons

[ [0, 0] , [a, a] , [a, a + b − e] , [a − e, a + b − e] , [0, b] ],

and

[ [v_{0}, 0] , [v_{0} + c, 0] , [v_{0} + c, c − 2 f + d] , [v_{0} + c − f, c − f + d] , [v_{0}, d] ],

where a, b, e, c, f, d, v_{0} are between 0 and 1 and all coordinates are nonnegative, then the black queens are located in the interiors of the pentagons

[ [v_{0}, 1] , [a, 1] , [a, v_{0}+2 c−2 f+d−a] , [\frac{1}{2} v_{0}+\frac{1}{2} d−\frac{1}{2} b+c−f, \frac{1}{2} v_{0}+\frac{1}{2} d+\frac{1}{2} b+c−f] ,

[v_{0}, v_{0} + b] ],

Figure 1: The Benoit Jubin’s Construction for a 240 by 240 Chess Board and [ [1, 1] , [v_{0}+c, v_{0}+c] , [v_{0}+c, a+b−e] , [a+b−e+v_{0}−d, a+b−e] , [1, 1+d−v_{0}] ]. The area of the white queens is

ab − \frac{1}{2} e^{2} + cd + \frac{1}{2} c^{2} − f^{2},

while the area of the black queens is

−a−\frac{3}{4} d^{2}+2 v_{0}−d−cd−ab−f^{2}−\frac{1}{2} e^{2}−\frac{3}{2} c^{2}+2 bc−2 af+3 ac+2 ad+2 cf−ec−ed+be

+ae − bf + fd + \frac{3}{2} bd − a^{2} − \frac{3}{4} b^{2} − 2 v_{0}c + \frac{1}{2} v_{0}d − \frac{1}{2} v_{0}b + av_{0} + v_{0}f − \frac{7}{4} v_{0}^{2}.

Optimally, these should be the same. Maximizing this quantity under this constraint shows that the maximum value is

\frac{7}{48},

and this is indeed achieved by Jubin’s construction. Place the white queens inside the pentagons

[ [0, 0] , [\frac{1}{4}, \frac{1}{4}] , [\frac{1}{4}, \frac{1}{2}] , [\frac{1}{6}, \frac{1}{2}] , [0, \frac{1}{3}] ],

and

[ [\frac{1}{2}, 0] , [\frac{3}{4}, 0] , [\frac{3}{4}, \frac{1}{4}] , [\frac{2}{3}, \frac{1}{3}] , [\frac{1}{2}, \frac{1}{6}] ].

With these placements, the black queens reside inside the pentagon

[ [\frac{1}{2}, 1] , [\frac{1}{4}, 1] , [\frac{1}{4}, \frac{3}{4}] , [\frac{1}{3}, \frac{2}{3}] , [\frac{1}{2}, \frac{5}{6}] ],

and the pentagon

[ [1, 1] , [\frac{3}{4}, \frac{3}{4}] , [\frac{3}{4}, \frac{1}{2}] , [\frac{5}{6}, \frac{1}{2}] , [1, \frac{2}{3}] ].

It seems natural that two components are the optimal because if there is only one connected component for white queens, black queens still have two connected components. From the view of symmetry, it seems good to add the other component for white queens. In the rest of the paper, it is shown that with only one connected component it is unlikely to surpass the \frac{7}{48} result. And by experimenting with three or more connected components for the white queens, it seems that it is not possible to improve on Jubin’s construction, hence we believe that it is indeed optimal (at least asymptotically).

Single Connected Component

In this section, we try to find the optimal case when W is a single connected component and when the configuration is restricted to rectangles, parallelograms, triangles and finally obtain a lower bound for the optimal case of one connected component.

A Single Rectangle

Let the rectangle for white queens be [ [0, 0] , [a, 0] , [a, b] , [0, b] ], with the obvious fact that for a rectangle with a given size, placing it in the corner will lead to the largest non-attacking area. The area for white queens is ab and the area for black queens is (1 − a − b)^{2}. We’d like to find the maximum of ab under the condition

ab = (max(1 − a − b, 0))^{2}, 0 ≤ a, b ≤ 1.

Since a and b are symmetric, the maximum must be on the line a = b. Hence the optimal case is when

a = b = \frac{1}{3}

and the largest area for peaceable queens when the configuration for white queens is a rectangle is \frac{1}{9}.

A Single Parallelogram

Let the parallelogram for white queens be [ [0, 0] , [a, a] , [a, a+b] , [0, b] ].

Note that as mentioned in the beginning of this section, because the line segment must be vertical, horizontal or of slope ±1 and the corner is the best place to locate a shape, there are only two kinds of parallelograms, the other one being [[0, 0], [b, 0], [a + b, a], [a, a]]. Obviously there are symmetric with respect to the line y = x, so let’s focus on one of them.

The area for white queens is still ab and the area for black queens is still (max(1 − a − b, 0))^{2}. So similarly with the rectangle case, the maximum area

Figure 2: The Optimal Rectangle for a 120 by 120 Chess Board \frac{1}{9} is reached when

a = b = \frac{1}{3}.

Figure 3: The Optimal Parallelogram for a 120 by 120 Chess Board

A Single Triangle

With similar arguments in the last subsection, the optimal triangle must have the format: [ [0, 0] , [0, a] , [a, a] ]. The area for white queens is

\frac{1}{2}a^{2}

and the area for black queens is

\frac{1}{2}(1 − a)^{2}.

with the condition 0 ≤ a ≤ 1. Hence, when a = \frac{1}{2} the area reaches its maximum \frac{1}{8}, which is better than the rectangle or parallelogram configuration.

Figure 4: The Optimal Triangle for a 120 by 120 Chess Board By the way, [ [0, 0] , [0, a] , [a, 0] ] won’t be a good candidate for optimal triangles because we can always extend it to a square [ [0, 0] , [0, a] , [a, a] , [a, 0] ] without decreasing the area of black queens. Then its maximum cannot exceed the maximum of rectangles, which is \frac{1}{9}.

A Single Hexagon

After looking at specific configurations in the above three subsections, we’d like to find some numerical lower bounds for the single connected component configuration. It is interesting to find out or at least get a numerical estimation how large the area of white or black queens can be if the white queens are in a single connected component. Note that from rectangles and parallelogram we get a lower bound \frac{1}{9} ≈ 0.1111 and from triangles we get a better lower bound \frac{1}{8} = 0.125.

The natural thing is that we want to place the polygon in a corner. Because of the restriction of the orientations of its sides, at most it can be an octagon. Let’s place the polygon in the lower left corner. Then we immediately realize that it is a waste if the polygon doesn’t fill the lower left corner of the unit square. It is the same for the upper right side of the polygon. If part of its vertices are [ [a, b] , [a, b+c] , [a−d, b+c+d] , [a−d−f, b+c+d] ], then we can always extend the polygon to [ …, [a, b] , [a, b+c+d] , [a−d−f, b+c+d] , …] without decreasing the area of black queens.

Hence the general shape is a hexagon

[ [0, 0] , [a, 0] , [a + b, b] , [a + b, b + c] , [d, b + c] , [0, b + c − d] ]

with four parameters. Then the area for white queens is

(a + b)(b + c) − \frac{1}{2}(b^{2} + d^{2}),

and the area for black queens is

\frac{1}{2}(1 − a − b − c)^{2} + \frac{1}{2}(1 − a − 2b − c + d)^{2}.

With the procedure MaxC1 in the Maple package PeaceableQueens.txt, we are able to find a reasonable local maximum using Lagrange multipliers when

a, c, d = \frac{1}{2}, b = 0.

The function call is MaxC1( [Area(W), Area(B)] , [a, b, c, d] ). However, actually this is the optimal triangle with an area of \frac{1}{8}.

Figure 5: The Nearly Best Lower Bound Configuration for a 100 by 100 Chess Board

To find a better numerical lower bound, we can try to fix one parameter and use the procedure MaxC. For example, if we fix a, then when a is around 0.21, MaxC( [Area(W), Area(B)] , [b, c, d] ) will return [ [0.2124117027, 0.2107168686, 0.2107168686] , 0.1339742952], which means when

a = 0.21, b = 0.2124117027, c = d = 0.2107168686

the hexagon can reach the area 0.1339742952. This is a huge improvement from the previous optimum \frac{1}{8} and is not that far from Jubin’s result \frac{7}{48} ≈ 0.1458.

When trying to fix other parameters, the returned result is quite close to this one. It means that the above parameters are quite close to the optimum. Actually when a = b = c = d, the area reaches a local maximum. In that case, we have

3a^{2} = (1 − 3a)^{2}.

Hence when

a = \frac{1}{3 + \sqrt{3}} ≈ 0.2113248654,

the area of white queens is maximized at

3a^{2} = \frac{1}{4 + 2\sqrt{3}} ≈ 0.1339745962.

The best configuration of hexagons is found and at least we have a numerical lower bound 0.1339745962 for the best single component configuration.

Two Components

Since in Jubin’s construction, there are two pentagons, it is natural to think of the optimum of certain two-component configurations. The difficulty for analyzing the two-component is that more parameters are introduced and the area formula for black queens becomes a much more complicated piece-wise function.

In this section, the cylindrical algebraic decomposition algorithm in quantifier elimination is applied to find out the exact optimal parameters and the maximum areas. Given a set S of polynomials in ℝ^{n}, a cylindrical algebraic decomposition is a decomposition of ℝ^{n} into semi-algebraic connected sets called cells, on which each polynomial has constant sign, either +, - or 0. With such a decomposition it is easy to give a solution of a system of inequalities and equations defined by the polynomials, i.e. a real polynomial system.

Two Identical Squares

To keep the number of parameters as few as possible, the configuration of two identical squares is the first we’d like to study. There are two parameters, the side length a and the x-coordinate s of the lower left vertex of the right square, the left square’s lower left vertex being the origin.

The two squares are

[ [0, 0] , [a, 0] , [a, a] , [0, a] ]

and

[ [s, 0] , [s + a, 0] , [s + a, a] , [s, a] ].

Based on this configuration, the domain is

0 ≤ a ≤ \frac{1}{2}, a ≤ s ≤ 1 − a.

The area of white queens is

2a^{2}.

Actually the formula for black queens is very complicated, especially when a is small there may be a lot of components for B. However, by experimentation (procedure FindM2Square), we found that for all mid-range s ∈ [0.24, 0.76], a around 0.23 will always maximize the area. Then we just need to focus on the shape of B when a is not far from its optimum.

The area of black queens is

(s−a)(1−s−a)+ \frac{1}{4}(s−a)^{2} +(max(1−s−2a, 0))^{2} +max(s−2a, 0)(1−s−a).

The domain for a and s is a triangle. The area formula for black queens shows that the two lines s = 2a and s = 1 − 2a separate the domain into 4 regions. In each region, we have a polynomial formula for the area of black queens. Since the area of white queens W is just a simple formula of a, we need to maximize a with the condition W = B.

Figure 6: The Nearly Optimal Two Identical Squares Configuration for a 200 by 200 Chess Board

When s ≥ 2a and s ≥ 1 − 2a, by cylindrical algebraic decomposition we obtained

\begin{cases}\frac{1}{2}(−1 + \sqrt{2}) ≤ a < \frac{1}{27}(1 + 2\sqrt{7}) & s = \frac{4+a}{7} + \frac{2}{7} \sqrt{4 − 19a + 9a^{2}} \\ \frac{1}{27}(1 + 2\sqrt{7}) ≤ a < \frac{1}{18}(19 − \sqrt{217}) & s = \frac{4+a}{7} ± \frac{2}{7} \sqrt{4 − 19a + 9a^{2}} \\ a = \frac{1}{18}(19 − \sqrt{217}) & s = \frac{4+a}{7} − \frac{2}{7} \sqrt{4 − 19a + 9a^{2}} \end{cases} .

When s ≤ 2a and s ≥ 1 − 2a, the result is an empty set.

When s ≤ 2a and s ≤ 1 − 2a, we obtained

\frac{2}{9} ≤ a ≤ \frac{1}{7}(3 − \sqrt{2}), s = 2 − 7a − 2\sqrt{−2a + 9a^{2}}.

When s ≥ 2a and s ≤ 1 − 2a, we obtained

\frac{2}{9} ≤ a ≤ \frac{1}{27}(1 + 2\sqrt{7}), s = 3a − \frac{2}{\sqrt{3}}\sqrt{1 − 7a + 12a^{2}}.

Comparing the four cases, we found that the largest area occurred in case 1, when

a = \frac{1}{18}(19 − \sqrt{217}) ≈ 0.2371711193,

s = \frac{13}{18} − \frac{1}{126}\sqrt{217} ≈ 0.6053101598.

The largest area is \frac{289}{81} − \frac{19 \sqrt{217}}{81} ≈ 0.112500281.

Two Identical Triangles

The configuration of two identical isosceles right triangles is the next to be considered. There are also two parameters, the leg length a and the xcoordinate s of the lower left vertex of the triangle on the right. Note that the slopes of both triangles’ hypotenuses are +1.

The two isosceles right triangles are

[ [0, 0] , [a, 0] , [a, a] ]

and

[ [s, 0] , [a + s, 0] , [a + s, a] ].

The domain for the two parameters a and s is also

0 ≤ a ≤ \frac{1}{2}, a ≤ s ≤ 1 − a.

The area of white queens is a^{2} and for the area of black queens, by numerical experimentation, we found that for all mid-range s ∈ [0.32, 0.68], the area is maximized when a is around 0.31. Hence for a around 0.31, we have the area of black queens is

2(s − a)(1 − s − a) + \frac{1}{2}(s − a)^{2} + \frac{1}{2}(1 − s − a)^{2} + \frac{1}{2}(max(1 − s − 2a, 0))^{2}.

When s ≥ 1 − 2a, by cylindrical algebraic decomposition we obtained

\begin{cases}\frac{1}{2}(2 − \sqrt{2}) ≤ a < \frac{1}{4}(−1 + \sqrt{5}) & s = \frac{1}{2} + \frac{1}{2} \sqrt{3 − 12a + 8a^{2}} \\ \frac{1}{4}(−1 + \sqrt{5}) ≤ a < \frac{1}{4}(3 − \sqrt{3}) & s = \frac{1}{2} ± \frac{1}{2} \sqrt{3 − 12a + 8a^{2}} \\ a = \frac{1}{4}(3 − \sqrt{3}) & s = \frac{1}{2} − \frac{1}{2} \sqrt{3 − 12a + 8a^{2}} \end{cases} .

When s ≤ 1 − 2a, we obtained

\frac{1}{11}(5 − \sqrt{3}) ≤ a ≤ \frac{1}{4}(−1 + \sqrt{5}), s = 2a − \sqrt{2 − 10a + 12a^{2}}.

Hence the area is maximized when

a = \frac{1}{4}(3 − \sqrt{3}) ≈ 0.316987298,

s = \frac{1}{2}.

The largest area is \frac{3}{4} − \frac{3}{8} \sqrt{3} ≈ 0.1004809470.

One Square and One Triangle with the Same Side Length

With the same notations as the above two subsections, let W be the union of the square

[ [0, 0] , [a, 0] , [a, a] , [0, a] ]

and the triangle

[ [s, 0] , [a + s, 0] , [a + s, a] ].

Then the area of white queens is \frac{3}{2}a^{2} and the area of black queens is

a(s − a)(1 − s − a) + \frac{1}{4}(s − a)^{2} + (max(1 − s − 2a, 0))^{2}

Figure 7: The Nearly Optimal Two Identical Triangles Isosceles Right Configuration for a 200 by 200 Chess Board

when a is around its optimum 0.27 and s ∈ [0.28, 0.72]. It is obtained that when s ≥ 1 − 2a

\begin{cases}\frac{1}{2}(−2 + \sqrt{6}) ≤ a < \frac{1}{21}(1 + \sqrt{22}) & s = \frac{4−a}{7} + \frac{1}{7} \sqrt{16 − 64a + 22a^{2}} \\ \frac{1}{21}(1 + \sqrt{22}) ≤ a < \frac{2}{11}(8 − \sqrt{42}) & s = \frac{4−a}{7} ± \frac{1}{7} \sqrt{16 − 64a + 22a^{2}} \\ a = \frac{2}{11}(8 − \sqrt{42}) & s = \frac{4−a}{7} − \frac{1}{7} \sqrt{16 − 64a + 22a^{2}} \end{cases} ,

Figure 8: The Nearly Optimal One Square and One Triangle (with the same side length) Configuration for a 200 by 200 Chess Board and when s ≤ 1 − 2a

\frac{1}{15}(6 − \sqrt{6}) ≤ a ≤ \frac{1}{21}(1 + \sqrt{22}), s = \frac{7a}{3} − \frac{1}{3}\sqrt{12 − 72a + 106a^{2}}.

Consequently, we have the maximized area when

a = \frac{2}{11}(8 − \sqrt{42}) ≈ 0.276228965

s = \frac{112}{33} − \frac{14}{33}\sqrt{42} − \frac{50}{33}\sqrt{7} + \frac{52}{33}\sqrt{6} ≈ 0.495622162.

The largest area is \frac{636}{121} − \frac{96}{121} \sqrt{42} ≈ 0.1144536616. Among the three configurations in this section, we found that this configuration with one square and one triangle has the largest area.

Future Work and Final Remarks

Our method can be easily generalized for configurations with more components and/or more parameters. For instance, let’s consider the configuration of two squares, not necessarily identical. Then there are three parameters, the side length a of the left square, the side length b of the right square and the x-coordinate s of the right square’s lower left vertex. For fixed b and s, we can find the interval of a in which the optimum is located. Then for each fixed s, we are able to find the interval of b such that its corresponding a will lead to the largest area a^{2} + b^{2}. When the estimated optimal parameters are determined, a piece-wise function of the area of black queens follows.

The main difficulty of this peaceable queens problem lies in the number of parameters and the complexity of the area formula of black queens. When there are multiple components, as long as the number of parameters is limited, it should be still doable. For example, the configuration of three identical squares which are placed equidistantly has only one parameter, the side length a. When the chess board is 240 by 240, the optimal a is around 40, which means in the unit square the optimal side length is around \frac{1}{6}.

In conclusion, in this paper we prove Jubin’s configuration is a local optimum. Optimal cases of some certain configurations are discussed. Future work includes the exact solution of complicated configurations with numerous parameters, whether the white queens have two components under the best configuration, and proof or disproof that Jubin’s configuration is indeed the best.

Acknowledgement We are thankful to Neil J.A. Sloane for introducing us to this interesting problem. We are also grateful to Lun Zhang for interesting conversations and helpful remarks. We appreciate Shalosh B. Ekhad’s impeccable computing support.

References

[Sl1] Neil J.A. Sloane, The On-Line Encyclopedia of Integer Sequences,

https://oeis.org/ .

[Sl2] Neil J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices of the American Mathematical Society 65 #9 (Oct. 2018), 1062-1074.

Yukun Yao, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: yao at math dot rutgers dot edu .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .