How many different ways (not counting rotations and reflections of the board as different) can K queens be...

competition/games/chess/queen.placements New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

How many different ways (not counting rotations and reflections of the
board as different) can K queens be placed on an NxN chessboard?

[ Editor: problem statement reconstructed from the postings, which ask
for the number of "different dispositions"; the formula below counts
placements up to the eight symmetries of the board. ]

Show solution

The answer is in "Polya's Theorem".
The wanted number is 1/8th of the coefficient of

a^K * b^(N^2-K) in these polynomials:

if N is even

p(a,b,N) := (a+b)^(N^2) + 2*(a+b)^N*(a^2+b^2)^((N^2-N)/2)
            + 3*(a^2+b^2)^(N^2/2) + 2*(a^4+b^4)^(N^2/4)

if N is odd

p(a,b,N) := (a+b)^(N^2) + 2*(a+b)*(a^4+b^4)^((N^2-1)/4)
            + (a+b)*(a^2+b^2)^((N^2-1)/2) + 4*(a+b)^N*(a^2+b^2)^((N^2-N)/2)

Note:
the total number of dispositions is equal to: Binomial coefficient(N^2, K)
and the number of different dispositions is near 1/8th.

Samples (K = N):
for N = 1           different dispositions = 1
for N = 2           different dispositions = 2
for N = 3           different dispositions = 16
for N = 4           different dispositions = 252
for N = 5           different dispositions = 6814
for N = 6           different dispositions = 244344
for N = 7           different dispositions = 10746377
for N = 8           different dispositions = 553319048
for N = 9           different dispositions = 32611596056
for N = 10          different dispositions = 2163792255680
...
for N = 14          different dispositions = 110066314584030859544
for N = 15          different dispositions = 11375695977099383509351
...

-- Timothy Chow and Mario Velucchi <velucchi@CLI.DI.Unipi.IT>

[ Editor: an earlier version of this message gave 5532069048 for N = 8;
the corrected value 553319048 is used above.  It checks: with K = N = 8
the four terms give C(64,8) = 4426165368, 2*139448, 3*C(32,4) = 107880
and 2*C(16,2) = 240, whose sum 4426552384 divided by 8 is 553319048. ]