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

Fakten

Bekannte Lösungen

Zur Referenzierung sind die Überschriften der Spalten der Reihenfolge nach den entsprechenden Einträgen in der On-Line Encyclopedia of Integer Sequences sortiert.

Problem
Größe
N
Alle
Lösungen

S
Incl. 180°
symmetrisch

W
Incl. 90°
symmetrisch

V
Eindeutige
Lösungen

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?
Eigenschaften
1. Für alle N > 1: 8U = S + W + 2V. (Beweis)
2. Für alle N ≡ 2,3 mod 4: V = 0. (Beweis)
Anmerkung
Wegen den viel starker einzugrenzenden Bedingungen für selbstsymmetrische Lösungen, sind größere N in der Berechnung gegenüber der Suche von allen Lösungen möglich.

Symmetrieüberblick

Possible Symmetries

Durch die eben beschriebenen Symmetrieeigenschaften, können aus der Symmetrieanalyse möglichen Lösungen abgeleitet werden. Dabei Spielen vor alle die Lösungen eine besondere Rolle, welche in irgendeiner Weise selbstsymmetrisch sind. Während alle nicht-selbstsymmetrischen Lösungen, durch Drehung und Spiegelung des Brettes, in acht unterschiedliche Formen übergehen können, fallen die Formen bei selbstsymmetrischen Lösungen in eine Untermenge, durch den Wegfall von identischen Abbildungen.

Als erstes kann festgestellt werden, dass für alle N > 1 in Anbetracht der Reflexion, keine Lösung zu sich selbst symmetrisch seien kann: Alle vier möglichen Reflektionsachsen sind schließlich bedrohte Felderreihen des Ausgangsproblems, so dass nicht mehr als eine Dame darauf platziert werden kann. Jede Dame, die also von dem Ursprung aus reflektiert wäre, würde folglich das Original angreifen und könnte damit nicht Teil der gleichen Lösung sein. Die Konsequenz daraus ist, dass nur Lösungen, welche lediglich eine Dame beinhalten selbstsymmetrisch sein können. Dies gilt für N = 1.

Bei Rotation sind Selbstsymmetrien jedoch sehr gut möglich, dabei sind 2 Fälle zu betrachten:

Punktsymmetrie
Über die Brettmitte, die mit einer Selbstsymmetrie in Bezug auf eine 180° Umdrehung gleichwertig ist.
Rotationssymmetrie
Bei einer Selbstsymmetrie in Bezug auf einer 90°. Umdrehung. Dieser Fall schließt sowohl die Punktsymmetrie, über eine zweite 90°-Rotation, als auch die Selbstsymmetrie in Bezug auf die 270°-Rotation ein.

Punktsymmetrische Lösungen haben lediglich vier von acht möglichen Abbildungsvarianten, genauso verhält es sich dementsprechend bei 180°-Rotationsymmetrien. Dies kann in der oberen grafischen Abbildung überprüft werden. Wie zu sehen, kann ein Bild der oberen Zeile unter Annahme der Punktsymmetrie in das über Kreuz liegende Bild der unteren Zeile überführt werden.

Lösungen mit Rotationssymmetrien haben dagegen sogar nur zwei eindeutige Abbildungen, welche unter der Bedingung von N > 1 nicht equivalent sein können. Im oberen Bild werde die beiden Klassen durch den untermalten helleren bzw. dunkleren Grauton repräsentiert. Hierbei sind alle vier Teilvarianten einer Klasse equivalent.

Punkt #1

Definition der vier Zähler (siehe Tabelle oben):

S
zählt jede gefundene Lösung.
W
zählt all die jenigen die punktsymmetrisch sind.
V
zählt alle Lösungen die selbstsymmetrisch sind (inkl. Rotationssymmetrien).
U
zählt nur die eindeutigen Lösungen, die eine Klasse repräsentieren welche sowohl die Punkt- als auch die Rotationssymmetrien einer Lösung zusammenfasst.

Die Anzahl der eindeutigen Lösungen U kann dabei in drei Gruppen unterteilt werden:

x Die Anzahl der rotationssymmetrischen Lösungen, welche in allen Zählern (V,W und S) zwei mal gezählt wurden.
y Die Anzahl der punktsymmetrischen Lösungen exklusive den Rotationssymmetrien, jede repräsentiert dabei vier gezählte Varianten aus W und S.
z Die Anzahl aller übrig geblieben Lösungen, jede spiegelt dabei alle 8 Varianten die in S gezählt wurden wieder.

Daher erhalten wir:

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

Was wiederum in S bzw. U umgewandelt werden kann:

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

Punkt #2

Schlußendlich betrachten wir die Felder welche die Größe N = 4k + r besitzen, mit der Nebenbediengung, dass r∈{2,3} ist. Die Quandranten dieser Felder (Mittelspalten und -Zeilen ausgenommen) haben eine Seitenlänge von:

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

Auf einem vollständig gefüllten Brett müssen natürlich auch auf den ersten D Spalten, D Damen platziert sein. Sollte das Brett selbstsymmetrisch sein, so befindet sich keine der Damen in einer möglichen Mittelzeile. Das würde schließlich zu einem Konflikt mit der Abbildung einer 180°-Rotation (bzw. zwei 90°-Rotation (bzw. zwei 90°-Rotationen) führen. Daher müssen die Damen entweder im oberen bzw. unteren Quadranten platziert sein. Da D ungerade ist, ist eine gleichmäßige Verteilung und folglich eine Rotationssymmetrie (durch 90°) unmöglich.

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