In Queens

Beim „N-Königinnen“-Rätsel muss der Spieler N Schachköniginnen so auf einem N×N-Schachbrett platzieren, dass sich keine zwei Königinnen gegenseitig bedrohen. Da eine Königin entlang ihrer Reihe, Spalte und beider Diagonalen angreifen kann, dürfen sich keine zwei Königinnen in derselben Reihe, Spalte oder Diagonale befinden. Die klassische Version verwendet ein 8×8-Brett mit 8 Damen, aber das Rätsel kann auf Brettern jeder Größe ab 4×4 gespielt werden (für 2×2 oder 3×3 gibt es keine Lösung). Die Anzahl der unterschiedlichen Lösungen wächst mit der Größe des Bretts rapide an – das 8-Damen-Problem hat 92 Lösungen (12 einzigartige, wenn man Symmetrien berücksichtigt).

Regeln

1. Platziere N Königinnen auf einem N×N-Schachbrett.
2. Es dürfen sich keine zwei Königinnen in derselben Zeile befinden.
3. Es dürfen sich keine zwei Königinnen in derselben Spalte befinden.
4. Es dürfen sich keine zwei Königinnen auf derselben Diagonale befinden (in beide Richtungen).
5. Alle N Königinnen müssen gleichzeitig auf dem Brett platziert werden.

Strategien

• Reihenweise Platzierung: Setze eine Königin pro Reihe, beginnend von oben. Dadurch wird die Reihenbedingung automatisch erfüllt und das Problem reduziert sich darauf, für jede Reihe eine Spalte auszuwählen.
• Spaltenverfolgung: Behalten Sie im Blick, welche Spalten bereits belegt sind. Jede neue Königin muss in eine freie Spalte gesetzt werden.
• Diagonalverfolgung: Für die beiden diagonalen Richtungen haben Felder auf derselben Diagonale einen konstanten Wert von (Zeile – Spalte) bzw. (Zeile + Spalte). Behalte diese Werte im Auge, um sichere Felder schnell zu identifizieren.
• Zurückverfolgung: Wenn du eine Zeile erreichst, in der keine Spalte sicher ist, kehre zur vorherigen Zeile zurück und probiere die nächste verfügbare Spalte aus. Dieser systematische Ansatz garantiert, dass eine Lösung gefunden wird.
• Ausnutzung von Symmetrien: Lösungen können um 90°, 180° und 270° gedreht sowie gespiegelt werden. Findet man eine Lösung, erhält man automatisch bis zu 8 verwandte Lösungen.
• Beginne an den Ecken: Das Platzieren einer Dame in einer Ecke schließt sofort viele Felder aus, was paradoxerweise die verbleibende Platzierung erleichtern kann, da sich die Auswahlmöglichkeiten verringern.

Das „N-Königinnen-Rätsel“ entstand ursprünglich als „Acht-Königinnen-Rätsel“, das erstmals 1848 vom Schachspieler Max Bezzel in der deutschen Schachzeitschrift „Schachzeitung“ vorgeschlagen wurde. Die Herausforderung, acht Königinnen so auf einem Standard-Schachbrett zu platzieren, dass sich keine gegenseitig angreift, beflügelte die Fantasie von Mathematikern und Schachbegeisterten gleichermaßen.

Die ersten Lösungen wurden 1850 von Franz Nauck veröffentlicht, der das Problem auch auf N Damen auf einem N×N-Brett verallgemeinerte. Der große Mathematiker Carl Friedrich Gauß interessierte sich für das Problem und korrespondierte darüber mit seinem Freund Heinrich Schumacher, obwohl Gauß zunächst nur 72 der 92 Lösungen für den Fall mit 8 Königinnen fand und fälschlicherweise glaubte, dies sei die vollständige Menge.

Das Rätsel wurde zu einem grundlegenden Problem der Informatik. Im Jahr 1972 nutzte Edsger Dijkstra das 8-Königinnen-Problem, um die Leistungsfähigkeit der strukturierten Programmierung und des Backtracking-Algorithmus zu veranschaulichen. Es ist nach wie vor eine der am häufigsten gestellten Programmieraufgaben in Informatikstudiengängen an Universitäten und dient dazu, Rekursion, die Erfüllung von Nebenbedingungen und den Entwurf von Algorithmen zu vermitteln. Es dient zudem als Maßstab für den Vergleich der Effizienz verschiedener Suchalgorithmen und Techniken der Constraint-Propagation.

Das Problem der N Königinnen weist Verbindungen zu vielen Bereichen der Mathematik auf, darunter Kombinatorik, Gruppentheorie (aufgrund seiner Symmetrien) und lineare Algebra. Im Jahr 2021 gelang ein bedeutender Durchbruch, als Michael Simkin eine asymptotische Formel für die Anzahl der Lösungen bewies und damit eine seit langem bestehende Vermutung bestätigte. Das Problem findet zudem praktische Anwendungen in der parallelen Speichertechnik, beim Testen von VLSI-Schaltungen und in der Verkehrssteuerung. Trotz seiner scheinbar einfachen Formulierung offenbart das Problem der N Königinnen immer wieder neue mathematische Tiefen.