Andere Seiten zum Damen-Problem, und Kommentare dazu

Wikipedia

Einen guten Artikel finden Sie bei Wikipedia, oder der englischen Version.

TU Dresden

Mit dem Weltrekord für das (normale) 26 × 26 Brett hat die TU Dresden eine Seite veröffentlicht. Sie beschreibt genauer, wie es gelang, den notwendigen Grad an Parallelität und Rechen-Leistung zu erreichen. Der Schlüssel dazu war, FPGAs (field programmable gate arrays, eigene Karten, die man in entsprechende Computer einstecken kann) zu verwenden und auf das Problem zu trimmen.

nQueens@home Projekt

Es gab auch ein BOINC Projekt, das die Möglichkeiten für größere Bretter zählen sollte. Offenbar war dies von Pech verfolgt. Das Projekt fand als erstes eine Anzahl für das 24 × 24 Brett; später stellte sich jedoch heraus, dass ein Überlauf-Fehler unbemerkt geblieben war. Die Differenz zur neuen und hoffentlich richtigen Zahl ist 781 684 047 872 = 0xb6 0000 0000.

Die Home-Page des Projektes war nQueens@home, aber diese Seite kann ich seit Monaten nicht mehr erreichen. Ich weiß nicht, warum sie offline ist, oder ob sie umgezogen ist. Die Teilergebnisse des Projektes sind auf jeden Fall interessant; ich gehe davon aus, dass sie für andere (insbesondere TU Dresden) eine Bestätigung beim Start des eigenen Projektes waren. Wenn jemand genaueres weiß, bin ich für Informationen dazu dankbar.

Die erste Lösung im Alfabet

Ein besonderer Aspekt ist die Frage: welche Lösung ist die kleinste, oder die erste im Alfabet? Martin und Colin Pearson sind dieser Frage nachgegangen, dazu gibt es die beiden Seiten CSP Queens - Counting Queen-placements (von Colin), und Queens On A Chessboard (von Martin).

Es ist eigentlich leicht, auch für große n eine Lösung für das Damen-Problem zu finden. Ein paar Artikel habe sich damit befasst. Dabei sollte man zunächst präzisieren: es gibt ja explizite Konstruktionen, mit denen man zu einer Lösung kommt, und das geht mit heutigen Computern sozusagen in Null Komma Nix. In den Artikeln geht es mehr darum, eine Lösung zu finden, die "in der Nähe" einer gegebenen Anfangs-Permutation liegt. "In der Nähe" heißt dabei, dass viele Positionen unverändert bleiben.

Will man aber eine strenge Ordnung haben, dann wird das Problem schwieriger. Es gibt sozusagen "fruchtbare" Gebiete im Raum aller Permutationen, in denen die Damen-Lösungen relativ dicht liegen, so dass man leicht viele Lösungen findet, und es gibt "karge" Gebiete. Und es erweist sich, dass der Anfangs- und der End-Bereich einer Suche extrem karg sind.

Der Standard-Algorithmus nimmt sich "gierig" zunächst viele lange Diagonale, und stranguliert sich damit gewissermaßen selbst.

Das geht so weit, dass man Hunderte Stunden braucht, um zur ersten Lösung zu kommen, während man sonst zehn oder mehr Lösungen pro Sekunde findet.

Da ist es natürlich eine Herausforderung, mit einem ausgefeilten Algorithmus dieses karge Gebiet schneller zu durchforsten, als es der "normale" Algorithmus tut. Ein paar Ideen dazu sind bei mir gerade in Arbeit.

Martin und Colin Pearson geben auch an, wieviele Versuche es brauchte, Damen einen Platz zuzuweisen, bis die kleinste Lösung gefunden ist. Das sind wunderbare Vergleichs-Daten. Die Grund-Idee ist, vor jeder neuen Platz-Zuweisung Aufwand zu spendieren, um dies andererseits durch eine viel geringere Zahl von Platz-Zuweisungen wieder einzusparen.

Heise Online und Heise Forum

Aus Anlass des Q26-Weltrekords gab es auch ein Meldung bei Heise und einige Diskussion im Heise-Forum.

• Zu einem großen Teil geht es dort um die Frage: ist es sinnvoll, sich mit dem Damen-Problem zu befassen? Wieviel Zeit, wieviel CPU-Zeit und wieviel elektrische Energie darf man dafür aufwenden?
• Ein Teil der Diskussion geht um Symmetrie. In der Tat wird Symmetrie beim "normalen" Damen-Problem bisher wenig genutzt; es ist offenbar zu wenig bekannt, wie man das macht. Ein Stück weit enthält die Seite der TU Dresden (siehe oben) Erklärungen zur Symmetrie.
• Am interessantesten für mich war, dass ein Teilnehmer im Forum ("Max-Spam") annimmt, man könne das Damen-Problem inzwischen ganz leicht lösen, mit vernachlässigbarer CPU-Zeit (< 10 s). Das soll mit der Methode gehen, die in Die Kunst des komplexen Zählens besprochen wird. Dabei handelt es sich um einen Artikel in der Tageszeitung "Frankfurter Allgemeine" von Professor Heinrich Hemme, über einen neuen Algorithmus, den Timme, van Bussel, Fliegner und Stolzenberg entwickelt haben. Es ist jedoch nicht wahr, dass sich damit das Damen-Problem lösen lässt. Der Algorithmus is sicher nützlich für einige Probleme der Grafen-Theorie; er lässt sich jedoch nicht direkt auf das Damen-Problem anwenden. Auch wenn die Probleme nahe verwandt sind - eine Lösung im bisherigen Sinne bringt der neue Algorithmus nicht. Es wäre sehr schade, wenn sich Leute, die sich mit dem Damen-Problem befassen, durch dieses Missversändnis entmutigen lassen.

Weitere Seiten

Weitere Seiten will ich hier noch ergänzen.