n queen topics
Home
Gruppen-Wirkungen
Such-Algorithmus
Symmetrie nutzen, normales Damen-Problem
Stammbäume
Besonderheiten
Halsbänder
Konflikte
Konflikt-Tabellen
Weltrekorde
Tabellen von Zähl-Ergebnissen
Bilder für n=8
Torus Bilder für n=13
Andere Seiten und Kommentare
Bibliografie
 
 
Other themes
Anzahl Primzahlen, die man als Summe von Faktoren erhält
Primzahl aus falscher binomischer Formel
Zahlen nach Primfaktor-Verteilung
 
 
 
Diese Seite in einer anderen Sprache
Englisch

Conflicts in the n-queens problem

First solution Q21
Die erste Damen-Lösung auf dem 21 x 21-Brett.

Das Damen-Problem hat sehr viele Lösungen, zumindest, wenn das Brett immer größer wird.

Daher scheint es einfach, die erste Lösung zu finden. Aber es ist keineswegs einfach, es ist ziemlich schwer.

Natürlich müssen wir zuerst definieren, was wir mit "die erste Lösung" meinen. Gemeint ist eine alfabetische Reihenfolge der Lösungen. Zeile für Zeile notieren wir, in welcher Spalte eine Damen auf dem Brett steht. Bis n = 26 können wir diese Nummer durch den entsprechenden Buchstaben des Alfabets ersetzen; so erhalten wir ein (verallgemeinertes) Wort aus n Buchstaben. Die Reihenfolge der Lösungen entspricht dann genau der Reihenfolge, in der die entsprechenden Worte in einem Lexikon stünden. Wir nennen dies die "alfabetische Reihenfolge".

Der Grund dafür ist, dass die Lösungen nicht gleichmäßig über den gesamten Bereich der möglichen Lösungen verteilt sind. Die folgenden Bilder zeigen durch die Farbe eines Feldes an, wie viele Lösungen auf diesem Feld eine Dame haben. Die Bilder sind also zu interpretieren wie eine Temperatur-Karte der Wettervorhersage: Blau bedeutet sehr kalt, nur wenige Lösungen, Grün nicht ganz so kalt, aber die Anzahl bleibt unter dem Medianwert; Gelb bedeutet warm, die Anzahl der Lösungen liegt über dem Medianwert, und Rot bedeutet einen heißen Bereich, sehr viele Lösungen. Die vier Farben ändern auch noch ihre Intensität, für Blau und Grün zeigt hohe Intensität weniger Lösungen und für Gelb und Rot bedeutet eine größere Intensität mehr Lösungen. Wenn es überhaupt keine Lösung mit einer Dame auf dem Feld gibt, dann bleibt es leer.

Distrib.N8.empty
Wetter-Karte, Anzahl Lösungen pro Feld, für ein leeres N8-Brett
Distrib.N8.0_0
Wetter-Karte, Anzahl Lösungen pro Feld, N8-Brett mit einer Dame auf 0/0
Distrib.N16.empty
Wetter-Karte, Anzahl Lösungen pro Feld, leeres N16-Brett
Distrib.N16.0_0
Wetter-Karte, Anzahl Lösungen pro Feld, N16-Brett mit einer Dame auf 0/0

Für N8 sind die Anzahlen in der untersten Reihe: 4 / 8 / 16 / 18, und in den nächsten Reihen 8 / 16 / 14 / 8, dann 16 / 14 / 4 / 12, und 18 / 8 / 12 / 8. Das Verhältnis von höchster Anzahl (in der Mitte) zu kleinster (am Eck) ist 4,5.

Für N16 sind die Anzahlen in der untersten Reihe: 436.228 / 569.531 / 736.363 / 892.999 / 1.050.762 / 1.160.280 / 1.249.262 / 1.290.831. Bei steigendem n sollte die Verteilung gleichmäßiger sein, aber das Verhältnis von höchste zu kleinster Anzahl ist immer noch 2,96.

Betrachtet man diese Bilder, so sieht man, dass die erste Dame in der Ecke nur wenige Lösungs-Möglichkeiten zulässt. Das ist ungünstig für die Suche nach der kleinsten Lösung. Auch wenn es nur wenige Lösungen gibt, muss man doch viele Felder prüfen, und die meisten führen zu keiner Lösung. Noch deutlicher sieht man das an den Bildern, bei denen auf 0/0 schon eine Dame steht. Beim 8 mal 8 Brett gibt es dann keine Lösung mit der zweiten Dame auf 2/1 oder 3/1. Damen auf 0/1 oder 1/1 sind von den Regeln nicht erlaubt; es ist keine Überraschung, dass diese Felder leer sind. Aber bei den anderen beiden gibt es keinen offensichtlichen Grund fürs Leer-Bleiben.

Das entsprechende Bild für N16 zeigt, dass Damen auf 2/1 oder 3/1 möglich sind; aber auch hier sind es nur wenige Möglichkeiten. Es sind 16.346 Möglichkeiten für 2/1, verglichen mit 44.128 für 8/1.

Wenn wir weitere Damen setzen, ergeben sich folgende Bilder:

Distrib.N16.2Q_min
Anzahl Lösungen pro Feld, N16 mit 2 Damen in Minimal-Position; total 16.364 Lösungen
Distrib.N16.3Q_min
Anzahl Lösungen pro Feld, N16 mit 3 Damen in Minimal-Position; total 819 Lösungen
Distrib.N16.3Q_rnd
Anzahl Lösungen pro Feld, N16 mit 3 Damen in Zufalls-Position; total 13.547 Lösungen

