Das Frosch-Spiel (mit xturtle)

Download: das Programm frogs.py

Spielregel:

Auf einem Feld stehen in einer Reihe N Figuren einer Farbe, N Figuren der zweiten Farbe und zwischen ihnen ein Leerfeld.

Die linken Figuren (grün) können nur nach rechts ziehen, die rechten (rot) nur nach links.

Jede Figur kann entweder auf das leere Nachbarfeld ziehen, oder über eine Figur der anderen Farbe auf das Leerfeld springen.

Ziel: alle linken (grünen) Figuren stehen rechts, alle rechten (roten) links

Beispiele

1.) im Textmodus

>>> f= FrogPlay(4)
löst das Spiel mit je vier Spielfiguren und zeigt die Lösungsschritte an

2.) mit Grafik

>>> f = Frog_GUI(3)
erstellt eine Grafik, in der man das Spiel versuchen kann.
Die Turtles sind anclickbar und bewegen sich nach Vorschrift.

>>> f.animate()
zeigt die Lösung animiert vor

Mathematik

Wie viele Züge braucht man (mindestens?) zur Lösung?
N Figuren müssen sich um (N+1) Felder bewegen, das macht insgesamt N mal N+1, also 2*(N²+N) Bewegungen. Dabei muss jede Figur jedoch N Figuren der anderen Farbe überspringen, was sie jeweils um 2 Felder voranbringt, das spart also eine je Bewegung ein. Insgesamt N Ersparnisse pro Figur das macht gesamt N².
Und somit verbleiben 2*(N²+N)-N² = N²+2N = (N+1)²-1 Züge