Das n-Damen Problem

Definition: Stelle auf einem Schachbrett 8 Damen (queens) so auf, dass keine eine andere schlagen kann.

Die 92 (11*8+4) Lösungen dieses Problems zu finden ist nicht ganz leicht, wird aber einfach, wenn man einen Rechner zur Verfügung hat und etwas programmieren kann. In einer Tabelle am Schluss kann man alle Lösungen finden, wobei es nur 12 grundverschiedene gibt, die anderen kann man durch Drehung und Spiegelung erzeugen. Aus diesem Grunde sind auch nur die ersten 46, die erste Hälfte der Lösungen, in der Tabelle konkret angegeben, die zweite Hälfte ist aber leicht abzuleiten.

Die Frage, die mich eigentlich fasziniert hat, war:

Gibt es auch Lösungen für n ungleich 8 und wie verhalten die sich untereinander.

Natürlich haben mich auch Anwendungen dieser speziellen Anordnungen interessiert. So denke ich, dass z.B. zwei Bleche mit den Punkten des Damenproblems zusammengeschweisst, bei wenigen Schweisspunkten grosse Festigkeit versprechen. Oder dass Mischer mit der Anordnung der Mischschaufeln nach dem Damenproblem maximale Durchmischung versprechen.

Interessant finde ich Ihre Idee, nach praktischen Anwendungen des n-Damen-Problems zu suchen. Die von Ihnen vorgeschlagenen Anwendungen sind m. E. jedoch nicht realisierbar, denn die materielle Welt unterscheidet sich bekanntlich in einigen Punkten von der heilen Welt des Schachspiels.

Wenn Sie in einem realen Objekt auf einen bestimmten Punkt Einfluß nehmen - sei es nun ein Schweißpunkt oder die Stelle an der ein Rührer plaziert ist - dann nimmt die Auswirkung auf die Umgebung mit zunehmendem Abstand drastisch ab (je nach physikalischem Zusammenhang in mehrfacher Potenz oder exponentiell). In der Umgebung einer Dame nimmt der Anteil der Felder, die überstrichen werden, lediglich mit dem Quadrat des Abstandes ab. Eine (Schach)dame hat eine unbegrenzte Reichweite - aus 10000 Feldern Entfernung erreicht sie das Ziel genauso wie mit nur einem Feld Abstand.

Wenn Sie sich manche Lösungen mit n=20 anschauen, werden Sie feststellen, daß Sie ca. 30% der Quadratfläche ausgehend von der oberen Ecke abknicken können, weil dort kein einziger "Schweißpunkt" ist.

Trotzdem glaube auch ich an Anwendungen des n-Damen-Problems. So wie große Primzahlen für Verschlüsselungsalgorithmen verwendet werden, kann man vielleicht Lösungen des n-Damen- Problems für Vernetzungen in Datenbanksystemen verwenden.

Auch an die Ästhetik sollte man denken. Wenn ich mir mal ein Haus baue, dann werde ich in einem Raum bei den Bodenfliesen das Problem für n=20-30 verwirklichen. Wer hat schon so etwas? Jedesmal, wenn ich ein Fliesenmuster, mit vielen hellen und ein paar dunklen Fliesen sehe, empfinde ich es als störend, wenn zwei Fliesen sich auf einer Diagonalen (oder gar in einer Reihe) in die Quere kommen.

Übrigens ist der Buchegger-Faktor nicht konstant, wie Sie vermuten. Die Anzahl der Lösungen a(n) gilt für große Werte von n näherungsweise: a(n) = n!/c^n, mit c = 2.54. Also wird b mit zunehmendem n immer größer.

In meinen Unterlagen fand ich 4 Lösungen für n = 26, die ich vor vielen Jahren mit dem Atari ST in 20h berechnet habe:

acebdikmouwytvxzjgplhfrnsq   (ist am Ende grafisch dargestellt)

acebdikmouwytvxzjhplqgrfsn

acebdikmowtxuyvzjgplhfrnsq

acebdikmowtxuyvzjhplqgrfsn

Natürlich sind nicht alle Lösungen ästhetisch wertvoll. Ich möchte Ihnen noch einen Link empfehlen:

http://www.research.att.com/~njas/sequences/Seis.html