| |||||||||||||||||||||
How many ways can 8 non-attacking queens or other pieces be placed on a chess board? These problems stimulate programmers to learn and optimize backtracking search techniques. But general estimates, principles and formulas remain elusive. Toward those ends, we fix the number of pieces q and we parametrize the board by its width n in two ways: (1) Fixed height and (2) fixed square shape. We then obtain two algebraic formulations and apply their interpretations as counting gain graph colorings and counting lattice points.
Theories of lattice point counting in affinographic hyperplane arrangements (counting gain graph colorings, equivalently) due to Forge and Zaslavsky, and in inside-out polytopes due to Beck and Zaslavsky, are applied to demonstrate that the corresponding counting functions F(n) are piecewise polynomial and periodically (sometimes called pseudo) polynomial in form, respectively.
We also contrast two explicit placement enumeration techniques: Deletion and contraction on weighted gain graphs, due to Forge and Zaslavsky, is better for counting because counts from smaller problems can be subtracted. A more complicated constraint propagation method might be better for listing because only valid subplacements are generated.
This work is being done jointly with Chris Hanusa and Thomas Zaslavsky of Binghamton University.
Refreshments at 4:15 pm in ES 152.