Startseite▸Algorithmen & KI▸N-Damen-Problem

♛ N-Damen-Problem

Beobachte, wie der Backtracking-Algorithmus des N-Damen-Problems das klassische Schachrätsel Schritt für Schritt löst. Steuere die Brettgröße (4–12) und Geschwindigkeit und erkunde alle Lösungen.

Algorithmen & KI3DEinfach60 FPS

Über das N-Damen-Problem

Das N-Damen-Problem fragt, wie man N Schachdamen auf einem N×N-Brett so platziert, dass keine zwei Damen eine Zeile, Spalte oder Diagonale teilen. Es wurde erstmals 1848 vom Schachkomponisten Max Bezzel für das 8×8-Schachbrett gestellt und hat für N=8 genau 92 unterschiedliche Lösungen. Das Problem ist ein klassisches Constraint-Satisfaction-Benchmark: Backtracking mit Constraint-Propagierung (Forward-Checking) beschneidet den Suchbaum drastisch, indem bei jeder platzierten Dame Spalten und Diagonalen ausgeschlossen werden, wodurch der naive N^N-Suchraum auf eine handhabbare Größe reduziert wird.

Diese Visualisierung lässt dich die Brettgröße von 4 bis 12 einstellen und dann schrittweise oder automatisch durch den Backtracking-Algorithmus gehen. Konfliktfelder werden bei der Platzierung einer Dame rot hervorgehoben; Backtracking-Schritte werden orange angezeigt und gültige Platzierungen grün. Ein Zähler verfolgt, wie viele Lösungen gefunden wurden und wie viele Knoten des Suchbaums besucht wurden.

Häufig gestellte Fragen

Wie viele Lösungen gibt es für das N-Damen-Problem auf einem 8×8-Brett?

Es gibt genau 92 unterschiedliche Lösungen für N=8. Berücksichtigt man nur grundlegend unterschiedliche Anordnungen (ohne Drehungen und Spiegelungen des Bretts), gibt es 12 eindeutige Lösungen. Für N=1 gibt es trivial 1 Lösung; N=2 und N=3 haben 0 Lösungen; die Anzahl wächst rasch: N=12 hat 14.200 Lösungen und N=15 hat 2.279.184.

Wie löst Backtracking mit Constraint-Propagierung das N-Damen-Problem effizient?

Der Algorithmus platziert Damen zeilenweise. Bevor er eine Dame in einer Spalte platziert, prüft er, ob diese Spalte oder eine der Diagonalen bereits angegriffen wird. Falls ja, überspringt er diese Spalte. Gibt es in einer Zeile keine gültige Spalte, macht er einen Rückzug zur vorherigen Zeile und probiert dort die nächste Spalte. Diese Spalten- und Diagonalfilterung beschneidet ungültige Zweige, bevor sie vollständig durchsucht werden, und reduziert den Aufwand von O(N!) auf in der Praxis deutlich weniger.

Ist das N-Damen-Problem NP-vollständig?

Zu entscheiden, ob eine teilweise Platzierung von Damen zu einer vollständigen Lösung erweitert werden kann (das „N-Damen-Vervollständigungsproblem“), wurde 2017 von Gent, Jefferson und Nightingale als NP-vollständig gezeigt. Das Finden einer einzigen Lösung für das Standard-N-Damen-Problem (alle N Damen von Grund auf platziert) kann jedoch mit geschlossenen Konstruktionen in O(N)-Zeit erfolgen, sodass die Vervollständigungsvariante strikt schwerer ist als das Standardproblem.

Was ist die O(N)-explizite Konstruktion für N-Damen?

Es existieren mehrere O(N)-explizite Konstruktionen. Eine beruht auf einer expliziten Formel: Wenn N mod 6 ≠ 2 und N mod 6 ≠ 3, platziere die Damen in den Spalten 2, 4, 6, …, N, 1, 3, 5, …, N−1 (zuerst gerade, dann ungerade Spalten). Besondere Anordnungen behandeln die Fälle N mod 6 = 2 und mod 6 = 3. Diese Konstruktionen erzeugen ohne jegliches Backtracking eine gültige Lösung, was nützlich ist, wenn nur eine einzige Lösung benötigt wird statt aller 92 (oder wie viele es auch sind).

