Das n-Damenproblem

stevepb, https://pixabay.com/photo-1511866/

Das n-Damen-Problem ist ein interessantes Problem aus der Graphentheorie und ist auch noch recht einfach zu verstehen.

Problem
Wie viele Möglichkeiten gibt es n Damen auf einem Schachbrett zu platzieren, so dass sie sich gegenseitig nicht schlagen können?

Eine einzelne Lösung für ein 8×8-Schachbrett zu finden, ist nicht schwer, dagegen die Anzahl der Lösungen zu ermitteln ist schon eine größere Herausforderung. Die Zahl 234.907.967.154.122.528 gibt die Anzahl der Lösungen für das 27-Damen-Problem an. Dresdner Forscher von der TUD ist es gelungen diese Zahl nach einem Jahr Berechnung zu ermitteln. Ihr Algorithmus beruhte letztendlich auf Brute-Force und ein paar mathematischen Überlegungen zu auftretenden Symmetrien. Grund genug sich dem Thema mathematisch zu nähern.

In der folgenden Abbildung ist die Situation des 8-Damen-Problems dargestellt. Wenn wir eine Dame auf dem Schachbrett in der Mitte platzieren (blauer Knoten), dann bedroht sie alle rot gefärbten Felder (bzw. Knoten).

Die sieben restlichen Damen können jetzt noch der Reihe nach auf dem Schachbrett verteilt werden. Woher wissen wir aber, dass auf einem 8×8-Schachbrett 8 Damen platziert werden können? 1999 wurde von H. Steinhaus bewiesen, dass auf einem nxn-Schachbrett (maximal) n Damen platziert werden können, so dass sie sich nicht bedrohen [1].

Wie in der vorherigen Abbildung zu sehen, können wir das Problem mit Hilfe der Graphentheorie darstellen. Wie platzieren in unseren Feldern des Schachbrett jeweils einen Knoten und verbinden solche Felder miteinander, die durch einen Zug einer Dame erreicht werden können. Einen solchen Graphen eines nxn-Schachbretts nennen wir Damengraph \(\)D_n\(\). Nun können wir unser Problem etwas anders formulieren: Wie viele unabhängige Mengen* \(\)i_n\(\) mit n Knoten gibt es in dem Damengraph \(\)D_n\(\)?

Das Turmproblem

Eine allgemeine Antwort auf diese Frage gibt es bisher nicht. Deshalb schauen wir uns erst einmal ein paar Teilprobleme an. Zunächst können wir uns die Frage stellen:

Problem
Wie viele Möglichkeiten gibt es n Türme auf einem Schachbrett zu platzieren, so dass sie sich gegenseitig nicht schlagen können?

In der Graphentheorie sprechen wir jetzt also von einem Turmgraphen und suchen darin die Anzahl der unabhängigen Mengen mit n Knoten (also die Anzahl der maximalen unabhängigen Mengen).

Die Anzahl der Möglichkeiten die Türme zu platzieren ist n!. Dies lässt sich recht einfach beweisen. In der ersten Spalte haben wir n Möglichkeiten den ersten Turm zu platzieren. In der zweiten Spalte haben wir dann nur noch n-1 Möglichkeiten, in der Dritten n-2, usw. Da wir n Spalten haben ergibt sich durch Multiplikation der Möglichkeiten n(n-1)(n-2)…1 = n!. Das n-Turmproblem ist somit gelöst und liefert auch eine obere Schranke für das n-Damenproblem. Wir wissen also schon mal, dass \(\)i_n\leq{n!}\(\) ist. Diese Schranke ist aber sehr ungenau. Eine Vermutung besagt, dass

\[i_n=n!/c^n\]

für \(\)c \approx 2.54\(\) gilt.

Das Läuferproblem

Ein zweites Teilproblem ist das Läuferproblem. Hier fragen wir nach der Anzahl der Möglichkeiten Läufer auf einem Schachbrett zu platzieren, so dass sie sich gegenseitig nicht bedrohen. Gegenüber den letzten zwei Problemen ist es hier aber möglich mehr als n Läufer auf einem nxn-Schachbrett zu platzieren, nämlich 2n-2 [2]. Dazu platziert man in der ersten Spalte n Läufer. Sie bedrohen jetzt alle anderen Felder bis auf n-2 Felder in der letzten Spalte. Auf diese Felder stellt man nun die verbleibenden Läufer.

Die Anzahl der maximalen unabhängigen Mengen in diesem Graphen wurde bereits durch Madachy [2] bewiesen. Da wir uns aber auf dem Weg zu n-Damenproblem befinden, sind wir an der Anzahl der maximalen unabhängigen Mengen mit n Knoten interessiert. Oder auch an der Anzahl der unabhängig dominierenden* Mengen mit n Knoten. Die Herleitung einer Formel für dieses Problem ist sehr lang und technisch. Die Idee ist aber, dass man von der Mitte des Felder ausgeht und je nach der Parität von n und [math]\left\lfloor\frac{n}{2}\right\rfloor[/math] verschiedene Fälle untersucht. Das Resultat beinhaltet dann entsprechend diese Fallunterscheidung. Für n gerade erhalten wir (k=n/2):

\[ d_i=\begin{cases}(k!\,(k+2)/2)^2,\,k\,gerade\\ ((k-1)!\,(k+1)^2/2)^2,\,k\,ungerade.\end{cases} \]

Und für ungerade n (k=(n-1)/2):

\[ d_i=\begin{cases}(((k!)^2/12)\,(3k^3+16k^2+18k+8),\,k\,gerade\\((k-1)!\,(k+1)!/12)\,(3k^3+13k^2-k-3),\,k\,ungerade.\end{cases} \]

Den Beweis kann man in einem Artikel von Robert W. Robinson [3] nachlesen. Die Komplexität des Beweises und des Ergebnisses macht aber wenig Hoffnung auf eine schöne und direkte Lösung für das n-Damenproblem. Mit Hilfe der Formel kann man aber recht einfach die Anzahl der Stellungen für n=27 berechnen:

30.525.493.449.118.187.520.000

Auch diese Anzahlen liefern natürlich obere Schranken für das n-Damenproblem. Die Lücke wird aber immer größer, je größer man n wählt.

Ich würde auch an dieser Stelle gerne die Lösung für das n-Damenproblem vorstellen, aber bisher ist keine Lösung bekannt.

Anmerkungen:

dominierend: Einen Knotenteilmenge eines Graphen heißt dominierend, falls alle anderen Knoten des Graphen einen Nachbarn in der Menge haben.

unabhängig dominierend: Eine Knotenteilmenge eines Graphen heißt unabhängig dominierend, falls sie dominierend ist und alle Knoten der Teilmenge paarweise nicht benachbart sind.

Literatur:

[1] Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 29-30, 1999.
[2] Madachy, J. Madachy’s Mathematical Recreations. New York: Dover, pp. 36-46, 1979
[3] R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Ich akzeptiere

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.