---

Das 8 Damen Problem

Das 8-Damen-Problem ist eines der bekanntesten und klassischsten Rätsel in der Mathematik und Informatik.

Übersichtliche Zusammenfassung der Regeln, Lösungen und Hintergründe:

Was ist das Ziel?

Die Aufgabe besteht darin, 8 Damen auf einem herkömmlichen Schachbrett ($8 \times 8$ Felder) so zu platzieren, dass keine zwei Damen sich gegenseitig schlagen können.

Da die Dame die stärkste Figur im Schach ist, bedeutet das:

1. Keine zwei Damen dürfen in derselben Reihe stehen.
2. Keine zwei Damen dürfen in derselben Spalte stehen.
3. Keine zwei Damen dürfen in derselben Diagonale stehen.

Die Lösungen

Obwohl es Milliarden von Möglichkeiten gibt, 8 Figuren auf 64 Feldern zu verteilen, gibt es für dieses spezifische Problem nur eine begrenzte Anzahl an Lösungen:

• Gesamtlösungen: Es gibt genau 92 verschiedene Anordnungen, die diese Regeln erfüllen.
• Fundamentallösungen: Wenn man Drehungen und Spiegelungen des Brettes ignoriert (da diese symmetrisch sind), bleiben nur 12 absolut einzigartige Grundlösungen übrig.

Ein visuelles Beispiel für eine Lösung

Hier ist eine der 92 möglichen Lösungen. Die Q stehen für die Damen (Queens) und die . für leere Felder:

. . . Q . . . .
. Q . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . Q .
. . Q . . . . .
Q . . . . . . .

Informatik & Algorithmen (Backtracking)

In der Informatik wird das 8-Damen-Problem oft verwendet, um eine Technik namens Backtracking (Rücksetzverfahren) zu lehren.

Wie funktioniert das? Stell dir vor, du gehst das Brett Reihe für Reihe durch:

1. Setzen: Du platzierst eine Dame in der ersten Reihe auf das erste Feld.
2. Weitergehen: Du gehst zur zweiten Reihe und suchst ein sicheres Feld.
3. Sackgasse: Wenn du in einer Reihe ankommst, wo kein Feld sicher ist (weil alle von den Damen darüber bedroht werden), hast du einen Fehler gemacht.
4. Backtracking: Du gehst einen Schritt zurück zur vorherigen Reihe, verschiebst die dortige Dame auf das nächste mögliche Feld und versuchst es erneut.

Dieser “Versuch-und-Irrtum”-Ansatz ist für Computer sehr effizient, um solche Probleme zu lösen.

Interessante Fakten

• Ursprung: Das Problem wurde erstmals 1848 vom Schachkomponisten Max Bezzel formuliert.
• Carl Friedrich Gauß: Der berühmte Mathematiker beschäftigte sich ebenfalls damit, fand aber zunächst nur 72 der 92 Lösungen.
• Das n-Damen-Problem: Das Problem lässt sich verallgemeinern. Man kann fragen: Wie platziere ich $n$ Damen auf einem $n \times n$ Brett?
  • Für $n=1$ gibt es 1 Lösung.
  • Für $n=2$ und $n=3$ gibt es keine Lösung.
  • Ab $n=4$ gibt es wieder Lösungen.

---