Schachbrett

Das Schachbrett ist traditionell ein Symbol für geistige Anstrengung. Die Schönheit mancher Meisterkombination erschließt sich gelegentlich nur nach Mühen - und häufig nur dem guten Spieler. Anders ist das mit den hier vorgestellten Themen, die so einfach, so offenkundig sind, daß sie kaum einer Überlegung bedürfen - oder doch?

Ein Schachbrett kann als Gitter aufgefaßt werden, auf dessen Kreuzungspunkte Spielfiguren mit bestimmten Eigenschaften regelgerecht plaziert werden. Im folgenden könnte die nicht unbegründete Gefahr bestehen, daß mathematische Formeln verwendet werden. Deshalb wird folgende Definition getroffen:

Definition für diese Seite

Und nun geht's los!

 Das 8-Damen-Problem

Das 8-Damen-Problem ist eine altbekannte Denksportaufgabe für Schachspieler.

8 Damen sind so auf einem Schachbrett aufzustellen, daß sie sich nicht gegenseitg bedrohen.

Eine der möglichen Lösungen ergibt sich mit einigen Überlegungen und etwas Ausprobieren:

In der Informatik wird diese Aufgabe häufig verwendet, um unterschiedliche Algorithmen zu erarbeiten, die das Plazieren der Damen auf dem Schachbrett durchführen.

 Das n-Damen-Problem

Das 8-Damen-Problem kann verallgemeinert werden:

n Damen sind so auf einem Schachbrett der Kantenlänge n aufzustellen, daß sie sich nicht gegenseitg bedrohen.

.

Für n=1 gibt es eine Lösung, die aber im Sinne der Aufgabenstellung nicht so recht befriedigt. Für n= 2 und n=3 gibt es keine Lösung. Die möglichen Lösungen ab n=4 sollen uns nun beschäftigen.

Um die folgenden Überlegungen etwas zu vereinfachen, ein paar Definitionen:

Beispiel: die gezeigte Lösung des 8-Damen-Problems kann durch die Menge B1 beschrieben werden:

B1 = {(0,5), (1,2), (2,0), (3,7), (4,4), (5,1), (6,3), (7,6)}

Unklugerweise habe ich die Menge nach den Spaltenindizes sortiert. Das provoziert sofort die Frage, ob nicht eine abgekürzte Schreibweise möglich ist. Sie ist möglich, wenn man sich vergegenwärtigt, daß folgende Bedingungen erfüllt sein müssen:

Auf dem Brett Formel für Damen i, j
in jeder Spalte steht genau eine Dame si ¹ sj
in jeder Zeile steht genau eine Dame zi ¹ zj
In den Diagonalen des Feldes, auf denen eine Dame steht, darf keine weitere Dame stehen ½si - sj½ ¹ ½zi - zj½

Bleiben wir dennoch zunächst bei den durch Paare beschriebenen Positionen. Sie sind sehr nützlich, wenn es darum geht, zu prüfen, ob die Anordnung zweier oder mehrerer Damen auf dem Brett den Ausschlußbedingungen genügt.

Aufgabe:

Für die Aufstellung der Damen wird schnell klar, daß ein "brute force"-Verfahren angewendet werden kann:

---

Ein Verfahren, daß eine ziemliche Komplexität hat. Welche?

Vereinfachen läßt sich die Sache erheblich, wenn die vorhin genannten formalen Bedingungen berücksichtigt werden. Dann nämlich wird klar, daß das brute force Verfahren alle Belegungen auf dem Brett prüft, darunter auch viele prinzipiell unzulässige.

Heute gelten Backtracking-Verfahren als die beste Methode, die Damen zulässig aufzustellen. Ihre Komplexität ist:

----

Sofort fragt sich der Autor dieser Seite, ob es nicht ein konstruktives Verfahren linearer Komplexität gibt, das das n-Damen-Problem löst. Dies würde bedeuten, eine Funktion queen_pos angeben zu können, die als Parameter die Kantenlänge n und die Spalte s bekommt, in der jeweils eine Dame zu plazieren ist. Die Laufzeit der Funktion soll unabhängig von n und s konstant sein. Protoyp der Funktion: 

int queen_pos (int n, int s);

Eine for-Schleife, die diese Funktion n-mal aufruft, ergäbe das gesuchte Resultat. Gesucht wird nur eine der möglichen Anordnungen, denn auch Backtracking-Verfahren halten an, sobald sie die erste gültige Lösung gefunden haben.

