<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Nonattacking Queens in a Rectangular Strip
Seth Chaiken1, Christopher R.H. Hanusa2, and Thomas Zaslavsky2
1Department of Computer Science, University at Albany (SUNY), Albany, NY 12222, USA
2Department of Mathematical Sciences, Binghamton University (SUNY), Binghamton, NY 13902-6000, USA
chanusa@qc.cuny.edu, zaslav@math.binghamton.edu
Annals of Combinatorics 14 (4) pp.419-441 December, 2010
AMS Subject Classification: 05A15; 00A08, 05C22, 52C35
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.
Keywords: nonattacking chess pieces, fairy chess pieces, affinographic arrangement of hyperplanes, weighted integral gain graph, generating function


1. Comtet, L.: Advanced Combinatorics. D. Reidel Publishing Co., Dordrecht (1974)

2. Forge, D., Zaslavsky, T.: Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements. J. Combin. Theory Ser. A 114(1), 97--109 (2007)

3. Forge, D., Zaslavsky, T.: Colorations, orthotopes, and a huge polynomial Tutte invariant of weighted gain graphs. Submitted.

4. Hanusa, C.R.H.: The WIGG (weighted integral gain graph) programs. { http://people.qc.cuny.edu/faculty/christopher.hanusa}

5. Stanley, R.P.: Enumerative Combinatorics, Vol. 1. Wadsworth \& Brooks/Cole, Monterey, CA (1986)

6. Stembridge, J.: The SF package. { http://www.math.lsa.umich.edu/\char126jrs/maple.html\#SF}

7. Azemard, L.: Echecs et Math\'ematiques, III: une communication de Vaclav Kotesovec, Rex Multiplex 28 (1992)

8. Kot{\v e}{\v s}ovec, V.: Mezi {\v s}achovnic{\'\i} a po{\v c}{\'\i}ta{\v c}em.\\On line at {http://members.chello.cz/chessproblems/index0.htm}; find ``Between chessboard and computer'' (1996)

9. Kot{\v e}{\v s}ovec, V.: Web page with formulas. {http://web.telecom.cz/vaclav.kotesovec/math.htm\#kap12} Publication list, {http://members.chello.cz/chessproblems/articles.htm}

10. Pauls, E.: Das Maximalproblem der Damen auf dem Schachbrete. Deutsche Schachzeitung 29, 261--263 (1874)

11. N.J.A.\ Sloane, The On-Line Encyclopedia of Integer Sequences. {http://www.research.att.com/\char126njas/sequences/}

12. Tarry, H.: Presentation to the Association fran{\c c}aise pour l'avancement des sciences, Limoges, 1890. L'interm\'ediaire des math\'ematiciens 10, 297--298 (1903)