Das Springerproblem
Eine Springertour ist eine Folge von Springerzügen, die jedes Feld eines Schachbretts genau einmal besucht. Das Springerproblem ist eines der ältesten Rätsel der Unterhaltungsmathematik: Eine Tour über ein halbes Brett erscheint in einem indischen Gedicht aus dem 9. Jahrhundert, und Leonhard Euler untersuchte das Rätsel 1759.
Ein altes Rätsel
Im Kavyalankara, das der indische Dichter Rudrata im 9. Jahrhundert schrieb, ist ein Vers so auf einem halben Schachbrett angeordnet, dass er sich entlang des Wegs eines Springers lesen lässt. Leonhard Euler verfasste 1759 die erste mathematische Untersuchung des Springerproblems, mit Verfahren, um Touren zu bilden und sie in geschlossene umzuwandeln.
Ein Weg durch einen Graphen
Stellen Sie sich jedes Feld als Punkt vor und jeden Springerzug als Linie zwischen zwei Punkten. Eine Springertour ist dann ein Weg, der jeden Punkt genau einmal besucht, was Mathematiker einen Hamiltonpfad nennen; eine geschlossene Tour ist ein Hamiltonkreis. In den meisten Netzwerken ist ein solcher Weg sehr schwer zu finden. Das Netzwerk des Springers ist großzügig: Es hat so viele Touren, dass eine gute Regel schnell eine findet.
Die Warnsdorff-Regel
H. C. von Warnsdorff beschrieb seine Regel 1823: immer auf das Feld springen, das die wenigsten weiteren Züge offenlässt. Felder am Rand haben wenige Nachbarn, daher besucht die Regel sie früh, statt sie abgeschnitten zurückzulassen. Haben zwei Felder denselben Wert, muss gewählt werden, und eine unglückliche Wahl kann den Springer trotzdem festsitzen lassen. In der App markieren die goldenen Zahlen die Felder, die die Regel wählen würde.
Suche mit Backtracking
Lösen folgt Warnsdorffs Reihenfolge, vertraut ihr aber nicht blind. Es sucht per Tiefensuche, und sobald ein unbesuchtes Feld nicht mehr erreichbar ist, verwirft es diesen Zweig und versucht den nächsten Zug. Auf Brettern bis 10×10 findet es meist sofort eine Tour. Wenn Ihr eigener Weg den Springer eingemauert hat, geht es zuerst ein paar Züge zurück.
Farben und geschlossene Touren
Jeder Springerzug wechselt die Farbe des Feldes. Auf einem Brett mit ungerader Seitenlänge wie 5×5 gibt es ein Feld mehr in der Eckfarbe als in der anderen Farbe, daher muss eine Tour auf der Eckfarbe beginnen und enden. Eine geschlossene Tour ist dort unmöglich, denn eine Schleife mit abwechselnden Farben hat von jeder Farbe gleich viele Felder. Auf Brettern mit gerader Seitenlänge gibt es geschlossene Touren ab 6×6.
In PictorX ausprobieren
Öffnen Sie das Springerproblem und klicken Sie auf ein Feld, um zu beginnen. Die hervorgehobenen Felder sind die erlaubten Sprünge, die goldene Zahl ist Warnsdorffs Wahl, und das Brett hält die Reihenfolge Ihrer Züge fest. Größe stellt das Brett von 5×5 bis 10×10 ein, „Geschlossene Tour“ verlangt von Lösen eine Schleife, und Rückgängig nimmt jeden Zug zurück. Speichern Sie den fertigen Weg als PNG.
Häufig gestellte Fragen
Wer hat das Springerproblem als Erster untersucht?
Touren waren lange bekannt, bevor jemand sie mathematisch untersuchte. Leonhard Euler verfasste 1759 die erste mathematische Abhandlung, und Warnsdorff stellte seine Regel 1823 auf.
Gibt es auf jedem Brett eine Tour?
Quadratische Bretter ab 5×5 haben offene Touren, und die mit gerader Seitenlänge ab 6×6 haben auch geschlossene Touren. Bretter der Größe 2×2, 3×3 und 4×4 haben gar keine Tour.
Wie viele Touren hat ein Schachbrett?
Es gibt 26.534.728.821.064 geschlossene Touren, wenn eine Tour und dieselbe Tour rückwärts getrennt gezählt werden. Die Zahl der offenen Touren liegt bei etwa 19,6 Billiarden.
Lädt PictorX etwas hoch?
Nein. Das Brett wird auf einer Leinwand in Ihrem Browser gezeichnet. Speichern lädt ein PNG herunter, und Bearbeiten öffnet das Bild im PictorX-Editor.
Verwandte Tools
Springerproblem
Springen Sie mit dem Springer genau einmal auf jedes Feld des Bretts. Spielen Sie selbst mit Warnsdorff-Hinweisen, oder sehen Sie zu, wie Lösen eine offene oder geschlossene Tour vollendet. Speichern Sie den Weg als PNG.
Acht Damen
Setzen Sie acht Damen so auf ein Schachbrett, dass keine eine andere angreift. Probieren Sie es selbst, sehen Sie zu, wie die Backtracking-Suche Schritt für Schritt eine Lösung findet, und gehen Sie alle 92 Lösungen durch.
Das Damenproblem
Geschichte und Mathematik des Damenproblems: Max Bezzel und Gauß, die 92 Lösungen in 12 Familien, das n-Damen-Problem und Backtracking.
Türme von Hanoi
Versetzen Sie im Browser einen Turm aus Scheiben über drei Stäbe. Immer nur eine Scheibe, nie eine größere auf eine kleinere. Die kürzeste Lösung hat 2ⁿ − 1 Züge.
Türme von Hanoi
Die Türme von Hanoi: drei Stäbe, immer nur eine Scheibe und nie eine größere auf einer kleineren. Die kürzeste Lösung hat 2ⁿ−1 Züge. Édouard Lucas stellte das Rätsel 1883 vor.
Langtons Ameise
Starten Sie Langtons Ameise im Browser. Sehen Sie Symmetrie, Chaos und die 104-Schritte-Autobahn, und probieren Sie dann mehrfarbige Regeln, mehrere Ameisen, ein Sechseckgitter und Turmiten.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Springerproblem ausprobieren