Es gibt einen Haken bei der Sache. Bis heute hat angeblich niemand eine Lösung gefunden - oder ist in den Lehrbüchern keine veröffentlicht? Da keine Lösung angegeben wird, liegen einige, sich widersprechende Vermutungen nahe:

  1. Backtracking stellt das beste Verfahren dar. In diesem Falle müßte ein Beweis gefunden werden, daß es kein besseres Verfahren gibt.
  2. Das konstruktive Verfahren ist prinzipiell nicht durchführbar - Beweis gesucht.
  3. Es gibt das konstruktive Verfahren, nur hat bislang niemand gründlich genug und zugleich richtig konstruiert.
  4. Es gibt das Verfahren, aber es wird nicht vorgestellt, weil es banal ist und man den Studierenden sonst nicht das Backtracking-Verfahren beibringen könnte.

Wer ein wenig in der unterhaltungsmathematischen Lieteratur kramt, wird einem Klassiker begegnen: W.W.Rouse Balls Mathematical Recreations. Und dort findet sich auch ein gut 100 Jahre alter Ansatz, um unsere Aufgabe zu knacken. Fangen wir an, ein paar Überlegungen und Ansätze aufzuschreiben.

Einfall Bemerkungen
Damen, die in einem Rösselsprung-Schema aufgestellt werden, bedrohen sich nicht. Man beachte, daß ein Rösselsprung-Schema nicht nur mit dem klassischen Springerzug 1+2 Felder sondern mit beliebigen ganzzahligen Werten s+z, s¹z angewendet werden kann, um die Bedingung zu erfüllen.  
n ist entweder gerade oder ungerade. Das hat möglicherweise Einfluß auf Symmetriebetrachtungen. Für n ungerade hat das Schachbrett ein Mittelfeld.
Wenn eine Lösung für n bekannt ist, könnte eine Lösung für n+1 konstruktiv gefunden werden. Es lohnt sich unter Umständen an die Lösung bestimmte Bedingungen zu stellen. Eine Art Induktionsverfahren könnte der Schlüssel zur Lösung des Problems sein. Doch Vorsicht! Wenn das Verfahren das Umstellen der Lösung für n erfordert, besteht die Gefahr, daß die Komplexität des Gesamtverfahrens wieder bei der des Backtracking endet.
Die Kantenlänge des Schachbrettes kann mod k, mit k > 1 klassifiziert werden. Gäbe es für jede der Klassen einen Lösungsalgorithmus, so könnte der Algorithmus für die Lösung der Gesamtaufgabe darauf zurückgreifen.
Man kann das Brett in Regionen unterteilen und für jede Region eine Lösung finden. Die Teillösungen werden anschließend zusammengesetzt. Die in der Algorithmik als "divide et impera" bekannte Vorgehensweise erfordert hier die Erfüllung von Bedingungen für die Ränder der jeweiligen Teilbereiche. Nicht in jedem Falle werden die Bedingungen so formulierbar sein, daß sich einer der Teilbereiche auf einfache Art lösen läßt
Es genügt, eine Hälfte/ ein Viertel des Brettes zu lösen und den Rest über Symmetriebetrachtungen Dieser Ansatz könnte den Aufwand drastisch reduzieren.
Es könnten Lösungen für spezielle Klassen von n existieren Naheliegend ist der Ansatz, Primzahlen oder Quadratzahlen besondere Aufmerksamkeit zu schenken, da sie Einschränkungen oder Erleichterungen beim Erarbeiten der Lösung bieten könnten.

Es ist nicht verboten, diese Denkansätze zu kombinieren, um zu einer brauchbaren Lösung zu gelangen. Beginnen wir mit dem Rösselsprung. Offenbar kann ein beliebig langer rechteckiger Streifen mit Damen gefüllt werden, die sich gegenseitig nicht bedrohen:

***Bild***

Nutzen wir zusätzlich das Verfahren, zwei solcher Streifen drehsymmetrisch aneinanderzufügen, so ergibt sich ein erster Erfolg:

***Bild***

Dieses Resultat kann offenbar nur für Schachbretter mit gerader Kantenlänge n verwendet werden - und auch nicht für jedes, wie das Beispiel der Kantenlänge 14 zeigt:

***Bild***

Was ist mit den ungeraden n?

yyy

 Der Weg des Springers

Zunächst die Aufgabenstellung:

Ein Springer soll auf dem Schachbrett regelkonform so gezogen werden, daß er jedes Feld genau einmal betritt.

Der Schwierigkeitsgrad der Aufgabe kann gesteigert werden, wenn gefordert wird, daß Ausgangs- und Endfeld identisch sind (dazu benötigt man offensichtlich einen Zug mehr als bei der Originalaufgabe). Ähnlich wie beim n-Damenproblen kann die Aufgabenstellung auf Spielfelder der Kantenlänge n erweitert werden.

Stand: 18.11..2002 /
 HPs Home      Mathematik/Home