Home | email | Rösselsprung

Die Warnsdorff Regel

Anfang des 19. Jh. Wurde eine praktische Methode entwickelt, das Rösselsprung-Problem zu lösen: H.C. Warnsdorff, „Des Rösselsprungs einfachste und allgemeinste Lösung" (Schmalkalden, 1823).

Ziel der Methode ist es, Sackgassen zu vermeiden. Hierzu werden die Felder, die der Springer als nächstes besuchen kann, vor jedem Zug untersucht. Man zählt die Anzahl der Möglichkeiten pro Feld und zieht dann zu dem Feld mit der geringsten Anzahl neuer Zug-Möglichkeiten (Beispiel 1).

Die Warnsdorff Regel ist heuristisch. Theoretische Betrachtet gibt es dagegen Einwände (2), aber bei einem 8*8 Feld arbeitet sie hervorragend.

Das Java Applet auf dieser Seite zeigt die Effizienz der Warnsdorff Regel:

Klick auf ein beliebiges Startfeld (linke Maustaste). Die Anzahl der freien Eingänge der Felder des nächsten erlaubten Zuges wird dann angezeigt. Klick auf die geringste Zahl und fahre so fort, bis das gesamte Feld mit der Springer Reise bedeckt ist. In vielen Fällen werden mehrere gleiche Möglichkeiten angeboten, manchmal ist es angebracht, das Feld mit der geringsten Anzahl nicht zu nehmen, um es als Endfeld einer geschlossenen Tour zu reservieren. Es gibt also eine gewisse Freiheit in der Wahl, aber Felder mit nur einem Eingang müssen sofort besucht werden, da sie sich sonst in Sackgassen verwandeln. Ein solches Feld kann als Endfeld für die gesamte Reise dienen, zwei bedeuten Ärger.
Zurück: Klick mit der rechten Maustaste auf ein schon besuchtes Feld. Die Reise wird dann entsprechend verkürzt, so dass der Zug von diesem Feld aus neu gemacht werden kann.

Versuche zu entdecken, wie einfach es ist, mit Hilfe der Warnsdorff Regel die Springer Reise zu lösen.

1. Beispiele: Nimm ein Eckfeld. Von einem solchen Feld aus kann der Springer nur auf zwei Felder springen. Umgekehrt kann das Eckfeld nur von diesen beiden Feldern aus erreicht werden - das Eckfeld hat also zwei „Eingänge". Wenn ein Springer auf seiner Reise einen dieser Eingänge besucht, ist er gezwungen, das Eckfeld als nächstes zu besuchen. Wenn der Springer dieses nicht macht, hat er einen der beiden freien Eingänge verbraucht und das Feld wird zu einer Sackgasse; das Feld kann zwar später noch besucht werden, es gibt aber keinen Weg mehr, der von ihm fort führt. Im Verlauf einer Springer Reise nimmt die die Zahl der freien Eingänge pro besuchtem Feld ab. Die Warnsdorff Regel dient als Anweisung für den Springer, Felder mit der kleinsten Anzahl von Eingängen zu besuchen, bevor sie zu Sackgassen werden.

2. Die Warnsdorff Regel findet Lösungen, aber nicht alle möglichen Lösungen (man kann Züge machen, die die Regel verletzen und doch eine vollständige Tour bekommen). Die Regel besitzt einen Hauch von Beliebigkeit, da es häufig zu einer Wahl zwischen gleichen Alternativen kommt. Auf wirklichen großen Feldern lässt sich die Regel kaum anwenden. Warnsdorff hatte wohl kaum die Möglichkeit, dies zu erforschen, aber Arnd Roth vom Max-Planck-Institut für Medizinische Forschung veröffentlichte eine entsprechende Untersuchung in "The Problem of the Knight".

3. More about the heuristic nature of Warnsdorff's rule and its performance could be found at Efficiency of Warnsdorff's rule.
(leider nur in Englisch)

Übersetzung: Clemens Heine

01 11 29

Visitors: