ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 549-561
https://doi.org/10.26493/1855-3974.1657.d75
(Also available at http://amc-journal.eu)
A q-queens problem VI. The bishops' period
Seth Chaiken *
Computer Science Department, The University at Albany (SUNY), Albany, NY 12222, U.S.A.
Christopher R. H. Hanusaf
Department of Mathematics, Queens College (CUNY), 65-30 Kissena Blvd., Queens, NY 11367-1597, U.S.A.
Thomas Zaslavsky
Department of Mathematical Sciences, Binghamton University (SUNY), Binghamton, NY 13902-6000, U.S.A.
Received 27 March 2018, accepted 22 August 2018, published online 31 March 2019
The number of ways to place q nonattacking queens, bishops, or similar chess pieces on an n x n square chessboard is essentially a quasipolynomial function of n (by Part I of this series). The period of the quasipolynomial is difficult to settle. Here we prove that the empirically observed period 2 for three to ten bishops is the exact period for every number of bishops greater than 2. The proof depends on signed graphs and the Ehrhart theory of inside-out polytopes.
Keywords: Nonattacking chess pieces, Ehrhart theory, inside-out polytope, arrangement of hyperplanes, signed graph.
Math. Subj. Class.: 05A15, 00A08, 05C22, 52C07, 52C35
* Chaiken and Zaslavsky thank the very hospitable Isaac Newton Institute for facilitating their work on this project.
tHanusa gratefully acknowledges support from PSC-CUNY Research Awards PSCOOC-40-124, PSCREG-41-303, TRADA-42-115, TRADA-43-127, and TRADA-44-168.
E-mail addresses: sdc@cs.albany.edu (Seth Chaiken), chanusa@qc.cuny.edu (Christopher R. H. Hanusa), zaslav@math.binghamton.edu (Thomas Zaslavsky)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
549
Ars Math. Contemp. 16 (2019) 445-463
1 Introduction
The famous n-Queens Problem is to count the number of ways to place n nonattacking queens on an n x n chessboard. That problem has been solved only for small values of n; there is no real hope for a complete solution. In this series of papers we treat a more general problem wherein we place q identical pieces like the queen or bishop on an n x n square board and we seek a formula for u(q; n), the number of ways to place them so that none attacks another. The piece may be any one of a large class of traditional and fairy chess pieces called "riders", which are distinguished by the fact that their moves have unlimited distance. We proved in Part I [4] that in each such problem the number of solutions, times a factor of q!, is a quasipolynomial function of n; that is, q!u(q; n) is given by a cyclically repeating sequence of polynomials in n and q, the exact polynomial depending on the residue class of n modulo some number p called the period of the function; and furthermore that each coefficient of the quasipolynomial is a polynomial function of q. Here we prove that for three or more bishops the period is always exactly 2.1 This period was previously observed by Kotesovec for 3 < q < 10 as a result of his extensive computations for five to ten bishops, added to previous work by Fabel for three and four bishops (see [10, pp. 126-129] for q < 6 and [11, pp. 234-241, 254-257] for q < 10).
The number of nonattacking placements of q unlabelled bishops on an n x n board is denoted by uB(q; n). The number for labelled bishops is therefore q!uB(q; n).
Theorem 1.1. For q > 3, the quasipolynomial q!uB(q; n) involved in counting the nonattacking positions of q bishops on an n x n board has period equal to 2. For q < 3 the period is 1 .
To get our results we treat non-attacking configurations as integral lattice points z := (zi,..., zq), zj = (xj, yj), in a 2q-dimensional inside-out polytope (see Section 2). The Ehrhart theory of inside-out polytopes (from [3]) implies quasipolynomiality with polynomials of degree 2q and that the period divides the least common multiple of the denominators of the coordinates of vertices of the inside-out polytope. We find the structure of these coordinates explicitly: in Lemma 4.4 we show that a vertex of the bishops' inside-out polytope has each zj G {0,1}2 or zj = (2, 2). From that, along with a formula from Part III [6] for the coefficient of n2q-6 that implies the period is even if q > 3, Theorem 1.1 follows directly.
One reason to want the period is a computational method for discovering u(q; n). To find it (for a fixed number q of pieces) one can count solutions as n ranges from 1 up to some upper limit N and interpolate the counting quasipolynomial from the resulting data. That can be done if one knows the degree of the quasipolynomial, which is 2q by [4, Lemma 2.1], and the period, for which there is no known general formula; then N = 2qp suffices (since the leading term is n2q/q! by general Ehrhart theory; see [4, Lemma 2.1]). Evidently, knowing the period is essential to knowing the right value of N, if the formula is to be considered proven. In general, for a particular rider piece and number q it is very hard to find the period; its value is known only for trivial pieces or very small values of q. In contrast, Theorem 1.1 gives the exact period for bishops, and it follows that to find the exact number of placements of q bishops it suffices to compute only 4q values of the counting function.
The reader may ask why we do not seek the complete formula for bishops placements in terms of both n and q. Remarkably, there is a simple such formula, due in essence to
1 This paper was originally announced as Part V, in Parts I and II.
S. Chaiken et al.: A q-queens problem. VI. The bishops' period
551
Arshon in a nearly forgotten paper [2] and completed by Kotesovec [11, pp. 244, 254257]. We restate this expression in Part V [8]. The trouble is that it is not in the form of a quasipolynomial, so that, for instance, we could not use it to obtain the number of combinatorial types of nonattacking configuration, which by [4, Theorem 5.3] is its evaluation at n = -1. We cannot even deduce the period from the Arshon formula.2 So there is reason to seek the general quasipolynomial q!uB(q; n) for every number q. The simple reason we do not seek to do so is that we have not found a way to do it. That remains an open problem whose solution would reveal the full character of the dependence of uB(q; n) on its two arguments. This has not yet been discovered for any rider—other than the mathematically trivial rook.
After necessary mathematical background in the next two sections, we prove Theorem 1.1 in Section 4, applying the geometry of the inside-out polytope for bishops and the properties of signed graphs, which we introduce in Sections 2 and 3, respectively. We conclude with research questions. For the benefit of the authors and readers, we append a dictionary of the notation in this paper.
2 Essentials from Parts I and II
We build upon the counting theory of previous parts as it applies to the square board, from Part II [5]. We summarize essential aspects here. First, we specialize our notation to q nonattacking bishops B on a square board. We assume that q > 0.
The full expression for the number of nonattacking configurations of unlabelled bishops
is
wB(q; n) = Yo(n)n2q + Yi(n)n2q-1 + Y2(n)n2q-2 +-----+ Y2q(n)n0,
where each coefficient Yi (n) varies periodically with n, and for labelled pieces the number is oB(q; n), which equals q!uB(q; n). (The coefficients also depend on q but we suppress that in the notation because only the variation with n concerns us here.)
The n x n board consists of the integral points in the interior (n + 1)(0,1)2 of an integral multiple (n + 1)[0,1]2 of the unit square B = [0,1]2 c R2, or equivalently, the 1/(n + 1)-fractional points in (0,1)2. Thus, the board consists of the points z = (x, y) for integers x, y = 1, 2,..., n.
A move is the difference between a new position and the original position. The bishop has moves given by all integral multiples of the vectors (1,1) and (1, -1), which are called the basic moves. (Note that for a move m = (c, d), the slope d/c contains all necessary information and can be specified instead of m itself.) A bishop in position z = (x, y) may move to any location z + ^m with ^ G Z and a basic move m, provided that location is on the board.
A configuration is the vector (z1, z2,..., zq) of positions of all q bishops. The constraint on a configuration is that no two pieces may attack each other, or to say it mathematically, when there are pieces at positions Zj and zj, then zj - zj is not a multiple of any basic move m.
The object on which our theory relies is the inside-out polytope (P, aB), where P is the hypercube [0,1]2q and AB is the move arrangement for bishops. The move arrangement is a finite set of hyperplanes whose members are the move hyperplanes or attack hyperplanes,
:= {z G R2q : (yj - y4) = ±(xj - x)}.
2Stanley in [12, Solution to Exercise 4.42] says the period is easily obtained from Arshon's formula, which has one form for even n and another for odd n; but we think it is not that easy.
552
Ars Math. Contemp. 16 (2019) 445-463
Each attack hyperplane contains the configuration points z = (zi, z2,..., zq) G Z2q in which bishops i and j attack each other. (The pieces in a configuration are labelled 1 through q to enable effective description.) The intersection lattice of A is the set of all intersections of subsets of the move arrangement, ordered by reverse inclusion. These intersection subspaces are the heart of our method.
3 Signed graphs
The signed graph we employ to describe an intersection subspace efficiently is a special case of the slope graph from [4, Section 3.3]. The fact that the bishops' two slopes are ±1 makes it possible to apply the well-developed theory of signed graphs.
A graph is r = (N, E), with node set N and edge set E. It may have multiple edges but not loops. A 1-forest is a graph in which each component consists of a tree together with one more edge; thus, each component contains exactly one circle. A spanning 1-forest is a spanning subgraph (it contains all nodes) that is a 1-forest. The notation ej means the edge has end nodes v and vj.
A signed graph, Z = (N, E, a), is a graph in which each edge e is labelled a(e) = + or -. In a signed graph, a circle (cycle, circuit) is called positive or negative according to the product of its edge signs. A signed circuit is either a positive circle or a connected subgraph that contains exactly two circles, both negative. A node v is homogeneous if all incident edges have the same sign. We generally write q := |N | because the nodes correspond to the bishops in a configuration.
Let c(Z) denote the number of components of a signed (or unsigned) graph and £(Z) := |E| - |N| + c(Z), the cyclomatic number of the underlying unsigned graph.
The incidence matrix of Z is the |N| x |E| matrix H(Z) (H is "Eta") such that, in the column indexed by edge e, the elements are n(v, e) = ±1 if v is an endpoint of e and = 0 if it is not, with the signs chosen so that, if vj and vj are the endpoints, then n(v,, e)n(vj, e) = —a(e) [13, Section 8A]. That is, in the column of a positive edge there are one +1 and one —1, while in the column of a negative edge there are two +1's or two — 1's. The rank of Z is the rank of its incidence matrix. From [13, Theorem 5.1(j)] we know a formula for the rank: rk(Z) = |N| — b(Z), where b(Z) is the number of components in which there is no negative circle. This rank function applied to spanning subgraphs makes amatroid G(Z) on the edge set of Z [13]. An unsigned graph r acts as if it is an all-positive signed graph; therefore its incidence matrix has rank rk(T) = |N| — c(T) where c(T) is the number of components and the corresponding matroid G(T) := G(+r) is the cycle matroid of r.
From this and [13, Theorem 8B.1] we also know that H(Z) has full column rank if and only if Z contains no signed circuit and it has full row rank if and only if every component of Z contains a negative circle. A signed graph that has both of these properties is necessarily a 1-forest in which every circle is negative.
A positive clique in Z is a maximal set of nodes that are connected by positive edges; equivalently, it is the node set of a connected component of the spanning subgraph Z+ formed by the positive edges. A negative clique is similar. Either kind of set is called a signed clique. We call them "cliques" (in a slight abuse of terminology) because the signed cliques of a graph do not change if we complete the induced positive subgraph on a positive clique, and similarly for a negative clique. A homogeneous node v gives rise to a singleton signed clique with the sign not represented by an edge at v; if v is isolated it gives rise to
S. Chaiken et al.: A q-queens problem. VI. The bishops' period
553
two singleton cliques, one of each sign.
The number of positive cliques in T is c(T+) and the number of negative cliques is c(T-). Let A(T) := {Ai,..., Ac(z+)} and B(T) := {Bi,..., Bc(z-)} (read "Alpha" and "Beta") be the sets of positive and negative cliques, respectively. Since each node of T is in precisely one positive and one negative clique, we can define a bipartite graph C(T), called the clique graph of T, whose node set is A(T) U B(T) and whose edge set is N, the endpoints of the edge v being the cliques A e A(T) and B e B(T) such that v e A n B.
Let us call an edge e redundant if T \ e (T with e deleted) has the same signed cliques as does T, and call T irredundant if it has no redundant edges, in other words, if each signed clique has just enough edges of its sign to connect its nodes. A signed graph is irredundant if and only if both T+ and T- are forests. For example, a signed forest is irredundant. Any signed graph can be reduced to irredundancy with the same signed cliques by pruning redundant edges one by one.
Lemma 3.1. If T is a signed graph with q nodes, then
|A(T)| + |B(T)| = 2q - [rk(T+) + rk(T-)]. If T is irredundant, then
|A(T)| + |B(T)| = 2q -IE | = q + c(T) - £(T). In particular, a signed tree has q +1 signed cliques.
Proof. The first formula follows directly from the general formula for the rank of a graph.
If T is irredundant, T+ is a forest with |A(T)| components and T- is a forest with |B(T)| components. Therefore, |A(T)| + |B(T)| = 2q - |E| = q - £(T) + c(T).
A more entertaining proof is by induction on the number of inhomogeneous nodes. Define g(T) := |A(T)| + |B(T)| - 2q + |E| = |A(T)| + |B(T)| - q - c(T) + £(T). If all nodes are homogeneous, obviously g(T) = 0. Otherwise, let v be an inhomogeneous node. Split v into two nodes, v+ and v-, incident respectively to all the positive or negative edges at v. The new graph has one less inhomogeneous node, two more signed cliques (a positive clique {v- } and a negative clique {v+}), one more node, and the same number of edges, hence the same value of g as does T. Thus, by induction, g = 0.	□
4 Proof of the bishops' period
We are now prepared to prove Theorem 1.1. We already proved in [6, Theorem 3.1] that the coefficients y» (n) are constant (as functions of n) for i < 6 and that y6 (n) has period 2. Thus it will suffice to prove that the denominator of the inside-out polytope (B, aB) for q bishops divides 2. (In fact, what we prove is the stronger result stated in Lemma 4.4.) To do this, we find the denominators of all vertices explicitly by analyzing all sets of 2q equations that determine a point. We use the polytope [0,1]2q for the boundary inequalities and the move arrangement AB for the equations of attack. We use a fundamental fact from linear algebra.
Lemma 4.1. The coordinates z = (xj, y») belong to a vertex of the inside-out polytope if and only if there are k attack equations and 2q - k boundary equations that uniquely determine those coordinates.
554
Ars Math. Contemp. 16 (2019) 445-463
We assume the q bishops are labelled Bi,..., Bq. A configuration of bishops is described by a point z = (z1, z2,..., zq) G R2q, where zj = (xj, yi) is the normalized plane coordinate vector of the ith bishop B^ that is, xj,yj G (0,1) and the position of Bj is (n + 1)zj. The bishops constraints are that z should not lie in any of the q(q - 1) bishops hyperplanes,
H+ : Xj - yj = xj - yj, H- : Xj + yj = Xj + yj,	(4.1)
where i = j. The corresponding equations are the bishops equations and a subspace U defined by a set of bishops equations is a bishops subspace. The boundary equations of [0,1]2q have the form xj = 0 or 1 and yj =0 or 1. We generalize the boundary constraints; we call any equation of the form xj = cj G Z or yj = dj G Z a fixation. We call any point of R2q determined by m bishops equations and 2q - m fixations a lattice vertex. (The term "fixation" was used in Part IV [7] only for a boundary equation; here it means any equation that fixes one coordinate at an integral value.)
The first step is to find the dimension of a bishops subspace. We do so by means of a signed graph E® with node set N := {v1,v2,..., vq} corresponding to the bishops Bj and their plane coordinates zj = (xj,yj) and with edges corresponding to the bishops hyperplanes. For a hyperplane H+ we have a positive edge e+ and for a hyperplane H-we have a negative edge e-. Thus, EB is a complete signed link graph: it has all possible edges (barring loops, of which we have no need) of both signs. For each bishops subspace U we have a spanning subgraph E(U) whose edges correspond to the bishops hyperplanes that contain U. (This is nothing other than the slope graph defined in [4, Section 3.3], except that it has extra nodes to make up a total of q.) Then U is the intersection of all the hyperplanes whose corresponding edges are in E(U).
Lemma 4.2. For any S C with corresponding signed graph Y. C E®,
codim P| S = rk(E+) + rk(E-).
For a bishops subspace U,
dim U = |A(E(U))| + |B(E(U))| and codim U = rk(E(U) + ) + rk(E(U)-).
Proof. We begin with S by looking at a single sign. Adjacent edges ej ,ejk of sign e in E, corresponding to Hj and HEjk, imply the third positive edge because the hyperplanes' equations imply that of Hfk. Consequently we may replace E(Ee) by a spanning tree of each e-signed clique without changing the intersection subspace. Call the revised graph E'. Being irredundant, it has 2q - (|A(E)| + |B(E)|) edges by Lemma 3.1. As each hyperplane reduces the dimension of the intersection by at most 1, we conclude that codim p| S < 2q - (|A(E)| + |B(E)|).
On the other hand it is clear that A® intersects in the subspace {(z,z,...,z) : z G R2}; thus, 2q - 2 = codi^p| A®. The corresponding signed graph E®, when reduced to irredundancy, consists of a spanning tree of each sign; in other words, it has 2q - 2 edges. One can choose the irredundant reduction of EB to contain E'; it follows that every hyperplane of S must reduce the dimension of the intersection by exactly 1 in order for the reduced EB to correspond to a 2-dimensional subspace of R2. Therefore, codim p| S = |E(E')| = 2q - (|A(E)| + |B(E)|) = rk(E+) + rk(E-).
The dimension formula for U follows by taking S := {H G A® : H D U}.	□
S. Chaiken et al.: A q-queens problem. VI. The bishops' period
555
Defining the rank of an arrangement A of hyperplanes to be the codimension of its intersection yields a matroid whose ground set is A. The matroid's rank function encodes the linear dependence structure of the bishops arrangement AB. The complete graph of order q is Kq.
Proposition 4.3. The matroid of the hyperplane arrangement AB is isomorphic to
G(Kq ) e G(Kq ).
Proof. The rank of S C A®, corresponding to E C E®, is the codimension of p| S, which by Lemma 4.2 equals rk(E+) + rk(E-). The matroid this implies on E(EB) is the direct sum of G(E+) and G(E-). Both E+ and E- are unsigned complete graphs. The proposition follows.	□
Now we return to the analysis of a lattice vertex z. A point is strictly half integral if its coordinates have least common denominator 2; it is weakly half integral if its coordinates have least common denominator 1 or 2. A weak half integer is an element of 1Z; a strict half integer is a fraction that, in lowest terms, has denominator 2.
Lemma 4.4. A point z = (z\,z2,... ,zq) G
determined by a total of 2q bishops
equations and fixations, is weakly half integral. Furthermore, in each zi, either both coordinates are integers or both are strict halfintegers.
Consequently, a vertex of the bishops' inside-out polytope ([0,1]2q, A®) has each zi g
{0,1}2 or zi = (2,1).
Proof. For the lattice vertex z, find a bishops subspace U such that z is determined by membership in U together with dim U fixations.
Suppose vi,vj G Ak, a positive clique in E(U); then xi - yi = xj - yj; thus, the value of xi - yi is a constant ak on Ak. Similarly, xi + yi is a constant bl on each negative clique Bl.
Now replace E(U) by an irredundant subgraph E with the same positive and negative cliques. The edges of E within each clique are a tree. The total number of edges is 2q -(|A(E(U))| + |B(E(U))|); this is the number of bishops equations in the set determining z. The remaining |A(E(U))| + |B(E(U))| equations are fixations.
Write CU for the clique graph C(E) = C(E(U)). Let tCu be the graph CU with each edge vi replaced by two edges called vf and V. If we (arbitrarily) regard x as - and y as +, this is a signed graph.
We defined ak and bl in terms of the xi and yi. We now reverse the viewpoint, treating the a's and b's as independent variables and the x's and y's as dependent variables. This is possible because, if Ak,Bl are the endpoints of vi in CU,then xi-yi = ak and xi+yi = bl, so
xi = x(ak + bi) and yi = -(-ak + bi);
2
in matrix form,
where x = [xi]q=1, y = j
x	1	"H(-CU)T"		a
y	= 2	H(+Cu)t		b
2
= 2 H(TCu)1
(4.2)
= ak
|A(Z(u))|
and b
|B(Z(u))|
1 j - L j j=l>~~ L"kJk=1 -----= LblJl = 1 are column
vectors and H(eCU) is the incidence matrix of CU with, respectively, all edges positive for
q
556
Ars Math. Contemp. 16 (2019) 445-463
e = + (with - and + at the A and B ends) and all edges negative for e = - (with + at both ends). Thus, the first coefficient matrix is the transposed incidence matrix of ^CU written with a particular ordering of the edges.
Fixing a total of |A(Z(U))| + |B(Z(U))| variables xil,... andyj1,... should determine all the values xi, yi,..., xq,yq. The fixations of z correspond to edges in ^CU so we may treat a choice of fixations as a choice of edges of tCu, where fixing xi or yi corresponds to choosing the edge vf or v\. We need to know what kind of edge set the fixations correspond to. Let denote the spanning subgraph of tCu whose edges are the chosen edges. The fixation equations can be written in matrix form as
M1
= 2
yj i
= 2
(4.3)
x
ii
where the fixation edges are vf,... with endpoints Akl,Bll,... and j,... with endpoints
Ak* ,Bi>,...; the fixations are xir = cr and yjs = ds; c = [cr] ^ and d = [ds] ^ are column vectors (with r + s = |A(Z(U))| + |B(Z(U))|, the total number of fixations); and M is an (|A(Z(U))| + |B(Z(U))|) x (|A(Z(U))| + |b(Z(U))|) matrix representing the relationships between the a's and b's and the fixed variables:
xi1		yji	
	" 1 ••	0 ••• "	
	0 ••	-1 •••	A(Z(U))
