|
Aspekte des Damen-Problems
Andere Themen
Diese Seite in einer anderen Sprache
|
Weltrekorde beim Damen-Problem
Weltrekord und Weltmeisterschaft beim Damen-Problem
Die Anzahl der Lösungen für immer größere Bretter zu bestimmen ist eine große Herausforderung.
Das gilt besonders für das "normale" Damen-Problem, in geringerem Maße auch für das Torus-Problem.
Die "normalen" Lösungen sind deutlich leichter zu finden, aber es gibt auch viel mehr von ihnen.
Beim Torus-Problem kann man hingegen die Symmetrien viel besser nutzen.
Es ist natürlich eine Frage, ob man eine neue Zahl für ein noch größeres Brett als Weltrekord
bezeichnen soll. Das tun wir hier, jedoch ohne dies Bier-ernst zu nehmen. Praktisch stellt man eine neue Zahl,
die man gefunden hat, in die On-Line Encyclopedia of Integer Sequences.
Damit ist dann der Rekord dokumentiert. Eventuell kommen dann Nachfragen
nach Teil-Ergebnissen, so dass die neue Zahl auch bestätigt werden kann.
Neben den reinen Zählungen gibt es auch eine Weltmeisterschaft; bei dieser geht es darum, welches Team,
ausgerüstet mit Programm und meist speziellen Computern, ein schon bekanntes Teil einer Zählung
am schnellsten durchführen kann. Die letzte mir bekannte Weltmeisterschaft
fand 2007 in Peking statt.
In der folgenden Tabelle fasse ich zusammen, was ich über die Weltrekorde weiß. Dabei kommt ein paarmal
INRIA vor; das ist die Abkürzung für "Institut National de Recherche en Informatique et en Automatique",
Frankreichs nationales Institut für Informatik und Automatisierung.
Das nomale Damen-Problem
| bis n=11 |
Die Zahlen wurden in mühsamer Handarbeit bis 1890 ermittelt |
| n=12 und n=13 |
A. Kopfermann aus Berlin ermittelt die Zahlen; leider schleicht sich ein Fehler ein.
1971 findet Mark B. Wells am Los Alamos Scientific Laboratory (USA) die richtigen Zahlen mit einem Computer. |
| n=14 bis n=20 |
Mit Computern findet man zwischen 1972 und 1997 die Zahlen; wer dies im Einzelnen war, weiß ich leider nicht.
|
| n=21 bis n=23 |
Sylvain Pion und Joel-Yann Fourre von INRIA, 1998. Sie verwenden 300 Prozessoren,
die zwei Monate lang suchen und zählen.
|
| n=24 |
Ein Web-Projekt, NQueens@home, auf der BOINC Plattform berechnet die Zahl;
leider kommte es dabei zu unbemerkten Überläufen, die Zahl ist falsch (zu klein). Am 1.September 2004
hat Kenji KISE aus Japan die richtige Zahl für Q24 gefunden.
|
| n=25 |
Denis Caromel (Universität Nizza und bei INRIA) findet im Jahr 2005 die Zahl Q25.
Dazu verwendet er 260 normale PCs, die etwa ein Dreivierteljahr laufen.
|
| n=26 |
Am 11.Juli 2009 geben Thomas Preußer, Bernd Nägel, Rainer Spallek von der TU Dresden
die Zahl Q26 bekannt. Um sie zu finden, verwenden sie FPGAs (= field programmable gate
array). Nach eine Veröffentlichung vom März 2009 sind es 11 Computer mit 377 FPGAs.
Kurz darauf, den 30.August 2009, bestätigt das russische Projekt MC#, die Zahl. Das Projekt hat dazu
zwei Super-Computer, die Nummern 54 und 82 aus der Liste der Top500-Computer vom Juni 2009 verwendet.
Sie haben dafür vom 19.November 2008 bis zum 30.August 2009 gebraucht (ich weiß nicht, ob es nur
um die sonst ungenutzte Zeit ging, oder ob die Zeit komplett verwendet wurde).
|
| n=27 |
Thomas Preußer von der TU Dresden mit seinem Team hat es am 19.September 2016 wieder geschafft:
Q27 = 234.907.967.154.122.528.
Wieder waren es FPGAs, die sich seit 2009 deutlich verbessert haben.
Ein weitere Punkt: die Symmetrien wurden erstmals besser genutzt (siehe auch Symmetrien nutzen beim normalen Damen-Problem).
Dazu hat das Projekt in der Vorbelegung und Aufteilung den kompletten Rand verwendet, und nicht nur die ersten Zeilen oder Spalten.
Konkret einen zwei Felder breiten Rand, statt der ersten sechs Spalten bei n=26.
Nachzulesen ist dies auch unter Neuer Weltrekord für Queens@TUD-Team, einer Seite der TU Dresden.
Weitere Informationen dazu.
|
Das Torus-Damen-Problem
In der Torus-Variante gibt es nur dann Lösungen, wenn n nicht durch 2 und auch nicht durch 3 teilbar ist.
Bis n=11 gibt es nur regelmäßige Lösungen, bei denen die Dame in der nächsten Reihe immer um die gleiche Anzahl Spalten
verschoben wird. Erst mit n=13 wird es interessant.
| n=13, n=17, n=19 |
Mir ist nicht bekannt, wer diese Zahlen zuerst ermittelt hat.
Für Hinweise wäre ich dankbar.
|
| n=23 |
Die Zahlen wurde zuerst in einem Projekt um die Programmiersprache LeLisp ermittelt,
und zwar mit 20 SUN Workstations
bei INRIA. Dazu brauchte es 267 Tage CPU-Zeit. Wann es genau war, weiß ich nicht, es muss jedoch vor 1994 gewesen sein.
|
| n=25 |
17.Dezember 1999, durch den Autor dieser Seiten, Matthias Engelhardt; die Zählung brauchte
etwa 4 Wochen CPU-Zeit auf einem 75 MHz Intel-Rechner. Algorithmisch war vor allem die Eingrenzung der Wertebereiche wichtig.
|
| n=29 |
11.Januar 2001, ebenfalls durch den Autor dieser Seiten. Die Suche brauchte
etwa 200 Tage CPU-Zeit auf einem 300 MHz Intel-Rechner. Beim Zusammenfassen der Lösungen war es ein 800 MHz Rechner, der etwa 2 Tage benötigte.
Der Such-Algorithmus ist hier beschrieben; er verwendet die Gruppen-Wirkung "Torus-Kongruenz".
|
| n=31 |
1.Mai 2005, ebenfalls durch den Autor dieser Seiten. Die Suche brauchte
wieder etwa 200 Tage, in denen fünf PCs mit 120 MHz, 300 MHz, 800 MHz, 1,6 GHz und 1,9 GHz verwendet wurden.
Dadurch ist die CPU-Zeit nur schwer abzuschätzen.
Der Such-Algorithmus ist in dieser Seite am Ende beschrieben;
er verwendet die Gruppen-Wirkung "Ähnlichkeit auf dem Torus".
|
| unterwegs: n=35 |
Seit über einem Jahr ist der Autor dabei, die Suche für diese Größe vorzubereiten und durchzuführen.
Das ist in einer eigenen Seite beschrieben.
Die Suche verwendet die Gruppen-Wirkung einer nochmals größeren Gruppe und die Methodik des "Easy counting lemma".
Trotzdem braucht die Suche viel Rechen-Leistung. Dabei unterstützt die Firma Lino GmbH aus Mainz:
sie stellt einen Server in sonst unbenutzten Zeiten für die Suche zur Verfügung.
|
|