Das Halsband der Dame

Ein echtes Halsband mit vielen Perlen.

Der Titel ist scherzhaft gemeint: es geht natürlich um die mathe­matischen Halsbänder (necklaces), und um deren Bezug zum Damen-Problem.

Was ist ein mathematisches Halsband?

Es scheint, dass Mathematiker echte Halsbänder ober­flächlich betrachten. Ein Hals­band besteht aus Teilen, die an einer Schnur aufgereiht sind. Die Teile sind meist Perlen, es kann aber auch eine Brosche oder ein ausgearbeitets Metall- oder Holz-Stück enthalten sein.

Ein reales Halsband hat einen Verschluss, und damit einen Punkt, an dem man beginnt, wenn man es im Detail be­schreiben will. Das mathematische Hals­band dagegen hat keinen Verschluss, man kann an beliebiger Stelle anfangen, und es handelt sich immer um das gleiche mathematische Halsband. Die Teile sind allesamt Perlen (beads), und sie sind über­dies alle gleich - bis auf die Farbe. Wichtig ist also nur die Anzahl der Perlen, und die Abfolge von deren Farben. In der Konsequenz kann man mathematische Hals­bänder auch umdrehen, und es bleibt dasselbe Halsband.

So war das, soweit ich mitbekommen habe, noch vor einiger Zeit. Inzwischen schauen die Mathematiker das Halsband offenbar genauer an, wie ich aus dem englischen Eintrag bei Wikipedia erfahren habe: die Halsbänder darf man nicht mehr umdrehen; das Objekt, das man umdrehen kann, heißt jetzt Armband (bracelet). Alternativ unterscheidet man freie (free) und orientierte (fixed) Halsbänder. In diesen Seiten verwende ich aber generell noch die alte Bezeichnung, es wird noch etwas dauern, bis ich alles umgestellt habe.

In der Sprache der Mathematik geht man also von endlichen Folgen von Farben aus, und definiert ein Hals­band als die Äquivalenzklasse dieser Folgen unter Drehung und Spiegelung. Die Spiegelung ist in diesem Fall einfach die Inversion, das Rückwärts-Lesen, der Folge. Oder noch etwas anders ausgedrückt: ein Hals­band ist eine Bahn in der Menge der endlichen Farb­folgen unter der Aktion der Dieder-Gruppe.

Ähnlichkeit von Halsbändern

Für das Damen-Problem (siehe unten) benutze ich nicht die normalen mathematischen Halsbänder, sondern Äquivalenz-Klassen bezüglich Streckung. Die Anzahl der Perlen entspricht der Größe des Brettes, also der Anzahl von Feldern in einer Zeile oder Spalte. Während in der Unterscheidung Halsband gegen Armband eine Transformation weggenommen wird, kommen hier Transformationen dazu. Eine Streckung ist dann ohne Probleme (= umkehrbar) möglich, wenn der Streckungs-Faktor relativ prim ist zur Größe des Brettes.

Den Äquivalenz-Klassen bezüglich Streckung kann man dann noch eine Ordnung geben. Zum Beispiel so, dass Halsbänder mit weniger schwarzen Perlen kleiner sind als solche mit mehr schwarzen Perlen. Ist die Anzahl der schwarzen Perlen gleich, so entscheidet die "alfabetische Anordnung". Dabei muss man aber zuerst zum kleinsten Vertreter aus der Äquivalenz-Klasse übergehen.

In ein paar Bildern sind hier Beispiele für die Äquivalenzklassen angegeben. Sie sehen die Bilder in normaler Größe, wenn sie darauf klicken.

Größe	Anzahl schwarzer (oder roter) Perlen
11	Alle zusammen in einem Bild:
35	3	6	7
35

Bezug zum Damen-Problem

In gewisser Weise sind Halsbänder das eindimensionale Pendant zum Torus-Schachbrett oder zum Torus-Damen-Problem.

Man kann die Felder des n mal n Schachbrettes in Linien der Länge n aufteilen. Das geht zum Beispiel mit den waagrechten Linien, den Zeilen (oder "Reihen" in der Schach-Sprache) oder den senkrechten Linien, den Spalten, die im Schach "Linien" heißen. Es geht aber ähnlich mit den Diagonalen oder Gegen-Diagonalen. Auf dem begrenzten Brett sind diese Diagonalen teilweise verkürzt, aber beim Torus-Brett von n mal n Feldern haben sie die gewünschte Länge von n Feldern. Ein Halsband mit den beiden Farben Schwarz und Weiß entsteht, wenn man für ein leeres Feld eine weiße Perle nimmt, und eine schwarze Perle für ein Feld mit Dame.

