A q-Queens Problem. II. The square board

作者：Chaiken Seth; Hanusa Christopher R H; Zaslavsky Thomas^*

来源：Journal of Algebraic Combinatorics, 2015, 41(3): 619-642.

DOI：10.1007/s10801-014-0547-0

• Nonattacking chess pieces
• Fairy chess pieces
• Ehrhart theory
• Inside-out polytope
• Arrangement of hyperplanes

We apply to the n x n chessboard the counting theory from Part I for nonattacking placements of chess pieces with unbounded straight-line moves, such as the queen. Part I showed that the number of ways to place q identical nonattacking pieces is given by a quasipolynomial function of n of degree 2q, whose coefficients are (essentially) polynomials in q that depend cyclically on n. Here, we study the periods of the quasipolynomial and its coefficients, which are bounded by functions, not well understood, of the piece's move directions, and we develop exact formulas for the very highest coefficients. The coefficients of the three highest powers of n do not vary with n. On the other hand, we present simple pieces for which the fourth coefficient varies periodically. We develop detailed properties of counting quasipolynomials that will be applied in sequels to partial queens, whose moves are subsets of those of the queen, and the nightrider, whose moves are extended knight's moves. We conclude with the first, though strange, formula for the classical n-Queens Problem and with several conjectures and open problems.

• 出版日期2015-5