M :=			
	1 ••	0 •••	
	0 ••	1 •••	B(Z(U))
The rows of M are indexed by the signed cliques and the columns are indexed by the fixations. The column of a fixation involving a node vi, whose endpoints in CU are Ak and Bi, has exactly two nonzero entries, one in row Ak and one in row Bt, whose values are, respectively, 1,1 for an x-fixation and -1,1 for a y-fixation. Thus, each column has exactly two nonzero elements, each of which is ±1.
Consequently, M is the incidence matrix of a signed graph, in fact, M = H(Wz). M must be nonsingular since the fixed x's and y's uniquely determine the a's and b's (because they determine z). It follows (see Section 3) that the fixation equations for z are a set corresponding to a spanning 1-forest in ^CU in which every circle is negative. This 1-forest is There is choice in the selection of but it is not completely arbitrary. Let Jz be the set of nodes vi such that zi is integral; consider Jz as a subset of E(CU). As fixations must be integral, E(Wz) must be a subset of ±Jz. As fixations are arbitrary integers, may be any spanning 1-forest of ^CU that is contained in ± Jz and whose
S. Chaiken et al.: A q-queens problem. VI. The bishops' period
557
circles are negative. Thus we have found the graphical form of the equations of a lattice vertex.
Example 4.5. For an example, suppose there are three positive and four negative cliques, so A(Z(U)) = {Ai,A2,As} and B(E(U)) = {Bi, B2, B3, B4}, and eight nodes, N = jvi,..., v8}, with the clique graph CU shown in Figure 1.
• B4
Figure 1: The clique graph CU.
An example of a suitable 1-forest	Ç is shown in Figure 2. It corresponds to fixations
xi = ci, y2 = di, X3 = c2,	X4 = C3, y5 = ¿2, xr = C4, yr = ¿3. The incidence matrix is
M := H(Vz)
Xi	X3	X4	X7	y2	y5	yr	
1	0	0	0	-1	0	0	Ai
0	1	1	0	0	-1	0	A2
0	0	0	1	0	0	-1	A3
1	1	0	0	0	0	0	Bi
0	0	1	0	1	0	0	B2
0	0	0	0	0	1	0	B3
0	0	0	1	0	0	1	B4
Every column has two nonzeros. The equations of the fixations in matrix form are
M1
ai		Xi		Ci
«2		X3		c2
a3		X4		c3
bi	= 2	xr	=2	c4
62		y2		di
63		y5		¿2
64		yr		
where the q's and dj 's are any integers we wish in the lemma (but in the application to
558
Ars Math. Contemp. 16 (2019) 445-463
Theorem 1.1 they will be 0's and 1's). The solution is
ai = xi - X3 + X4 - y2 = ci - + C3 - di,
= -xi + X3 + X4 - y2 = -ci + C2 + C3 - di, a3 = X7 - yr = C4 - d3,
bi = xi + X3 - X4 + y2 = ci + C2 - C3 + di,
62	= xi - X3 + X4 + y2 = ci - C2 + C3 + di,
63	= -xi + X3 + X4 - y2 + 2y5 = -ci + c2 + c3 - di + 2d2,
64	= xr + yr = c4 + d3,
and the unfixed variables are
ai + 62
X2 = -2- = ci - c2 + c3,
a2 + b3	, ,	j 1 j
X5 = -2- = -ci + c2 + c3 - di + d2,
a3 + 63 -ci + c2 + c3 + c4 - di + 2d2 - d3
X6 = —2~ =-2-,
-ai + 6i , , yi =-2-= c2 - c3 + di,
-a2 + 6i y3 = -2- = ci - c3 + di,
-a2 + 62 , , y4 = -2- = ci - c2 + di,
-a3 + 63 -ci + c2 + c3 - c4 - di + 2d2 + d3 y6 = ^^ =-2-•
Observe that x6 and y6 are the only possibly fractional coordinates and their difference, x6 - y6 = a3 = c4 - d3, is integral; therefore, either z6 is integral, or both x6 and y6 are half integers and z6 = (i, i) if z G [0,1]2q.
We are now prepared to prove Lemma 4.4. We need a result from (e.g.) [9], which can be stated:
S. Chaiken et al.: A q-queens problem. VI. The bishops' period
559
Lemma 4.6. The solution of a linear system with integral constant terms, whose coefficient matrix is the transpose of a nonsingular signed-graph incidence matrix, is weakly halfintegral.
Proof. The way in which this is contained in [9] is explained in [1, p. 197].
□
Since M is the incidence matrix of a signed graph, and since the constant terms in Equation (4.3), being twice the fixed values, are even integers, the a's and b's are integers by Lemma 4.6. The remaining x's and y's are halves of sums or differences of a's and b's, so they are weak half-integers. The exact formula is obtained by substituting Equation (4.3) into Equation (4.2):
l-i T
H (tCuY(M-l)
(4.4)
□
Theorem 1.1 is an immediate corollary of Lemma 4.4.
5 Open questions
5.1 Coefficient periods
We proved that je (n) is the first coefficient that depends on n, having period 2. We guess that every coefficient after je(n) also has period 2.
5.2 Subspace structure
We have not been able to find a complete formula for all q. By our method, that would need a general structural analysis of all subspaces, which is too complicated for now. We propose the following problem: Give a complete description of all subspaces, for all q, in terms of signed graphs. That is, we ask for the slope matroid (see [4, Section 7.3]). The signed-graphic frame matroid G(Z) ([13, Theorem 5.1], corrected and generalized in [15, Theorem 2.1]), while simpler than the slope matroid, perhaps could help find a description of the latter.
5.3 Similar two-move riders
The slope matroid for the bishop is simple compared to those for other riders. We wonder if riders with two slopes that are related by negation (that is, the basic moves are symmetrical under reflection in an axis), or negation and inversion (that is, the basic moves are perpendicular), may be amenable to an analysis that uses the bishops analysis as a guide.
5.4 Other two-move riders
We expect that finding formulas for any rider with only two basic moves is intrinsically easier than for riders with more than two and can be done for all such riders in a comprehensive though complicated manner.
561
Ars Math. Contemp. 16 (2019) 445-463
Dictionary of notation
b(Z)	# of signed-graph components with no negative circle (p. 552)
c(r), c(Z)	# of components of a graph (p. 552)
c(Z± )..................# of positive or negative cliques (p. 553)
d/c	slope of a line or move (p. 551)
(c, d)	coordinates of a move vector m (p. 551)
ci, di ...................fixation equation constants (p. 554)
e	edge of a (signed) graph (p. 552)
ej	edge of a signed graph with sign e and end nodes vi, vj (p. 554)
g(Z)....................function on a signed graph (p. 553)
k, l indices in the clique graph (p. 555) m = (c, d) basic move (p. 551) n ......................size of a square board
oB(q; n)	# of nonattacking labelled configurations (p. 551)
p	period of a quasipolynomial (p. 550)
q ......................# of pieces on a board (p. 550)
q	# of nodes in a (signed) graph (p. 552)
r, s	indices of fixations (p. 556)
uB(q; n) ................# of nonattacking unlabelled configurations (p. 550)
v	node in a signed graph (p. 552)
z = (x, y), zi = (xi, yi) piece positions (p. 551)
a, b....................clique vectors (p. 555)
c, d	fixation vectors (p. 556)
x, y	x, y coordinate vectors of a configuration (p. 555)
z = (z\,... ,zq ) ........a configuration in R2q (p. 554)
Yi (n)	coefficient of uB (p. 551)
e	sign of an edge (p. 554)
£ ......................cyclomatic number (p. 552)
a	sign function of the signed graph S (p. 552)
rk	rank of the incidence matrix of a (signed) graph (p. 552)
Ak,Bl .................positive, negative cliques (p. 552)
C(Z)	clique graph (p. 553)
CU = C(Z(U))	clique graph (p. 555)
E......................edge set of a graph (p. 552)
G	matroid on ground set E (p. 552)
Jz	set of vertices zi in the configuration z such that zi is
integral (p. 556)
Kq.....................complete graph (p. 555)
M	incidence matrix H(Wz) (p. 556)
N	node set of a graph (p. 552)
aB.....................move arrangement of bishops B (p. 551)
B	board polygon [0,1]q (p. 551)
bishops hyperplane (p. 550)
(P, A) .................inside-out polytope (p. 551)
S	subarrangement (p. 554)
U	subspace in the intersection lattice of an arrangement (p. 554)
S. Chaiken et al.: A q-queens problem. VI. The bishops' period
229
R......................real numbers
Z	integers
B	bishop (p. 551)
A(Z), B(Z).............sets of positive, negative cliques (p. 552)
r	graph (p. 552)
H	incidence matrix (read "Eta") of a (signed) graph (p. 552)
Z......................signed graph (p. 552)
Z(U)	signed graph of the bishops subspace U (p. 554)
subgraph for a vertex z (p. 556)
References
[1]	G. Appa and B. Kotnyek, A bidirected generalization of network matrices, Networks 47 (2006), 185-198, doi:10.1002/net.20108.
[2]	S. E. Arshon, Resheniye odnoy kombinatornoy zadachi, Mat. Prosveshchenie Ser. 1 8 (1936), 24-29, http://mi.mathnet.ru/eng/mp694.
[3]	M. Beck and T. Zaslavsky, Inside-out polytopes, Adv. Math. 205 (2006), 134-162, doi:10.1016/ j.aim.2005.07.006.
[4]	S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, A q-queens problem. I. General theory, Electron. J. Combin. 21 (2014), #P3.33 (28 pages), https://www.combinatorics.org/ojs/ index.php/eljc/article/view/v21i3p33.
[5]	S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, A q-queens problem. II. The square board, J. Algebraic Combin. 41 (2015), 619-642, doi:10.1007/s10801-014-0547-0.
[6]	S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, A q-queens problem. III. Nonattacking partial queens, submitted, arXiv:1402.4886 [math.CO].
[7]	S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, A q-queens problem. IV. Attacking configurations and their denominators, submitted, arXiv:1807.04741 [math.CO].
[8]	S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, A q-queens problem. V. Some of our favorite pieces: Queens, bishops, rooks, and nightriders, under revision, arXiv:1609.00853 [math.CO].
[9]	D. S. Hochbaum, N. Megiddo, J. Naor and A. Tamir, Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, Math. Programming Ser. B 62 (1993), 69-83, doi:10.1007/bf01585160.
[10]	V. Kotesovec, Non-Attacking Chess Pieces, self-published online book, 3rd edition, 2011, http://www.kotesovec.cz/math.htm.
[11]	V. Kotesovec, Non-Attacking Chess Pieces, self-published online book, 6th edition, 2013, http://www.kotesovec.cz/math.htm.
[12]	R. P. Stanley, Enumerative Combinatorics, Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2nd edition, 2012.
[13]	T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), 47-74, doi:10.1016/ 0166-218x(82)90033-6.
[14]	T. Zaslavsky, Erratum: "Signed graphs", Discrete Appl. Math. 5 (1983), 248, doi:10.1016/ 0166-218x(83)90047-1.
[15]	T. Zaslavsky, Biased graphs. II. The three matroids, J. Comb. Theory Ser. B 51 (1991), 46-72, doi:10.1016/0095-8956(91)90005-5.