A051906 Number of ways of placing n nonattacking queens on an n X n toroidal chessboard.

1, 0, 0, 0, 10, 0, 28, 0, 0, 0, 88, 0, 4524, 0, 0, 0, 140692, 0, 820496, 0, 0, 0, 128850048, 0, 1957725000, 0, 0, 0, 605917055356, 0, 13404947681712, 0, 0, 0

Offset: 1

Author

Matthias Engelhardt, Dec 17 1999

Keywords

• nonn
• nice
• hard
• more

Comments

The sequence has been computed up to n = 23 by Rivin, Vardi & Zimmermann, see p. 637 of their paper from 1994. Further terms were calculated by the submitter, Dec 17 1999 and Jan 11 2001.

a(n) is divisible by n.

Only terms indexed by odd numbers coprime to 3 are nonzero, therefore A007705(n) = a(2n+1) is the main entry. - M. F. Hasler, Jul 01 2019

From Eduard I. Vatutin, Nov 27 2023: (Start)

For n <= 11 all solutions can be found using a knight moving with some displacements dx and dy starting from some cell with coordinates (x,y): (x,y) -> (x+dx,y+dy) -> (x+2*dx,y+2*dy) -> ... -> (x,y) (all operations modulo n). For n >= 13 some solutions are same, but not all (see examples).

All solutions of n-queens problem on toroidal chessboard are also solutions of n-queens problem on classical chessboard; the converse is not true, so a(n) <= A000170(n).

(End)

Examples

			From _Eduard I. Vatutin_, Nov 27 2023: (Start)
n=5 (all 10 solutions are shown below):
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
| Q . . . . | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
| . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | Q . . . . |
| . . . . Q | | . Q . . . | | Q . . . . | | . . Q . . | | . . . Q . |
| . Q . . . | | . . . . Q | | . . Q . . | | Q . . . . | | . Q . . . |
| . . . Q . | | . . Q . . | | . . . . Q | | . . . Q . | | . . . . Q |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
| . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | . . . . Q |
| . . . . Q | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
| . Q . . . | | . . Q . . | | . . . . Q | | . . . Q . | | Q . . . . |
| . . . Q . | | . . . . Q | | . . Q . . | | Q . . . . | | . . . Q . |
| Q . . . . | | . Q . . . | | Q . . . . | | . . Q . . | | . Q . . . |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
n=7:
+---------------+
| Q . . . . . . |
| . . . Q . . . |
| . . . . . . Q |
| . . Q . . . . |
| . . . . . Q . |
| . Q . . . . . |
| . . . . Q . . |
+---------------+
n=11:
+-----------------------+
| Q . . . . . . . . . . |
| . . Q . . . . . . . . |
| . . . . Q . . . . . . |
| . . . . . . Q . . . . |
| . . . . . . . . Q . . |
| . . . . . . . . . . Q |
| . Q . . . . . . . . . |
| . . . Q . . . . . . . |
| . . . . . Q . . . . . |
| . . . . . . . Q . . . |
| . . . . . . . . . Q . |
+-----------------------+
n=13 (first example can be found using a knight moving from cell (1,1) with dx=1 and dy=2, second example can't be obtained in the same way):
+---------------------------+ +---------------------------+
| Q . . . . . . . . . . . . | | Q . . . . . . . . . . . . |
| . . Q . . . . . . . . . . | | . . Q . . . . . . . . . . |
| . . . . Q . . . . . . . . | | . . . . Q . . . . . . . . |
| . . . . . . Q . . . . . . | | . . . . . . Q . . . . . . |
| . . . . . . . . Q . . . . | | . . . . . . . . . . . Q . |
| . . . . . . . . . . Q . . | | . . . . . . . . . Q . . . |
| . . . . . . . . . . . . Q | | . . . . . . . . . . . . Q |
| . Q . . . . . . . . . . . | | . . . . . Q . . . . . . . |
| . . . Q . . . . . . . . . | | . . . Q . . . . . . . . . |
| . . . . . Q . . . . . . . | | . Q . . . . . . . . . . . |
| . . . . . . . Q . . . . . | | . . . . . . . Q . . . . . |
| . . . . . . . . . Q . . . | | . . . . . . . . . . Q . . |
| . . . . . . . . . . . Q . | | . . . . . . . . Q . . . . |
+---------------------------+ +---------------------------+
(End)
		

Links

• M. R. Engelhardt, A group-based search for solutions of the n-queens problem, Discr. Math., 307 (2007), 2535-2551.
• Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 62-63.
• Kevin Pratt, Closed-Form Expressions for the n-Queens Problem and Related Problems, arXiv:1609.09585 [cs.DM], 2016.
• I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math. Monthly, 101 (1994), 629-639.

Crossrefs

See A007705, which is the main entry for this sequence.

Cf. A000170, A071607.

Formula

a(n) = A071607((n-1)/2) * n for odd n. - Eduard I. Vatutin, Nov 27 2023, corrected Apr 10 2024

Extensions

Term a(31) added from A007705 by Vaclav Kotesovec, Aug 25 2012