Nonattacking queens in a rectangular strip

DOI10.1007/S00026-011-0068-7MaRDI QIDQ659600zbMATH OpenOpenAlexWikidataFDO

Authors Seth Chaiken, Christopher R. H. Hanusa, Thomas Zaslavsky

Publication date 24 January 2012

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.5087

zbMATH Keywords

generating functionaffinographic arrangement of hyperplanesfairy chess piecesnonattacking chess piecesweighted integral gain graph

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Other designs, configurations (05B30) Signed and weighted graphs (05C22) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Recreational mathematics (00A08)

Abstract: The function that counts the number of ways to place nonattacking identical chess or fairy chess pieces in a rectangular strip of fixed height and variable width, as a function of the width, is a piecewise polynomial which is eventually a polynomial and whose behavior can be described in some detail. We deduce this by converting the problem to one of counting lattice points outside an affinographic hyperplane arrangement, which Forge and Zaslavsky solved by means of weighted integral gain graphs. We extend their work by developing both generating functions and a detailed analysis of deletion and contraction for weighted integral gain graphs. For chess pieces we find the asymptotic probability that a random configuration is nonattacking, and we obtain exact counts of nonattacking configurations of small numbers of queens, bishops, knights, and nightriders.

Recommendations

• A q-queens problem. I: General theory
• A $q$-Queens Problem. III. Nonattacking Partial Queens
• A \(q\)-queens problem. II: The square board
• A \(q\)-queens problem. V: Some of our favorite pieces: queens, bishops, rooks, and nightriders
• A \(q\)-queens problem. VI. The bishops' period

Cites work

• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements
• Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs
• The On-Line Encyclopedia of Integer Sequences

Cited in

(10)

• A \(q\)-queens problem. VII: combinatorial types of nonattacking chess riders
• Counting monomials
• A \(q\)-queens problem. VI. The bishops' period
• A \(q\)-queens problem. I: General theory
• Nonattacking Queens on a Triangle
• On the distribution of non-attacking bishops on a chessboard \(C\)
• scientific article; zbMATH DE number 7556143 (Why is no real title available?)
• Non-attacking Bishop and King positions on regular and cylindrical chessboards
• Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements
• The problem of pawns

Describes a project that uses

Uses Software

• OEIS
• SF

This page was built for publication: Nonattacking queens in a rectangular strip

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659600)