Betrachten wir zunächst nur die vertikalen Bewegungen. Bei einem 5x5-Brett gibt es insgesamt genau sechs Bewegungsschritte der Frösche von oben nach unten und analog zu dazu genau sechs Bewegungsschritte der Kröten von unten nach oben. Die Zahl der vertikalen Züge selbst kann unterschiedlich sein, da innerhalb eines Zuges ein oder bei einem Sprung auch zwei Schritte zurückgelegt werden können. Im allgemeinen Fall gibt es
| n2 - 1 |
| 4 |
vertikale Schritte der Frösche (und genauso viele auch für die Kröten in die andere Richtung).
Ziel der vertikalen Schritte muß es sein, in jeder Zeile die richtige Zahl von Fröschen und Kröten zu transportieren. Ziel der horizontalen Schritte ist es dann, die Frösche und Kröten innerhalb einer Zeile korrekt zu sortieren. Eine solche Sortierung innerhalb einer Zeile ist jedoch nur möglich, wenn eine Zelle dort frei ist. Dabei ist zu berücksichtigen, daß nur vertikale Züge eine freie Zelle in eine Zeile bringen, die noch zu sortieren ist.
Daraus läßt sich folgende wichtige Folgerung gewinnen: Sobald eine Zeile die beiden Maxima der Summen aus dem Tip 1 erreicht hat, kann sie nicht mehr umsortiert werden. Entweder sind dann alle Frösche und Kröten auf ihren Endpositionen oder wir haben eine Sackgasse. Daraus folgt, daß die Sortierung erfolgen muß, bevor der letzte Frosch oder die letzte Kröte in die Zeile kommt.
Daraus ergibt sich eine gewisse Reihenfolge, in der die einzelnen Zeilen fertiggestellt werden. Es ist offensichtlich, daß diese Reihenfolge nicht beliebig ist. So muß die mittlere Zeile beispielsweise ganz zum Schluß fertiggestellt werden, damit dort in der Mitte das freie Feld verbleiben kann.
Es stellt sich heraus, daß die Reihenfolge der Fertigstellung der anderen Zeilen sehr eingeschränkt ist. Wir haben dabei folgende Hypothese:
Zeilen können nur von außen nach innen fertiggestellt werden. Dies aber in beliebigen Kombinationen. Zuletzt wird die mittlere Zeile fertiggestellt.
Das bedeutet, daß zunächst die oberste oder die unterste Zeile fertiggestellt werden muß. Dann von dem verbliebenen Zeilen die oberste oder unterste usw. Sei m = (n - 1)/2, dann gibt es insgesamt
| (2m)! |
| (m!)2 |
Möglichkeiten, in welcher Reihenfolge die einzelnen Zeilen fertiggestellt werden können. Im Fall von 5x5 sind dies 6 Varianten, bei 6x6 werden es dann 20 Varianten und bei 9x9 70 Varianten. Weitere Werte finden sich bei der Folge Sloane A000984.
Wir haben die Hypothese mit einem separaten Backtracking-Programm untersucht, das nur die vertikalen Züge berücksichtigt, und fanden sie bestätigt für alle Brettgrößen bis 9x9. Da wir für letzteres bereits 4.032.000 verschiedene Lösungsmöglichkeiten bei der Reihenfolge von vertikalen Zügen gefunden haben, nahmen wir Abstand von größeren Brettern.
Aber im Rahmen dieses Übungsblattes (das sich auf 5x5 und möglicherweise 7x7 bezieht), können Sie diese Hypothese als gegeben annehmen.
afb - 07/2005