Knight's Tour

KURZES VORWORT Dieses soll kein Fachartikel sein. Wer einen solchen erwartet, der sei auf unseren Aufsatz in der Discrete Applied Mathematics 50/1994, S. 125-134 verwiesen. EINLEITUNG Es gibt manchmal Probleme, die so schwer sind, daß sie entweder nur Verrückten oder Genies einfallen konnten. Und dann gibt es auch wieder solche wie das Springerproblem. Ausgedacht wurde es vor langer Zeit, vor über 200 Jahren, genauer im Jahre 1758, und zwar von einem Schweizer. Dieser Schweizer war kein geringerer als Leonhard Euler, der in Berlin saß und eines schönen Abends nicht an diese damals wie heute zu tiefst provinzielle Stadt dachte, sondern an etwas größeres, an ein Schachbrett: "Gegeben sei ein leeres Schachbrett. Gibt es eine Zugfolge, mit der der Springer alle (schwarzen und weißen) Felder des Brettes genau einmal besucht?" Abb. 1: Zugmöglichkeiten des Springers Hm, eine gute Frage, wird jetzt der geneigte Leser denken. Man kann sie innerhalb von ein paar Minuten selbst lösen, schließlich ist ein Schachbrett nun nicht so gewaltig groß. Abb. 2: Eine formschöne Lösung für ein 8x8-Brett Wie jedoch kann man einen Weg auf größeren Schachbrettern finden? Ein normaler Mensch würde jetzt sagen:"Gar nicht, weil ein Schachbrett immer nur 8x8 Felder hat." Richtig! Doch wie es halt so ist im Leben, Mathematiker sind manchmal nicht normal, und so ging man an, auch einen Weg für ein 10x10-Brett, ein 100x100-Brett und gar ein unendlich großes Brett zu finden. "Ein wirklich gutes Problem", wird der mathematisch interessierte Leser denken (jeder andere wird jetzt nichts denken, denn er ist wahrscheinlich schon auf der nächsten Webpage). Wie gesagt, Euler war Schweizer, und Schweizer gelten im Allgemeinen als sehr gewissenhaft und ebenso langsam. Vielleicht gilt dieses auch für die Lösung von schweizerischen Problemen, jedenfalls konnte das Springerproblem in den nächsten 200 Jahren nicht gelöst werden. Vielleicht lag das auch daran, daß es zu der Klasse der schwierigsten Informatikprobleme gehört und deshalb nach dem irischen Mathematiker R. W. Hamilton (1805-1865) als Hamilton-Wege-Problem bezeichnet wird. Allgemein gilt für Hamiltonwege, daß es nur Algorithmen gibt, deren Berechnungslaufzeit exponentiell mit der Anzahl der zu besuchenden Knoten - hier: Felder - wächst. Das Springerproblem ist nun aber ein Spezialfall, und daher stellt sich die Frage, ob es nicht doch einen effizienteren Algorithmus gibt. Die Verfahren, die im Nachfolgenden genannt werden, werden auch durch dieses Programm anschaulich erklärt. Zudem sei auf die Programme unten bei den Links verwiesen. BACKTRACKING Der Standardalgorithmus für die Lösung solcher Probleme ist das sogenannte Backtracking. Die Idee hierbei ist, die Figur solange zu setzen, bis entweder die Lösung gefunden wurde, oder man nicht mehr weitersetzen kann. In diesem Fall nimmt man einen Zug zurück und versucht eine Lösung über einen Alternativweg zu finden. Das Verfahren findet immer einer Lösung - wenn es sie denn gibt. Zu beachten ist dabei nur ein kleiner Schönheitsfehler: Es dauert, nicht Jahre, sondern Jahrhunderte. Jedenfalls für Bretter mit einer Seitenlänge größer als zehn.

Feldgröße	5x5	6x6	7x7	8x8	9x9	10x10
Laufzeit (in Sek)	21	609	38.954	Tage	Monate	Jahre

