Aspekte des Damen-Problems
Home
Gruppen-Wirkungen
Such-Algorithmus
Symmetrie nutzen, normales Damen-Problem
Stammbäume
Besonderheiten
Halsbänder
Konflikte
Konflikt-Tabellen
Minimal-Lösung und gierige Folge
Tabellen von Zähl-Ergebnissen
Bilder für n=8
Torus Bilder für n=13
Andere Seiten und Kommentare
Weitere Quellen
 
 
Andere Themen
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

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.

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".
Seiten-Anfang
Erstellt von Matthias Engelhardt
Mail an Matthias Engelhardt
 
last change: 2016-05-22
Address of page: http://nqueens.de/sub/WorldRecord.de.html