Skip to content.

TUD TU Dresden

Queens@TUD

DE EN 

TU Dresden » Faculty of Computer Science » Institute for Computer Engineering » Chair for VLSI – EDA » Queens
Queens@TUD-Logo

Facts

Known Solution Counts

For reference, the column headings of the individual sequences are linked with their corresponding entries in the On-Line Encyclopedia of Integer Sequences.

Problem
Size
N
Overall
Solutions

S
Incl. 180°
Symmetric

W
Incl. 90°
Symmetric

V
Fundamental
Solutions

U
11111
2000
3000
42221
510222
6441
74086
8924012
935216046
107241292
11268048341
12142008081787
137371213689233
1436559642045752
1522791841240285053
16147725123000641846955
1795815104815212811977939
186660906241810483263591
19496805784844184621012754
20390291888841446204804878666808
2131466622271237566470439333324973
2226910087016441250692336376244042
232423393768444035812403029242658210
2422751417197373611675080332828439272956934
252207893435808352341325923264275986683743434
26223176996163640441157182682789712466510289
27?320403024?
Properties
1. For all N > 1: 8U = S + W + 2V. (Proof)
2. For all N ≡ 2,3 mod 4: V = 0. (Proof)
Note
Due to the far tighter constraints for self-symmetric solutions, their number can be determined easily for somewhat greater N than the number of all solutions.

Symmetry Insights

Possible Symmetries

The properties given above can be derived directly from the analysis of the possible solution symmetries. It turns out that the interesting solutions are those that display some kind of self-symmetry. While all other solutions have eight distinguishable appearances, which may all be transformed into one another by reflecting or rotating the hosting board, some of these appearances collapse into a single instance if the backing fundamental solution has self-symmetric properties.

At first, observe that for all N > 1, no solution can ever be symmetric to itself with respect to reflection: All four possible reflection axis are attacking paths so that no more than a single queen can be placed directly upon it. Every queen not placed upon it would, however, result in a reflected image attacking the original so that both cannot be part of the same solution. Consequently, only solutions containing a only single queen can be self-symmetric, which are, in turn, are only complete for N = 1

Rotational symmetries, on the other hand, are very well possible and may be distinguished into two subcases:

Point Symmetry
about the board center, which is equivalent to a self-symmetry with respect to a rotation by 180°.
Rotational Symmetry
in the narrow sense for describing the self-symmetry with respect to a rotation by 90°. This case implies point symmetry as the appearance of the solution is not altered even by the second application of the 90°-rotation and is also equivalent to self-symmetry with respect to a 270°-rotation.

Point symmetric solutions only have four instead of eight distinct appearances as the original pairs of solutions, which equivalent with repect to a 180°-rotation, become indistinguishable. This can be verified in the figure above where one image of the top row cross-merges into another of the bottom row when point symmetry is assumed.

Rotational symmetric solutions even only have two distinct appearances, which capture the two reflective images, which cannot be equivalent for N > 1 as shown above. In the figure, these two classes are represented by the lightly and strongly shaded images. Assuming rotational symmetry, all members of either class become equivalent.

Property #1

Define the four counts of above table:

S
counts all the appearances of any solution.
W
counts all the appearances of point-symmetric solutions.
V
counts all the appearances of rotationally-symmetric solutions.
U
counts only the unique classes of fundamental solutions, which comprise all the appearances, which are equivalent through reflection or rotation.

The number of fundamental solutions U can then be partitioned into three groups:

x The number of rotationally-symmetric solutions, each contributing two appearances to all of the counts V, W and S.
y The number of point-symmetric but not rotationally-symmetric solutions, each contributing four appearances to the counts W and S.
z The number of all other solutions, each contributing the full eight appearances to the count S.

Hence, we obtain:

V = 2x
W = 2x + 4y
S = 2x + 4y +8z
U =  x +  y + z

which can be transformed into the first property stated above:

 S = 8U - W - 2V
8U =  S + W + 2V

Property #2

Finally, consider boards with N = 4k + r with r∈{2,3}. Its quadrants (excluding any center row or column) have sides of length:

D=⌊N/2⌋=2k+1

On a completely filled board, the first D columns must also host D queens. If the board was self-symmetric, none of these queens could be found in a potential center row as it would be in conflict with its own image after a 180°-rotation (or two 90°-rotations). Thus, they must be distributed among the top and bottom quadrants. Since D is odd, an even distribution and, hence, a rotational symmetry (by 90°) is impossible.

Sponsors
Signalion
Contact

Prof. Rainer G. Spallek
rainer.spallek@tu-dresden.de

Thomas B. Preußer
thomas.preusser@tu-dresden.de

Bernd Nägel
bernd.naegel@mailbox.tu-dresden.de

Telefax
+49 (0)351 463 38324
Street Address
Nöthnitzer Straße 46, Room 1095
01187 Dresden
Mail Address
Chair for VLSI – EDA
Fakultät Informatik
Technische Universität Dresden
D-01062 Dresden