Acht Damen, das Springerproblem von Euler und das beschnittene Schachbrett: die großen mathematischen Knobelaufgaben rund um das Brett

Diese Knobelaufgaben löst man mit den Figuren oder dem Raster des Bretts, doch eine Partie spielt dabei keine Rolle: Es handelt sich um echte mathematische Fragestellungen, die schon in der Sekundarstufe verständlich sind und bereits bedeutende Namen des Fachs beschäftigt haben. Sie passen gut in einen Mathe-Kreis, auf ein Referat oder als Thema für die Matura.

Übersicht

Das Achtdamenproblem

Das Achtdamenproblem

Acht Damen auf einem Brett mit 8 × 8 Feldern so aufzustellen, dass keine die andere schlagen kann: niemals zwei Damen in derselben Reihe, derselben Spalte oder auf derselben Diagonale.

Veröffentlicht wurde das Problem 1848 von Max Bezzel, einem Schachproblemkomponisten. Franz Nauck legte 1850 die ersten Lösungen vor und verallgemeinerte die Aufgabe auf n Damen auf einem Brett mit n × n Feldern. Unter den Mathematikern, die sich dafür interessierten, war auch Carl Friedrich Gauß.

Ziel der Aufgabe: eine Aufstellung finden und anschließend alle. Es sind 92. Viele davon gehen durch Drehen oder Spiegeln des Bretts auseinander hervor; fasst man sie zusammen, bleiben 12 grundlegende Lösungen. Hier ist eine davon, mit den Damen auf d8, g7, c6, h5, b4, e3, a2 und f1:

Man prüft leicht nach, dass jede Reihe und jede Spalte genau eine Dame enthält. Bei den Diagonalen genügt die Kontrolle, dass bei je zwei Damen der Spaltenabstand niemals dem Reihenabstand entspricht.

Wie geht man vor?

Die klassische Methode ist das Rücksetzverfahren (englisch backtracking): Man stellt eine Dame in die erste Spalte, danach eine Dame in die zweite Spalte auf ein nicht bedrohtes Feld und so weiter; ist kein Feld mehr frei, geht man zurück und versetzt die vorige Dame. Im Informatikunterricht am Gymnasium ist das eine sehr beliebte Übung. Für jedes n außer 2 und 3 gibt es Lösungen: etwa 2 für n = 4, 10 für n = 5, 4 für n = 6 und 40 für n = 7.

Das Springerproblem von Euler

Springerproblem

Man sucht eine Folge von Springerzügen, die jedes der 64 Felder genau einmal erreicht. Der Weg heißt geschlossen, wenn das letzte Feld von einem Springerzug aus dem ersten erreichbar ist, sodass sich der Kreislauf wiederholen lässt.

Die Aufgabe ist uralt: Eine Springerreise, die über ein halbes Schachbrett führt, taucht schon in einer sanskritischen Poetik des 9. Jahrhunderts auf, im Kavyalankara von Rudrata. Leonhard Euler befasste sich in einer Abhandlung mit ihr, „Solution d'une question curieuse qui ne paroit soumise à aucune analyse“, die 1759 eingereicht und 1766 in den Memoiren der Berliner Akademie der Wissenschaften gedruckt wurde. Im Jahr 1823 legte H. C. von Warnsdorff eine unkomplizierte Faustregel nahe, mit der sich ein solcher Weg auffinden lässt: Man wählt immer das Feld, auf dem der Springer die geringste Anzahl an Zügen zur Verfügung hat.

Auf dem gewöhnlichen Schachbrett gibt es eine ungeheure Zahl geschlossener Wege: 26 534 728 821 064, wenn man die Laufrichtung berücksichtigt; die Hälfte davon, 13 267 364 410 532, wenn ein Weg und sein Rückweg als dasselbe gelten.

Ein Weg zum Nachvollziehen auf einem Brett mit 5 × 5 Feldern

Zum Einüben kann man mit einem kleineren Brett beginnen. Hier ist ein offener Weg, der alle 25 Felder eines Bretts mit 5 × 5 Feldern besucht: Man folgt den Zahlen von 1 bis 25, wobei jede Zahl einen Springerzug von der vorigen entfernt liegt.

Dieser Weg wurde mithilfe der Warnsdorff-Regel gefunden, und jeder Sprung wurde nachgeprüft. Herausforderung: Finden Sie einen anderen Weg, der im Zentrum beginnt.

