Thursday, April 21st, 2011
2:00pm - 3:00pm, in Science 2-066

Thomas Zaslavsky

Binghamton University

Nonattacking Chess Pieces: The Bishops' Dance

Abstract: Recreational chess fans (of Western chess) have asked questions like: What is the largest number of identical pieces (queens, or bishops, or ...) that can be placed on a chessboard so none attacks any other? Some have tried to solve a harder question: Given q identical pieces, how many ways can they be placed on an n x n chessboard? Here q is fixed, n is variable. For some chess pieces the answer, surprisingly, is given by a cyclically repeating sequence of polynomials in n. This can be proved by geometry. To find the polynomials one must know how long the sequence is (the 'period'). That can be partly solved by geometry, but it is hard. The bishop moves and attacks diagonally any distance. Seth Chaiken, Chris Hanusa, and I have found that the bishop requires only 2 polynomials, no matter how many bishops one has. The proof uses the geometric theory of signed graphs. Vaclav Kotesovec has found amazingly many formulas for non-attacking chess pieces, but no proofs. Our theorem implies (I think) that his method of computation is strong enough to give correct formulas for the bishops. His formulas show surprising properties, some of which we think we'll be able to prove. I will explain the geometry and graph theory that lies behind all the foregoing assertions.