By means of the Ehrhart theory of inside-out polytopes we establish a general counting theory for nonattacking placements of chess pieces with unbounded straight-line moves, such as the queen, on a polygonal convex board. The number of ways to place $q$ identical nonattacking pieces on a board of variable size $n$ but fixed shape is (up to a normalization) given by a quasipolynomial function of $n$, of degree $2q$, whose coefficients are polynomials in $q$. The number of combinatorially distinct types of nonattacking configuration is the evaluation of our quasipolynomial at $n=-1$. The quasipolynomial has an exact formula that depends on a matroid of weighted graphs, which is in turn determined by incidence properties of lines in the real affine plane. We study the highest-degree coefficients and also the period of the quasipolynomial, which is needed if the quasipolynomial is to be interpolated from data, and which is bounded by some function, not well understood, of the board and the piece's move directions.
@article{10_37236_4093,
author = {Seth Chaiken and Christopher R. H. Hanusa and Thomas Zaslavsky},
title = {A \(q\)-queens problem. {I:} {General} theory},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {3},
doi = {10.37236/4093},
zbl = {1298.05021},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4093/}
}
TY - JOUR
AU - Seth Chaiken
AU - Christopher R. H. Hanusa
AU - Thomas Zaslavsky
TI - A \(q\)-queens problem. I: General theory
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/4093/
DO - 10.37236/4093
ID - 10_37236_4093
ER -
%0 Journal Article
%A Seth Chaiken
%A Christopher R. H. Hanusa
%A Thomas Zaslavsky
%T A \(q\)-queens problem. I: General theory
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4093/
%R 10.37236/4093
%F 10_37236_4093
Seth Chaiken; Christopher R. H. Hanusa; Thomas Zaslavsky. A \(q\)-queens problem. I: General theory. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/4093
