Acht Damen, Springerproblem nach Euler, verstümmeltes Schachbrett: die großen mathematischen Denksportaufgaben des Schachbretts

Diese Denksportaufgaben werden mit den Figuren oder dem Raster des Schachbretts gelöst, haben aber mit einer Partie nichts zu tun: Es handelt sich um echte mathematische Probleme, die bereits in der Sekundarstufe zugänglich sind und von denen einige große Namen des Fachs beschäftigt haben. Sie eignen sich hervorragend für einen Mathe-Club, ein Referat oder ein Abiturthema.

Übersichtstabelle

Das Achtdamenproblem

Das Achtdamenproblem

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

Das Problem wurde 1848 von Max Bezzel veröffentlicht, einem Schachproblemkomponisten. Franz Nauck veröffentlichte 1850 die ersten Lösungen und verallgemeinerte es auf n Damen auf einem Brett mit n × n Feldern. Zu den Mathematikern, die sich dafür interessierten, gehört Carl Friedrich Gauß.

Ziel des Problems: eine Aufstellung finden, und dann alle. Es gibt 92 davon. Viele gehen durch Drehung oder Spiegelung des Schachbretts 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 überprüft leicht, dass jede Reihe und jede Spalte genau eine Dame enthält. Bei den Diagonalen genügt es zu kontrollieren, dass für je zwei Damen der Spaltenabstand nie gleich dem Reihenabstand ist.

Wie löst man es?

Die klassische Methode ist das Rücksetzverfahren (englisch backtracking): Man setzt eine Dame in die erste Spalte, dann eine Dame in die zweite Spalte auf ein nicht angegriffenes Feld, und so weiter; wenn kein Feld mehr möglich ist, geht man zurück und versetzt die vorherige Dame. Es ist eine sehr beliebte Aufgabe im Informatikunterricht am Gymnasium. Die Version mit n Damen hat für alle n außer 2 und 3 Lösungen: zum Beispiel 2 Lösungen für n = 4, 10 für n = 5, 4 für n = 6 und 40 für n = 7.

Das Springerproblem nach Euler

Springerproblem

Eine Folge von Springerzügen finden, die jedes der 64 Felder genau einmal besucht. Der Weg heißt geschlossen, wenn das letzte Feld einen Springerzug vom ersten entfernt liegt, sodass sich der Kreislauf wiederholen lässt.

Das Problem ist sehr alt: Ein Rösselsprung-Weg über einen halben Schachbrett findet sich bereits in einer sanskritischen Poetik des 9. Jahrhunderts, dem Kavyalankara von Rudrata. Leonhard Euler widmete ihm eine Abhandlung, „Solution d'une question curieuse qui ne paroit soumise à aucune analyse“, die 1759 vorgelegt und 1766 in den Memoiren der Berliner Akademie der Wissenschaften veröffentlicht wurde. 1823 schlug H. C. von Warnsdorff eine einfache Regel vor, um einen solchen Weg zu finden: Man geht stets zu dem Feld, von dem aus der Springer die wenigsten Zugmöglichkeiten hat.

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

Ein Weg zum Nachprüfen auf einem Schachbrett mit 5 × 5 Feldern

Zum Üben kann man mit einem kleineren Brett beginnen. Hier ist ein offener Weg, der alle 25 Felder eines Schachbretts mit 5 × 5 Feldern besucht: Folgen Sie den Zahlen von 1 bis 25; jede Zahl liegt einen Springerzug von der vorherigen entfernt.

Dieser Weg wurde mit der Regel von Warnsdorff gefunden, und jeder Sprung wurde überprüft. Herausforderung: Finden Sie einen anderen, der im Zentrum beginnt.

Das Springerproblem beim großen Abitur-Vortrag

Das Thema eignet sich gut für die mündliche Prüfung im Abitur-Leistungsfach Mathematik oder Informatik: 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, Regel von Warnsdorff und ihre Effizienz. Man kann auch erklären, warum es auf einem Schachbrett mit 5 × 5 Feldern keinen geschlossenen Weg gibt: Der Springer wechselt bei jedem Sprung die Feldfarbe, ein Kreislauf hat also notwendigerweise eine gerade Anzahl von Feldern, 25 aber ist ungerade.

Das verstümmelte Schachbrett

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

Antwort: nein. Jeder Dominostein bedeckt notwendigerweise ein weißes und ein schwarzes Feld. 31 Dominosteine würden also 31 weiße und 31 schwarze Felder bedecken. Die beiden gegenüberliegenden Ecken haben jedoch dieselbe Farbe: Es bleiben 32 Felder der einen und 30 der anderen Farbe. Die Belegung ist unmöglich, ohne dass man auch nur eine Anordnung ausprobieren müsste. Martin Gardner machte dieses Problem 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 (Ergebnis veröffentlicht 1973), dass die Belegung dann stets möglich ist, unabhängig davon, welche beiden Felder entfernt werden.

Polyominos und Pentominos

Ein Polyomino ist eine Form aus gleichen Quadraten, die an ihren Seiten zusammenhängen; das Domino besteht aus zwei, das Pentomino aus fünf Quadraten. Der Mathematiker Solomon Golomb hat diese Formen 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 von 2 × 2 frei bleibt. 1958 ließ Dana Scott dieses Problem von einem Computer lösen, einer 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 pflastern.

Wie viele Quadrate gibt es auf einem Schachbrett?

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

Die Gesamtzahl ist die Summe der Quadratzahlen der Ganzzahlen von 1 bis 8: 1 + 4 + 9 + … + 64 = 204. Zum Weiterdenken: Ein Schachbrett enthält 1 296 Rechtecke (einschließlich der Quadrate), denn ein Rechteck ist durch die Wahl von 2 Linien aus den 9 Linien des Rasters und von 2 Spalten aus 9 bestimmt, also 36 × 36.

Weiterlesen

Diese Probleme beruhen auf genauen Begriffen: Parität, Färbung, Abzählen, Graphen. Wir erläutern sie mit Übungen für Grundschule und Sekundarstufe auf der Seite die auf dem Schachbrett verwendeten mathematischen Begriffe. Zu anderen sehr großen Zahlen siehe das Schachbrett von Sissa. Und für alle, die gern knobeln, bietet der Blog des Palais des Échecs die Logikaufgaben des Palais des Échecs, die regelmäßig erneuert werden.