Das Springerproblem im Vortrag zur Matura

Das Thema eignet sich gut für die mündliche Prüfung im Schwerpunktfach Mathematik oder Informatik der Matura: Modellierung durch einen Graphen (die Felder sind die Knoten, die möglichen Sprünge die Kanten), Suche nach einem Weg, der alle Knoten durchläuft, Backtracking-Algorithmus, Warnsdorff-Regel und deren Effizienz. Man kann auch begründen, warum es auf einem Brett mit 5 × 5 Feldern keinen geschlossenen Weg gibt: Der Springer wechselt bei jedem Sprung die Feldfarbe, ein Kreislauf muss also eine gerade Anzahl von Feldern umfassen, 25 aber ist ungerade.

Das beschnittene Schachbrett

Der Philosoph Max Black stellte die Aufgabe 1946 in seinem Buch Critical Thinking. Man entfernt zwei gegenüberliegende Ecken eines Schachbretts (etwa a1 und h8). Lassen sich die verbleibenden 62 Felder mit 31 Dominosteinen belegen, sodass jeder Stein zwei benachbarte Felder bedeckt?

Antwort: nein. Jeder Dominostein bedeckt zwangsläufig ein weißes und ein schwarzes Feld. 31 Steine würden also 31 weiße und 31 schwarze Felder abdecken. Die beiden entfernten Eckfelder haben jedoch dieselbe Farbe: Übrig bleiben 32 Felder der einen und 30 der anderen Farbe. Die Belegung ist daher unmöglich, ohne dass man eine einzige Anordnung ausprobieren müsste. Martin Gardner machte die Aufgabe 1957 in seiner Kolumne im Scientific American einem breiten Publikum bekannt.

Und wenn man ein weißes und ein schwarzes Feld entfernt? Ralph Gomory hat bewiesen (veröffentlicht 1973), dass die Belegung dann stets möglich ist, gleichgültig, welche zwei Felder man entfernt.

Polyominos und Pentominos

Ein Polyomino ist eine Figur aus gleich großen Quadraten, die über ihre Seiten miteinander verbunden sind; das Domino besteht aus zwei, das Pentomino aus fünf Quadraten. Der Mathematiker Solomon Golomb hat diese Figuren ab 1953 eingeführt und untersucht. Es gibt 12 verschiedene Pentominos (wenn man ein gewendetes oder gedrehtes Teil als dasselbe betrachtet), die zusammen 60 Felder bedecken.

Ein Schachbrett hat 64 Felder, also 60 + 4: Man kann daher versuchen, die 12 Pentominos so auf das Brett zu legen, dass in der Mitte ein Quadrat aus 2 × 2 Feldern frei bleibt. 1958 ließ Dana Scott diese Aufgabe von einem Computer lösen, eine der ersten Anwendungen der Backtracking-Methode: Es gibt 65 Lösungen. Eine weitere berühmte Herausforderung: Das Rechteck von 6 × 10 lässt sich auf 2 339 verschiedene Arten mit den 12 Pentominos auslegen.

Wie viele Quadrate lassen sich auf einem Schachbrett zählen?

Die Antwort „64“ ist falsch oder zumindest unvollständig: Sie zählt nur die kleinen Quadrate. Man muss auch die Quadrate mit 2 × 2, 3 × 3 … bis hin zum großen Quadrat mit 8 × 8 Feldern hinzuzählen.

Die Gesamtzahl ist die Summe der Quadratzahlen der ganzen Zahlen von 1 bis 8: 1 + 4 + 9 + … + 64 = 204. Zum Weiterdenken: Ein Schachbrett enthält 1 296 Rechtecke (die Quadrate eingeschlossen), denn ein Rechteck wird durch die Wahl von 2 der 9 Rasterlinien in einer Richtung und 2 der 9 in der anderen festgelegt, also 36 × 36.

Weiterlesen

Diese Aufgaben beruhen auf präzisen Begriffen wie Parität, Färbung, Abzählen und Graphen. Wir erläutern sie mit Übungen für Volksschule und Sekundarstufe auf der Seite die mathematischen Begriffe auf dem Schachbrett. Zu anderen sehr großen Zahlen siehe das Schachbrett von Sissa. Und wer gerne tüftelt, findet im Blog des Palais des Échecs die Logikaufgaben des Palais des Échecs, die regelmäßig erneuert werden.