Eine ähnliche Zählung habe ich für das 24 mal 24 Brett gemacht, mit 7 vorab gesetzten Damen. Sind sie in Minimal-Position, dann gibt es 26 Lösungen, bei einer Zufalls-Position erhielt is 2.849.191 Lösungen. Das zeigt, wie dünn gesät die Lösungen im Minimal-Bereich sind.

Bekannte Minimal-Lösungen

Minimal-Lösungen sind bis zur Größe 55 gefunden. Sie können sie in einem großen gif-Bild betrachten, das sie alle in einer Schleife anzeigt.

Dr größte Teil der Suche wurde von Colin Pearson druchgeführt; er unterhält eine Web-Seite zu diesem Thema. Auch Wolfram Schubert und der Autor (M.Engelhardt) haben bei der Suche geholfen.

Erstauhnlich ist, dass der Aufwand für die Suche nicht direkt an die Größe der Seite gekoppelt ist; zum Beispiel braucht 48 mehr Aufwand als jede Größe zwischen 49 und 55. Das scheint mit der Teilbarkeit der Zahl zu tun zu haben, aber wir haben keine weitere Erklärung dafür. Wenn es stimmt, dann wird die Suche nach der kleinsten 60 mal 60 Lösung eine große Herausforderung.

Die gefräßige Folge (greedy sequence)

Stellen Sie sich ein endloses Schachbrett vor; das heißt, die Zeilen und Spalten (oder auch Reihen und Linien) starten bei 1, aber enden nicht. Die Frage nach der kleinsten Damen-Lösung kann man auch für dieses Brett stellen. Die Nummern der Spalten dieser Minimal-Lösung sind die "greedy sequence", was wohl mit "gefräßige Folge" zu übersetzen ist; sie ist unter A065188 in der Encyclopedia of integer sequences enthalten. Lassen sie mich die Spalte der Dame in Zeile k als g(k) bezeichnen. (g als Abkürzung für "greedy").

Der Algorithmus zum Finden der Werte ist ganz simpel: man fängt mit der ersten Dame auf 1/1 an. Dann macht man Zeile für Zeile weiter, und nimmt jedesmal das erste erlaubte Feld. Damit ist dessen Spalte "verbraucht", oder "aufgegessen"; das ist wohl der Grund für den ungewöhnlichen Namen der Folge.

Die gefäßige Folge hat eine interessante Eigenschaft: sie ist eine Permutation der natürlichen Zahlen. Keine Spalte kommt mehrfach vor (die Abbildung ist injektiv), und jede Spalte kommt früher oder später einmal vor (die Abbildung ist surjektiv); das letztere erscheint einleuchtend, aber ist nicht so leicht zu beweisen.

Weil die Folge eine Permutation ist, kann man fragen, wie viele Spalten lückenlos besetzt sind, wenn die k-te Zeile ihre Dame bekommen hat. Diese Zahl bezeichne ich mit f(k). (f als Abkürzung für "filled"). Es ist klar, dass f eine monotone Abbildung ist. Meine Berechnungen zeigen, dass der Quotient k / f(k) gegen die Fibonacci-Zahl konvergiert, also gegen (sqrt(5) - 1) / 2 = 1.618034. Bisher habe ich noch keinen Beweis dafür.

Hier gebe ich Ihnen eine kleine Tabelle von Werten, die mich zur dieser Hypothese geführt haben (k / f(k) konvergiert gegen die Fibonacci Zahl); die letzte Spalte (Delta) enthält die Differenz zwischen aktuellem Wert und Grenzwert.

kg(k)f(k)k / f(k)Delta
5032321,56250,055534
100162621,639344-0,02131
2003231241,6129030,005131
5003103111,6077170,010317
10006186191,6155090,002525
2000323612361,618123-0,000089
5000808930921,6170760,000958
99991617961791,618223-0,000189

Andere Start-Werte für die gefräßige Folge

Man kann eine gefräßige Folge auch mit anderen Start-Werten betrachten; das heißt, der Algorithmus ist der gleiche, die Folge ist immer noch "gefräßig", aber die ersten Werte sind anders.

Auch in diesen Fällen ist der Grenzwert derselbe. Das brachte mich zur Frage ob vielleicht auch die Folge selbst irgendwann gleich wird. Formal aufgeschrieben: ist h(k) die gefräßige Folge mit anderen Start-Werten, gibt es dann eine natürliche Zahl m so dass g(k) = h(k) für alle k > m. Ich war ein wenig enttäuscht, dass es offenbar nicht so ist, außer bei trivialen Konstellationen. Ein Beispiel für eine solche triviale Konstellation sind die Start-Werte h(1) = 2, h(2) = 4, h(3) = 1, h(4) = 3, h(5) = 5. Der Footprint dieser ersten 5 Damen auf die Spalten und auf die Diagonalen beider Richtungen ist in diesem Fall exakt derselbe; daher gibt es danach keine Abweichungen mehr.

In einigen Fällen habe ich lange Bereich von k gefunden wo g(k) und h(k) übereinstimmen; aber dann gabe es doch wieder eine Abweichung.

Erstellt von Matthias Engelhardt
Mail an Matthias Engelhardt
 
last change: 2015-08-15
Address of page: http://nqueens.de/sub/FirstAlfa.de.html