Zur Implementierung siehe Prog.Pas. OPTIMIERUNG Weltstadt Wermelskirchen, im Jahre 1989. Hier regnet es 360 Tage im Jahr, an fünf weiteren fällt Schnee. Da hat man genug Zeit, solche Probleme zu lösen ... Nachdenklich blickte Tanja zu mir, ich zu Hussein und der auf das fast leere Schachbrett. "Das müßte zu lösen sein!" rief die Dame in der Runde. "Ja, nur wie?" fragten wir uns und dachten ein wenig nach. Um genau zu sein, wir dachten knapp zweieinhalb Jahre über das Problem nach, das Euler in so kurzer Zeit ersonnen hatte. Zuerst kamen wir auf die Idee, jene Fälle zu ermitteln, in denen der Springer völlig sinnlos auf dem Brett herumhüpft, obwohl keine Lösung mehr gefunden werden kann. Dieses ist beispielsweise dann der Fall, wenn ein Feld oder eine Gruppe von Feldern nicht mehr erreichbar ist (vgl. Abb. 3 und 4). Abb. 3: Lücke Abb. 4: Das gekennzeichnete Feld ist nicht mehr erreichbar Ob ein Feld noch erreicht werden kann, läßt sich anhand der Anzahl der noch freien Nachfolgefelder jedes Feldes sagen: Wenn diese gleich 0 ist, kann keine Lösung gefunden werden. Etwas schwieriger wird es, wenn zwei oder Feldern zwar untereinander verbunden sind, aber zu ihnen kein Weg mehr gefunden werden kann. Dann verwenden wir die sogenannnte Breitensuche. Zur Wiederholung: Die Breitensuche funktioniert mit zwei Beuteln: 1. Beutel 1 ist leer. (In Beutel 1 werden all die Felder geworfen, die mit dem Feld, auf dem der Springer gerade steht (aktuelles Feld), verbunden sind). 2. Beutel 2 ist leer. 3. Die von dem aktuellen Feld aus erreichbaren und freien Felder werden in Beutel 1 geworfen, das aktuelle Feld selbst kommt in Beutel 2. 4. Solange Beutel 1 nicht leer ist, wiederhole folgende drei Schritte: 4.1 Nimm ein Feld aus Beutel 1. 4.2 Werfe die Nachfolger dieses Feldes, sofern sie a) frei und b) noch nicht in Beutel 1 oder Beutel 2 sind, in Beutel 1. 4.3 Werfe danach das Feld in Beutel 2. 5. Zähle nun die Felder in Beutel 2 und vergleiche sie mit der Anzahl der noch freie Felder. Sind die beiden Zahlen nicht gleich, so existiert ein Feld oder mehrere Felder, die nicht mehr erreicht werden können. Die Suche kann auch dann abgebrochen werden, wenn mehr als ein Feld nur noch über ein anderes Feld aus erreichbar ist (Abb. 5 und 6). Denn dann müssen diese Felder Zielfelder sein, das heißt, wenn man sie erreicht hat, kann man von ihnen aus nirgendwo mehr hinspringen. Eine Lösung mit mehr als einem Endfeld ist aber gar nicht denkbar. In den folgenden Abbildungen symbolisieren die Knoten die noch freien Felder, die Kanten die Sprungmöglichkeit zwischen den freien Feldern. Abb. 5: Drei Endfelder Abb. 6: Die beiden Felder links oben sind Endfelder Zur Implementierung siehe Funktion KeineLuecke in Luecke.Pas. Der Aufruf Erlaubt in der Prozedur SucheWeg muß durch KeineLuecke ersetzt werden. HEURISTIKEN Die Laufzeit wurde zwar erheblich verbessert (8x8 in 5 Sek), und wir dachten schon, daß wir wieder mehr Zeit zum Schachspielen gehabt hätten. Doch dann merkten wir, daß sich grundsätzlich nichts an dem exponentiellen Wachstum des Verfahrens geändert hatte. Die Berechnung eines 10x10-Brett hätte immer noch mehrere Monate gedauert. Wie schon oben beschrieben, kann jeder von uns den Weg auf einem 8x8-Brett innerhalb weniger Minuten finden. Auch für ein 10x10-Brett wird man keine Monate brauchen. Der Mensch geht demnach seiner Intuition folgend einem völlig anderen Ansatz nach. Das Zauberwort heißt Heuristik! Um das zu verdeutlichen, finden Sie bitte selbst einen Weg auf einem 8x8-Brett. Wie Sie vielleicht festgestellt haben, bewerten Sie jeden Zug mehr oder weniger unbewußt. Insgesamt fanden wir eine Reihe von (brauchbaren) Kriterien, nach denen man vorgehen kann. Wenig sinnvoll waren Abstandsregeln (Abstand zum Rand, zum Zielfeld). Im Gegensatz dazu waren diejenigen Verfahren sehr schnell, die versuchten, nacheinander einzelne Gebiete zu füllen. Die jedoch mit Abstand beste Methode war auch die einfachste, die wir über folgende Überlegung entwickelten: Wenn der Springer auf einem beliebigen Feld steht, kann es nicht egal sein, auf welches der nachfolgenden Felder er springt. Es ist sinnvoll, das Feld auszusuchen, das schlecht erreichbar ist. Denn nimmt man nicht dieses Feld, so kann der Springer mit zunehmender Besetzung des Brettes immer schlechter einen Weg dorthin finden. Was heißt nun aber "schlecht erreichbar"? Es ist naheliegend, die Anzahl der Nachfolgefelder als einen Maßstab heranzuziehen. Damit war eine Regel gefunden: Man muß immer nur auf das Feld springen, das die wenigsten Nachfolgefelder hat. Die Berechnung einen 10x10-Brettes dauerte damit noch nicht einmal eine Sekunde, ein 80x80-Brett etwa drei Sekunden. Während von daußen leichter Regen gegen die Fenster prasselte, waren wir froh, dieses Verfahren entwickelt zu haben. Jedoch waren wir nicht die ersten, die auf diese Idee kamen. Bereits im Jahre 1823 veröffentlichte H. C. Warnsdorf diese Regel, womit wir wieder sehen, daß dieses Problem doch schon in so manchem Mathematikerhirn steckte. Zur Implementierung siehe Funktion MinGefunden in Warnsdorf.Pas. Der Aufruf Erlaubt in der Prozedur SucheWeg muß durch MinGefunden ersetzt werden. ERWEITERUNG DER WARNSDORFREGEL Als ein überaus glücklicher Umstand erwies sich, daß wir nichts von der Veröffentlichung von Warnsdorf wußten, denn wir forschten munter weiter. Warnsdorf berücksichtigte nämlich nicht den Fall, daß zwei Felder gleich bewertet werden. In diesem Fall gibt es verschiedene Möglichkeiten, ein Feld auszusuchen, von denen wir aber nur zwei näher untersuchten: Die erste Möglichkeit ist, daß die Nachfolgefelder der Nachfolgefelder gezählt werden. In mindestens einem Fall konnten wir aber feststellen, daß genau auf das Feld gezogen werden muß, das mehr Nachfolgefelder besaß. Die zweite Möglichkeit ist wesentlich einfacher: Wir haben eine Zugliste berechnet, in der eine interne Reihenfolge der Felder steht. So muß beispielsweise, wenn zwei Felder gleich bewertet werden, zuerst auf das Feld, das links oben liegt, gezogen werden. Im Grunde ein sehr merkwürdiges Verhalten, das wir nicht näher untersucht haben. Ungeklärt ist auch, bei welchen Listen dieses Phänomen auftritt. Immerhin kann mit dieser Zugliste ein Brett bis n=150 ohne Rücknahme, das heißt in weniger als einer Tausendstel Sekunde berechnet werden. Mit einer kleinen Erweiterung konnten wir auch einen Weg berechnen, von dessen Ziel aus wieder das Startfeld erreichbar war (sog. Start-Zielweg oder Rundweg). Dabei mußte jedoch beachtet werden, daß bei ungerader Feldanzahl nur auf der Farbe gestartet werden darf, die mehr Felder deckt. Diese Farbe ist natürlich auch Zielfarbe. Bei gerader Feldanzahl müssen Start- und Zielfeld eine unterschiedliche Färbung besitzen (sog. Farbbedingung). Der Grund hierfür ist einfach: Die Farbe des Feldes wechselt bei jedem Zug (vgl. oben Abb. 1). Wir waren richtig stolz auf unsere gelösten 150x150-Bretter, bis, ja, bis irgendwann jemand auf die Idee kam, auch größere Bretter berechnen zu müssen. Und damit meinen wir richtig große. So groß, daß man damit schon einen Beweis aufstellen kann, daß es für jede Größe mindestens einen Weg gibt. DIVIDE ET IMPERA! Während noch immer herannahenden Wolken den Himmel über Wermelskirchen verdeckten, rief einer aus der Gruppe: "Machen wir es doch wie die Römer!" Ja! Nur - wie machten es die Römer? Anstatt ins sonnige Italien zu fahren, dachten wir wieder nach und erinnerten uns an lang zurückliegende Lateinstunden: Divide et impera! Teile und herrsche! Wir mußten die großen Felder in viele kleine zerlegen. Also holten wir eine Säge und werkelten munter drauflos. Natürlich war es eine virtuelle Säge. Und endlich packte jemand an, der wußte, wie man eine Säge halten muß: Prof. Dr. Ingo Wegener von der Uni Dortmund. Die sägende Idee war folgende: Von einem beliebigen Brett läßt sich ein Streifen der Breite 5 abschneiden. Die 5x5-Bretter lassen sich so lösen, daß man in das nächste 5x5-Brett springen kann. Übrig bleiben dann nur L-förmige Bretter und ein Brett der Größe 6x6 bis 9x9, von denen man aber auch zeigen kann, daß es hierfür eine Lösung gibt. Man kann nämlich nacheinander die Bretter von außen nach innen und damit das gesamte Brett füllen. Abb. 7: Beispiel für das L-Verfahren Damit läßt sich beweisen, daß es für beliebige nxn-Bretter eine Lösung gibt. Gilt das denn auch eine für beliebige nxm-Bretter mit beliebigem Start- und Zielfeld? Grundlage für die Lösung ist folgende Überlegung: Jede natürliche Zahl, die großer ist als 17, läßt sich in die Zahlen 6, 7 und 8 zerlegen. Mit anderen Worten: Wir zerlegen jedes beliebig große Brett in Bretter der Größen 6x6, 6x7, 6x8, 7x7, 7x8 und 8x8. Diese kleinen Bretter können nun mit den oben genannten Verfahren recht flott berechnet werden. Das einzige größere Problem war nun nur noch zu zeigen, daß man die Bretter so aneinander legen kann, daß der Springer immer in das nächste Brett hüpfen und nacheinander alle Bretter besuchen kann. Das erste Problem - also, daß Start- und Zielfeld immer so gewählt werden können, daß der Springer von einem Brett in das nächste hüpfen kann, konnten wir durch die oben beschriebenen Algorithmen lösen. Das zweite, also einen Weg durch die Teilbretter zu finden, war etwas komplizierter. Der Weg zu der Lösung führte über eine andere Schachfigur: Den König. Denn im Grunde stellten die kleinen Bretter nur Felder eines großen Brettes dar, die nacheinander mit den Zugmöglichkeiten des Königs besucht werden müssen. Der Weg des Königs ist nun aber trivial, so daß wir uns mit Riesenschritten dem Beweis genähert hatten, daß es für jedes beliebig große Brett eine Lösung gab. Eine Leserin schrieb dazu, daß es bei ihr nicht ansatzweise so viel regnen würde wie in Wermelskirchen und daß sie deshalb nicht eine Ewigkeit Zeit hätte, sich selbst diesen "trivialen" Beweis auszudenken. Gut, überredet. Also hier die Idee: Man teilt das Brett in 9 Bereiche. Es gibt nun insgesamt 9 Fälle, die unterschieden werden müßen (die anderen kann man durch Drehen und Spiegeln herleiten). Jeder Bereich kann gelöst werden; s und z bezeichnen das Teilbrett in dem das Start- bzw. Zielfeld liegt: (Drücken Sie auf den jeweiligen Fall, um sich die Grafik im Normalformat anzusehen.) Alle Fälle sind lösbar, also läßt sich für den König immer eine Lösung finden. Nebenbei sprang so noch ein Verfahren dabei heraus, das erlaubt, z.B. ein 100.000x100.000 oder ein 100.000.000x123.456.789-Brett innerhalb einer Sekunde zu berechnen - vorausgesetzt, sie haben einen langsamen Rechner. Nebenbei bemerkt, kann es - da das Verfahren parallelisierbar ist - keinen schnelleren Algorithmus als unseren für eine Lösung geben. Den Beweis finde ich sehr schön, möchte hier aber auf die mathematischen Feinheiten verzichten. Abb. 8: Beispiel für den Königsalgorithmus Und kaum hatten wir es gelöst, da brachen die Wolken über Wermelskirchen entzwei, und die ersten Strahlen der Sonne berührten die Erde. Ok, das ist natürlich ein Märchen; nicht ohne Grund hat Wermelskirchen die größte Trinkwassertalsperre der Welt. ENDE GUT, ALLES GUT Das Springerproblem war damit vollständig gelöst worden. Oder doch nicht? Natürlich, es gab eine ganze Reihe von Spezialfällen. Aber diese Fälle waren sehr begrenzt und ließen sich mit einem PC innerhalb von Stunden berechnen. Bisher ist aber noch nicht gelöst, wie viele Wege überhaupt bei einem beliebig großen Brett existieren. Die Anzahl der Königswege wächst exponentiell, was natürlich auch bedeutet, daß die Anzahl der Springerwege exponentiell wächst. Eine genauere Abschätzung ist aber bis heute nicht bekannt. Abschließend ist zu sagen, daß wir es nur als Gruppe schaffen konnten, denn erst die Summe aller Ideen hatte insgesamt den "krönenden" Beweis erbracht. Abb. 9: Gruppenbild mit Dame: Tanja Hindrichs, Hussein Morsy und Axel Conrad Das Springerproblem war damit vollständig gelöst worden. Oder doch nicht? Man lernt ja nie aus. 1998 kam jemand auf die Idee, das Problem - was liegt näher - auch für den 3- und n-dimensionalen Raum zu lösen. Die Lösung von Diana Schmied und mir finden Sie hier. DOWNLOAD Hier können Sie sich noch ein Programm, das alles genauer erklärt, herunterladen. LITERATURVERZEICHNIS W. Ahrens (1979): Mathematische Spiele, Wiss. Buchgesellschaft, Kapitel 7. L. Euler (1766): Memories de Berlin 1759 M.R. Gary & D.B. Johnson (1979): Computers and intractability: A guide to the theory of NP-completeness; H. W. Freeman M. Kraichik (1966): Mathematical recreations, chapter 11, The problem of the Knight, Allen and Unwin, London P.M. Roget (1840): Philosophical Magazine 3, Vol XVI, S. 305 B.R. Stonebridge (1986): The Knight's Tour of a Chessboard; Mathematical Spectrum 86/87 No. 3 P. 83f; mit Anmerkung von Engelhaupt in Mathematical Spectrum 88/89 No. 1 P. 24 Vondermode (1771): L'histoire de l'Academie des sciences, S. 566ff H. C. Warnsdorf (1823): Des Rösselssprung einfachste und allgemeinste Lösung, Schmalkanden LINKS Zahlreiche Links (international) Unfangreiche Seiten von Stefan Behnel in englisch oder deutsch Programm von Rico Sonntag Programm von Mathias Retzlaff, Stefan Roehrich, Daniel Heck und Hendrik Dahlkamp Programm von js Seite von Prof. Dr. Edwin Schicker, Fachhochschule Regensburg Programm von Winfried Schönfeld (Überarbeitung des Programmes aus der c't 1992 Heft 3 S. 180ff. Facharbeit von Steffen Forkmann Seite von Jürgen Geßwein Applet von Martin Klöckner und Daniel Höpfl Zahlreiche Schachaufgaben von Martin Wohlgemuth Springerseite der Landrat-Lucas-Schule, Leverkusen Hompage von Jugend-forscht Hinweis: Axel Conrad ist nicht verantwortlich für die Inhalte externer Internetseiten. P.S.: Sie waren Besucher Nummer in diesem Monat. Diese Seite wurde im Dezember 1999 anläßlich eines Vortrages an der HTW-Zittau/Görlitz bei Prof. Dr. Christian Wagenknecht überarbeitet. Der Autor, Axel Conrad (e-mail: ac@axel-conrad.de) hat schon einige Vorträge an Universitäten und Schulen über das Thema gehalten und freut sich immer über weitere Einladungen.

---

(c) Axel Conrad (ac@axel-conrad.de) Zu meiner Homepage.