Dr. Andreas Borchert Abteilung Angewandte Informationsverarbeitung 30.06.2005
Norbert Heidenbluth Blatt 10






Allgemeine Informatik II für Mathematiker/Wirtschaftsmathematiker
(SS 2005)


Abgabetermin: 07. Juli 2005

Aufgabe 14: Krötenwanderung (10 Punkte)

Nachdem wir im letzten Übungsblatt kräftig Hauptspeicher ver(sch)wendet haben, gönnen wir uns in diesem Blatt nun mal eine Aufgabe, in der wir die CPU so richtig ausreizen können.

Gegeben sei das Spiel ``Toads and Frogs Puzzle in 2D'', das Sie beispielsweise auf http://www.cut-the-knot.org/SimpleGames/FrogsAndToads2d.shtml finden und spielen können.

Bei diesem Spiel ist ein Spielbrett von $n \times n$ Feldern gegeben, wobei $n$ eine ungerade natürliche Zahl ist. Das mittlere Feld des Spielbretts ist leer, in den $\frac{n-1}{2}$ linken Spalten sitzt auf jedem Feld genau ein Frosch, ebenso sitzt in den $\frac{n-1}{2}$ rechten Spalten auf jedem Feld genau eine Kröte. Die ersten $\frac{n-1}{2}$ Zeilen der mittleren Spalte sind durch je einen Frosch, die untersten $\frac{n-1}{2}$ Zeilen der mittleren Spalte durch genau eine Kröte besetzt. Somit befinden sich von beiden Tieren jeweils $\frac{n^2-1}{2}$ auf dem Spielfeld.

Ziel des Spiels ist es nun, einen Zustand zu erreichen, in dem die Anordnung der Tiere genau herumgedreht ist, das heißt: dort, wo zu Beginn Kröten sitzen, befinden sich dann Frösche und umgekehrt.

Um diesen Zustand zu erreichen gelten folgende Spielregeln:

• Frösche dürfen nur nach rechts oder nach unten ziehen.
• Kröten dürfen nur nach links oder nach oben ziehen.
• Ein Tier kann in einem Zug über (genau) ein Tier der anderen Gattung springen.
• Die letztgenannten vier Punkte gelten natürlich nur dann, wenn das Zielfeld frei ist.

Dies führt nun zur folgenden

Aufgabe:

Schreiben Sie ein Oberon-Programm, das mit Hilfe von Backtracking eine Lösung des Spiels ermittelt und ausgibt!

Hinweise:

• Achtung: Auch wenn es auf den ersten Blick trivial erscheint, so lassen Sie Ihr Programm bitte ausschließlich für den Fall eines $3\times3$-Spielfeldes laufen (sofern Sie noch vor Ende Ihres Studiums an einem Ergebnis interessiert sind).

• Es geht bei dieser Aufgabe zunächst nur um das Prinzip des Backtrackings, nicht unmittelbar um die effizienteste Implementierung. Insofern kann es schon bei einer $5\times5$-Matrix passieren, daß Sie in überschaubarer Zeit kein Ergebnis geliefert bekommen.
  Bei einem $3\times3$-Spielfeld ist der Rechenaufwand jedoch noch überschaubar.

• Mit anderen Worten: Sie dürfen für diese Aufgabe nach der sog. Brute-Force-Methode vorgehen, d.h. Sie können wirklich alle gültigen Züge betrachten lassen, auch wenn bereits ein Zustand erreicht ist, der zu keiner Lösung mehr führen kann.

• Zu Beginn der Bearbeitung dieser Aufgabe sollten Sie sich zunächst Gedanken über eine sinnvolle Datenstruktur für dieses Problem machen.

• Anregungen dafür, wie man das Spielfeld darstellen kann, können Sie zum Beispiel der Übungsaufgabe von Blatt 11 des letzten Semesters (WS 2004/05) entnehmen$\ldots$

• $\ldots$ und die Restaurant-Aufgabe von Blatt 2 aus diesem Semester könnte beim Entwickeln der Programmlogik helfen.

Viel Erfolg!