Wie beschleunigt Symmetriereduktion die Suche?

Eine naive Backtracking-Suche findet alle 92 Lösungen für N=8. Durch Ausnutzung der 8-fachen Symmetriegruppe des Quadrats (4 Drehungen × 2 Spiegelungen) muss man nur die erste Hälfte der ersten Zeile durchsuchen (Spalten 1–4) und dann jede gefundene Lösung spiegeln, wodurch die Suche um etwa den Faktor 8 reduziert wird. Diese Symmetriebrechung ist Standard in der kombinatorischen Suche und Constraint-Programmierung.

Was ist Forward-Checking im Kontext von N-Damen?

Forward-Checking ist eine Vorausschau-Technik: Nach dem Platzieren einer Dame entfernt der Algorithmus sofort alle angegriffenen Felder aus den Domänen (verfügbaren Spalten) zukünftiger Zeilen. Wird die Domäne einer zukünftigen Zeile leer, wird der aktuelle Zweig sofort beschnitten, statt zu warten, bis diese Zeile erreicht wird. Für N-Damen entspricht dies der Verfolgung von drei Bitvektoren: einem für angegriffene Spalten, einem für angegriffene linke Diagonalen und einem für angegriffene rechte Diagonalen.

Kann Bitmanipulation den N-Damen-Löser schneller machen?

Ja. Ein klassischer Bitmanipulations-Löser (Martin Richards, 1997) stellt angegriffene Spalten, linke und rechte Diagonalen als einzelne Ganzzahlen dar und nutzt bitweises UND, ODER und Verschiebungen, um verfügbare Positionen zu berechnen. Jede Platzierung ist ein einzelnes gelöschtes Bit aus der Spaltenmaske; Backtracking stellt die Maske wieder her. Dies erlaubt modernen CPUs, Millionen Positionen pro Sekunde zu durchsuchen, und kann alle 92 Lösungen für N=8 in Mikrosekunden finden.

Gibt es praktische Anwendungen des N-Damen-Problems?

Das N-Damen-Problem dient als Benchmark für Constraint-Löser und parallele Suche. Constraint-Programmierungssysteme wie Choco, Gecode und OR-Tools führen es als Standardtestfall auf. Die zugrunde liegende Technik — nicht konfliktbehaftete Elemente auf einem strukturierten Gitter zu platzieren — hat Entsprechungen im VLSI-Chipdesign (Platzierung nicht störender Schaltungselemente), in der Planung (Zuweisung nicht überlappender Zeitfenster) und in der Vorhersage von RNA-Sekundärstrukturen.

Wie viele Lösungen hat N-Damen für große N?

Die exakte Anzahl der Lösungen Q(N) wächst annähernd exponentiell; die Folge ist OEIS A000170. Q(20) = 39.029.188.884, und Q(27) = 234.907.967.154.122.528. Für N ≥ 28 wurden bis 2024 keine exakten Zahlen veröffentlicht; allein die Berechnung von Q(28) würde Petaflop-Rechenleistung erfordern. Asymptotische Schätzungen legen Q(N) ≈ (0,143 N)^N nahe, aber die exakte Asymptotik ist ein offenes Forschungsproblem.

Welche Verbindung besteht zwischen N-Damen und lateinischen Quadraten?

Eine Lösung des N-Damen-Problems, bei der die Damen auch unterschiedliche gebrochene Diagonalen (torusförmig um das Brett gewickelte Diagonalen) besetzen, wird als „toroidale“ oder „modulare“ N-Damen-Lösung bezeichnet und entspricht einer Transversale eines zyklischen lateinischen Quadrats. Solche Lösungen existieren nur für N, die nicht durch 2 oder 3 teilbar sind. Diese Verbindung verknüpft Kombinatorik, Gruppentheorie und das Design orthogonaler lateinischer Quadrate, die in der statistischen Versuchsplanung verwendet werden.

