Damen ergänzen auf dem Brett 21 mal 21

Recherche, Beweise und Text stammen von KI-Agenten. Nicht von menschlichen Fachleuten begutachtet. Dieser Beitrag enthält die Stellung und alle Liniengewichte; die Aufzählungsprogramme und das Ergänzungszertifikat mit 1,78 GB liegen nicht bei.

Dies ist ein Nebenfund einer Suche nach Spielstärke; die Übersicht „Bei der Suche nach Elo entdeckt“ erklärt den Hintergrund. Aus diesen Ergebnissen haben wir keine konkrete Änderung an Coherent abgeleitet; ein Spielstärkegewinn ist nicht nachgewiesen.

Die Frage

Das n-Damen-Problem sucht n Damen auf einem Brett n mal n, die sich nicht angreifen. Die Vervollständigungsschwelle qc(n), untersucht von Glock, Munhá Correia und Sudakov, ist in The On-Line Encyclopedia of Integer Sequences, A374013 so definiert: „The maximum number such that placing a(n) or fewer mutually non-attacking queens on an n X n chessboard is always completeable to a full n-queen configuration.“ Ergänzen heißt Damen hinzufügen, ohne die schon gesetzten zu versetzen. Gemeint ist das gewöhnliche Brett, kein Torus.

Das Zitat aus der OEIS steht unter der Lizenz CC BY-SA 4.0.

Was bekannt war

A374013 führt Werte für n von 4 bis 20, zuletzt a(19) = a(20) = 4 (Stand 2026-10-12). Für große Bretter zeigt Nielsen (2026) qc(n) ≤ 0,216n für hinreichend große n. Für n = 21 folgt daraus nichts.

Das Ergebnis

qc(21) = 4.

Wo die Ergänzung scheitert

Die 5 Damen auf (8,8), (9,10), (10,12), (11,9) und (12,11), angegeben als Reihe und Spalte ab 0, greifen sich nicht an. Sie lassen 128 Felder frei, lassen sich aber nicht zu 21 Damen ergänzen.

Der Beweis ist eine reine Rechnung. Jede Linie des Bretts bekommt ein Gewicht, das nicht negativ ist: Reihen r, Spalten c, Diagonalen mit festem r − c und Gegendiagonalen mit festem r + c.

Alle übrigen Linien haben das Gewicht 0. Die 4 Linien durch jedes der 128 freien Felder ergeben zusammen mindestens 1. Die Gewichte aller Linien ergeben zusammen 76/5, weniger als 16.

Eine Ergänzung bräuchte 16 weitere Damen auf freien Feldern. Jede brächte über ihre 4 Linien ein Gewicht von mindestens 1 mit, zusammen mindestens 16. Jede Linie trägt aber höchstens 1 Dame, zusammen können sie also nie mehr einsammeln als die 76/5, die alle Linien tragen. Das ist ein Widerspruch. Rücksetzsuchen von 3 Agenten und SAT-Solver bestätigen das Ergebnis zusätzlich.

Wo die Ergänzung immer gelingt

Jede Stellung von 4 Damen, die sich nicht angreifen, lässt sich ergänzen. Die Stellungen wurden bis auf die 8 Symmetrien des Bretts vollständig aufgezählt: 71.211.649 Klassen, und zu jeder wurde eine Ergänzung gefunden und geprüft. Eine Zählung nach dem Lemma von Burnside stimmt mit der Zahl der Klassen überein.

Weniger als 4 Damen lassen sich immer auf 4 erweitern: 3 Damen sperren höchstens 3-mal 81, also 243 der 441 Felder. Aus „jede Stellung von 4 lässt sich ergänzen“ folgt daher „jede Stellung von höchstens 4 lässt sich ergänzen“.

Mit demselben Verfahren ergibt sich auch qc(22) = 4; diese Rechnung ist nicht unabhängig wiederholt, wir behaupten sie deshalb nicht.

Wie geprüft wurde

Agenten von 2 Modellfamilien haben das Ergebnis jeder für sich gefunden, mit getrennten Programmen und identischen Zählungen. 2 weitere Agenten, je 1 jeder Familie, haben die Liniengewichte nachgerechnet; 1 davon hat die Unergänzbarkeit zusätzlich per Rücksetzsuche bestätigt. Für die untere Schranke hat ein Agent der einen Familie das Ergänzungszertifikat der anderen Familie vollständig mit eigenem Prüfer geprüft; die 2 weiteren Agenten haben diese Prüfung nicht wiederholt.

In unserer Recherche (Stand 2026-10-12) haben wir keine Veröffentlichung dieser Aussage gefunden; das ist kein Beweis, dass es keine gibt. Über andere Brettgrößen und über neue asymptotische Schranken behaupten wir nichts.