Nonattacking queens in a rectangular strip

DOI10.1007/S00026-011-0068-7zbMATH Open1233.05022arXiv1105.5087OpenAlexW2100649005WikidataQ60691903 ScholiaQ60691903MaRDI QIDQ659600FDOQ659600

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

Publication date: 24 January 2012

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

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.

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

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

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)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs
• Title not available (Why is that?)
• Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements

Cited In (7)

• A q-queens problem. VI. The bishops' period
• Counting monomials
• Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements
• Title not available (Why is that?)
• Non-attacking Bishop and King positions on regular and cylindrical chessboards
• A \(q\)-queens problem. I: General theory
• Nonattacking Queens on a Triangle

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)