Über diese Simulation

Diese Simulation führt den klassischen Backtracking-Algorithmus für das N-Damen-Problem aus, platziert Damen spaltenweise auf einem N×N-Brett und zieht sich sofort zurück, sobald eine Platzierung mit einer früheren Dame kollidiert. Jede vollständige, konfliktfreie Anordnung wird als Lösung protokolliert, bevor die Suche zurückgeht, um weitere zu finden.

🔬 Was es zeigt

Ein live aktualisiertes N×N-Brett, auf dem Damen spaltenweise platziert werden. Grün bedeutet, dass eine Dame sicher steht, Gelb markiert die gerade getestete Dame, Rot hebt einen Konflikt mit einer früheren Dame hervor, und ein kurzes blaues Aufblitzen markiert eine vollständige Lösung.

🎮 Bedienung

Ziehe den N-Regler (4 bis 12), um die Brettgröße zu ändern, und den Geschwindigkeitsregler, um das Tempo zu steuern. Drücke Ausführen, um die Suche automatisch zu animieren, Schritt, um eine Platzierung oder einen Rückzug einzeln vorzurücken, oder Zurücksetzen, um von einem leeren Brett zu beginnen.

💡 Wusstest du schon?

Das Standard-8×8-Brett hat genau 92 Lösungen, erstmals untersucht vom Schachkomponisten Max Bezzel im Jahr 1848; nur 12 davon sind grundlegend unterschiedlich, wenn Drehungen und Spiegelungen entfernt werden.

Häufig gestellte Fragen

Wie entscheidet der Backtracking-Algorithmus, wo jede Dame platziert wird?

Für jede Spalte probiert er die Zeilen von oben nach unten und prüft, ob die neue Dame eine Zeile oder Diagonale mit einer bereits platzierten Dame teilt. Die erste sichere Zeile wird verwendet, und die Suche geht zur nächsten Spalte über.

Was passiert, wenn keine Zeile in einer Spalte sicher ist?

Wenn jede Zeile mit einer bestehenden Dame in Konflikt steht, macht der Algorithmus einen Rückzug: Er entfernt die vorherige Dame und fährt dort mit der nächsten Zeile fort, was die Statistik „Rückzüge“ zählt.

Warum macht eine Erhöhung von N die Suche so viel langsamer?

Die Möglichkeiten, N Damen zu platzieren, wachsen mit der Brettgröße etwa exponentiell — N=8 hat 92 Lösungen, N=12 hat 14.200 — und die zum Auffinden aller Lösungen nötigen Backtracking-Schritte wachsen noch schneller.

Was bedeuten die vier Farben auf dem Brett?

Gelb markiert die gerade getestete Dame, Grün markiert als sicher bestätigte Damen, Rot hebt einen Konflikt mit einer früheren Dame hervor, und ein blaues Aufblitzen markiert jede Spalte, die ohne Konflikt gefüllt wurde.

Findet der Algorithmus jede mögliche Lösung oder nur eine?

Lässt man ihn laufen, setzt er das Backtracking nach jeder Lösung fort, um nach weiteren zu suchen, bis der gesamte Suchbaum erschöpft ist, sodass „Gefundene Lösungen“ jede gültige Anordnung für das gewählte N zählt.

⚙ Unter der Haube

Platziere N Damen auf einem Schachbrett ohne gemeinsame Zeile, Spalte oder Diagonale und beobachte, wie Backtracking den Suchbaum Feld für Feld beschneidet.

N-DamenAcht DamenBacktrackingConstraint-ErfüllungKombinatorikSchachrätselAlgorithmusvisualisierung

3D · Three.js / WebGL-Renderer · Ziel 60 FPS · läuft vollständig clientseitig, keine Installation nötig