Die so entstehenden Halsbänder sind noch wenig interessant. Für Zeilen und Spalten ergibt sich immer das gleiche Halsband: eine Perle ist schwarz, alle anderen sind weiß. Bei den Diagonalen gilt dasselbe, wenn wir Torus-Lösungen betrachten. Hingegen kann es eine Variation geben, wenn wir das normale Damen-Problem aus der Perspektive des Torus-Brettes betrachten: eventuell stehen zwei Damen auf derselben Torus-Diagonale, oder gar keine.

Es gibt aber noch weitere Aufteilungen des Schachbrettes in Linien. Zum Beispiel kann man Springer-Linien nehmen; eine Springer-Linie entsteht, wenn man immer eine Zeile hoch und zwei Spalten nach rechts geht.

Damen auf einer Springer-Linie; eine Torus-Lösung für n = 13.

Im Prinzip kann man alle Partitionen der Felder des Brettes nehmen, bei denen jede Teilmenge n Elemente hat, die Teilmengen numerieren, und eine (zyklische) Reihenfolge innerhalb jeder Teilmenge festlegen. Dann erhält man aus einer Damen-Aufstellung eine Folge von Halsbändern. Das ist dann jedoch so allgemein, dass ich keine sinnvolle Anwendung dafür sehe.

Sinnvoll und hinreichend allgemein nimmt man wohl die Partitionen, die aus der Partition duch horizontalen Linie entsteht, wenn man eine umkehrbare affine Abbildung erlaubt.

Auf solchen Linien können fast beliebige schwarz-weiße Halsbänder entstehen. Ist n ungerade und auch nicht durch 3 teilbar, dann bekommt man eine Torus-Lösung, wenn man ein Springer-Linien-Halsband ganz schwarz wählt (alle Perlen sind schwarz), und alle anderen, parallelen Springer-Halsbänder ganz weiß. Die Damen stehen also genau in einer Springer-Linie.

Konkretere Anwendung beim Damen-Problem

Man kann die Lösungs-Mengen nach maximalen Halsbändern auf Diagonalen oder Gegen-Diagonalen ordnen. Dabei nützt man aus, dass eine kongruente Abbildung der Lösung das maximale Hals­band und auch deren Anzahl unverändert lässt. Das maximale Hals­band bezüglich Diagonalen von einer Damen-Lösung hat entweder eine oder zwei Perlen. Jedes Zwei-Perlen-Hals­band auf einer Diagonale entspricht einem Konflikt zwischen zwei Damen, der erst auf dem Torus sichtbar wird (siehe "Konflikte").

Ist das maximale Halsband einer Lösung das Hals­band mit nur einer schwarzen Perle, so ist die Lösung eine Torus-Lösung. Besonders in diesem Fall ist es sinnvoll, noch einen Schritt weiter­zu­gehen.

Dazu ordne ich die Lösungen nach maximalem Hals­band auf den Springer-Linien. Es gibt vier Arten von Springer-Linien: steil oder flach, und nach oben oder nach unten. Das Maximum suche ich immer unter diesen 4n Linien.

Zusätzlich benutze ich nicht die normalen mathematischen Halsbänder, sondern Äquivalenz-Klassen bezüglich Streckung, die oben beschrieben sind.

Diese Äquivalenz-Klassen von Halsbändern passen genau zur Aktion der ähnlichen Trans­formationen auf dem Schach­brett. Beim Suchen nach Torus-Lösungen nimmt man sich nach­einander alle Äquivalenz-Klassen; man setzt die ersten Damen so, wie es ein Hals­band angibt. Dann ergänzt man. Der springende Punkt ist, dass man nun alle Felder ausschließen kann, die zu einem größeren Halsband führen.

Mir der oben angedeuteten Ordnung beginnt man mit wenigen Damen; dann wirkt die Einschränkung sehr stark, und man kann relativ schnell alle möglichen Erweiterungen finden. Mit etwas mehr Damen wird der Suchraum zunächst größer. Dann aber kommt man zu den Halsbändern mit vielen Perlen, und da schränkt die Anzahl der schon gesetzten Damen den Suchraum wieder ein.