Das verflixte Schildkrötenspiel

Autor: Stefan Moser, Universität Bern

Die Spielanleitung ist denkbar einfach: 9 Kärtchen sollen zu einem 3 x 3 Quadrat zusammengesetzt werden, so dass die in vier Farben gezeichneten Vorder- und Hinterteile der Schildkröten zusammenpassen. Für uns Menschen ist es eine schwierige Aufgabe, eine Lösung zu finden. Noch schwieriger ist es, alle möglichen Lösungen herauszufinden. Mit dem Computer wird dieses Problem typischerweise mit Backtracking gelöst.

Die Idee des Algorithmus ist die folgende: Eine erste Karte wird in das Feld links oben gelegt. Beim Legen jeder weiteren Karte wird überprüft, ob sie passt. Anderfalls wird sie gedreht. Passt die Karte mit allen vier Drehrichtungen nicht, wird die nächste Karte genommen. Falls keine der restlichen Karten passt, wird die bereits liegende Karte weggenommen und durch eine andere ersetzt. Dieses Verfahren wird natürlich, wie bei den vorherigen Problemen, rekursiv durchgeführt, so dass am Schluss alle Möglichkeiten durchprobiert wurden.

Die Programmausführung wird mit Klick auf Run gestartet. In der Titelleiste wird die Anzahl Schritte angezeigt.

Es gibt mehrere Lösungen. Nachdem die erste Lösung vorliegt, pausiert das Programm. Mit Klick auf Run wird die nächste Lösung gesucht.

Programmcode downloaden: TrickyTurtles.zip

Jar-File downloaden: TrickyTurtleJar.zip

Eigenes Turtles-Spiel gestalten

Mit der folgenden Erweiterung kann man das Turtle-Spiel selbst erstellen. Dazu zieht man mit der Maus die Turtlehälften in das Spielfenster. Bei der entstehenden Anordnung kann es sich bereits um eine Lösung handeln. In diesem Fall wird der Computer mit Sicherheit mindestens eine Lösung finden. Gibt es aber noch andere (nicht triviale) Lösungen? (Triviale Lösungen sind 90°-Rotationen einer bestimmten Lösung). Bei einer "wilden" Anordnung wird meist keine Lösung gefunden.

Sind die Karten erstellt, wird mit Klick auf Generate zuerst nach einem Namen für die Kartenbilder gefragt. Nachher wählt man ein Dateiverzeichnis, in dem diese Kartenbilder abgelegt werden. Schliesslich kann man auswählen, ob während der Lösungssuche die Grafik unterdrückt wird (Fast forward wählen). Dadurch werden die Lösungen wesentlich schneller gefunden.

Im Lösungsfenster werden die Karten auf der linken Seite von 0 bis 8 nummeriert. Diese Nummern beziehen sich auf die Lösungsbeschreibung im Textfenster. Z. Bsp. heisst "3 DOWN", dass die Karte Nummer 3 mit der Ziffer nach unten gelegt wird.

Druckt man die Kartenbilder aus, erhält man ein eigenes Kartenspiel, mit man andere Personen herausfordern kann.

Programmcode downloaden: TurtlesGenerator.zip

Jar-File downloaden: TurtleGeneratorJar.zip