A054500 Indicator sequence for classification of nonattacking queens on n X n toroidal board.

1, 5, 7, 11, 13, 13, 13, 13, 17, 17, 17, 17, 17, 19, 19, 19, 23, 23, 23, 25, 25, 25, 25, 25, 25, 25, 25, 29, 29, 29, 29, 29

Offset: 1

Author

Matthias Engelhardt

Keywords

• nonn
• nice
• hard

Comments

The three sequences A054500/A054501/A054502 are used to classify solutions to the problem of "Nonattacking queens on a 2n+1 X 2n+1 toroidal board" by their symmetry; solutions are considered equivalent iff they differ only by rotation, reflection or torus shift.

For brevity, let i(n) = A054500(n) (indicator sequence), m(n) = A054501(n) (multiplicity) and c(n) = A054502(n) (count).

i(n) = k means that there are solutions for the k X k board and that m(n) and c(n) refer to it. There are c(n) inequivalent solutions which may be extended to m(n) different representations each (i.e., m(n) permutations).

This gives two formulas: A007705(n) = Sum (c(k) * m(k)), A053994(n) = Sum (c(k)), where the sum is taken over all k for which i(k) = 2n+1, for both formulas. Note that m(n) is always a divisor of 8 * i(n)^2.

Examples

			For a 19 X 19 toroidal board, you have three entries in the indicator sequence A054500; their count terms (A054502) give 354 = 4 + 132 + 218 inequivalent solutions; together with their multiplicity (A054501) they add up to 4*76 + 132*1444 + 218*2888 = 820496 solutions at all.
		

References

• A. P. Street and R. Day, Sequential binary arrays II: Further results on the square grid, pp. 392-418 of Combinatorial Mathematics IX. Proc. Ninth Australian Conference (Brisbane, August 1981). Ed. E. J. Billington, S. Oates-Williams and A. P. Street. Lecture Notes Math., 952. Springer-Verlag, 1982 (for getting equivalence classes).

Links

• Manuel Kauers and Christoph Koutschan, Guessing with Little Data, arXiv:2202.07966 [cs.SC], 2022.
• I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math.Monthly, 101 (1994), 629-639 (for finding the solutions).

Crossrefs

Cf. A054501, A054502, A053994, A007705, A006841.

Extensions

More terms from Matthias Engelhardt, Jan 11 2001