A \(q\)-queens problem. I: General theory (Q740671)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A \(q\)-queens problem. I: General theory
scientific article

    Statements

    A \(q\)-queens problem. I: General theory (English)
    0 references
    0 references
    0 references
    9 September 2014
    0 references
    Summary: 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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    nonattacking chess pieces
    0 references
    fairy chess pieces
    0 references
    Ehrhart theory
    0 references
    inside-out polytope
    0 references
    arrangement of hyperplanes
    0 references
    0 references