12 Pentominos in ein 6x10 mit Gemini programmieren

Hier soll ausführlich beschrieben werden, wie man ein Python-Programm erstellt, um ein Geduldspiel zu lösen. Dieses Beispiel soll als Vorlage dafür dienen, weitere (und auch eigene) Lösungsprogramme zu erstellen. Als Geduldspiel wurde hier das folgende Problem ausgewählt: Packe die 12 Pentominos in einen Rahmen der Größe 6x10. Hier im Blog wurde sie bereits hier und allgemeiner hier besprochen. Aufgaben über Pentominos sind allgemein bekannt und wir können zu recht hoffen, dass Gemini die Pentominos kennt. 

Das folgende Experiment wurde im August 2016 mit Gemini 3.1 Pro durchgeführt. Wir öffnen https://gemini.google.com/app und tippen in die Eingabezeile: 

Schreibe ein Python-Programm, welches die 12 Pentominos in ein 6x10-Rechteck und die Lösung als ASCII-Grafik zeichnet.

Nach kurzer Zeit zum Nachdenken erhalten wir nicht nur ein fertiges Python-Programm, sondern auch etwas Beschreibung dazu. Wenn wir es eilig haben, laden wir sofort das Programm herunter und starten es auf der Kommandozeile. Wir erhalten die folgende Ausgabe: 

Das sieht gut aus und ist tatsächlich eine Lösung für unser Problem. Bevor wir uns das Programm anschauen, lesen wir vielleicht erst einmal die mitgelieferte Beschreibung:

Um die Zellen annähernd quadratisch wirken zu lassen, wird jeder Buchstabe bei der Ausgabe doppelt gedruckt. Außerdem nutzt der Code zur besseren Übersicht ANSI-Farbcodes für das Terminal.

So funktioniert das Programm:

1. Repräsentation: Die zwölf Pentominos sind auf einem Raster durch relative (x,y)-Koordinaten definiert (die Basis-Form).
2. Transformationen (get_orientations): Aus der Basisform berechnet das Programm alle möglichen Drehungen (90°, 180°, 270°) und Spiegelungen. Duplikate werden per Mengensystem (set) aussortiert.
3. Normalisierung (normalize): Dieser Schritt ist entscheidend für die Performance. Jede Variante eines Pentominos wird so verschoben, dass ihr oberster, linkester Block immer genau auf den Koordinaten (0,0) liegt.
4. Tiefensuche / Backtracking (backtrack): Das Programm iteriert von oben links nach unten rechts durch das 6×10-Raster. Findet es ein leeres Feld (.), durchläuft es iterativ alle noch nicht genutzten Bausteine und prüft, ob die Form in das Gitter passt. Passt sie, verbleibt sie an der Position, und die Funktion ruft sich rekursiv für das nächste leere Feld auf.

📥 Solver herunterladen

Das heruntergeladene Programm Pentominos_in_6x10_v10.py kann auf der Kommandozeile gestartet werden mit python Pentominos_in_6x10_v10.py.

Und nun schauen wir uns den Quellcode an. Das Programm besteht aus 136 Zeilen und ist mit vielen Kommentaren (in deutscher Sprache!) versehen. Wir finden noch mehr Informationen. Beispielweise sucht das Programm nach einer geeigneten Reihenfolge der 12 Steine beim Backtracking, was ein wenig an die Nützlichkeit der Pentominos erinnert.