Loch über Loch, mit SMT-Solver gelöst

Dieses Geduldspiel besteht aus 10 Brettchen der Größe 1x5. In jedem der 1x1-Quadrate kann sich ein Loch befinden, insgesamt enthalten die Brettchen 26 Löcher. 

Die Brettchen sollen in zwei Lagen (einmal für hoch und einmal für quer) übereinandergelegt werden, so dass jeweils zwei Löcher übereinanderliegen. Beim folgenden Bild hat es nicht ganz geklappt.

Schwierigkeit: Höchstens mittelschwer. Man kommt durch systematisches Probieren zum Ziel, und es gibt mehr als eine Lösung.

Ähnliche Geduldspiele: Bei Golf Putting Green gibt es zusätzlich halbe "Golfbälle", die in die Löcher passen.

Design und Herstellung:  HolzArt Robby Ellwitz

Shopping: Nicht lieferbar.

Das Geduldspiel automatisch lösen mit Python und Z3

Das folgende Python-Programm benutzt den SMT-Solver Z3 und wurde mit Hilfe von Gemini geschrieben. Dabei wurden die Unterschiede zu Golf Putting Green beschrieben und ein vorher für Golf Putting Green erzeugtes Programm wurde passend abgeändert.

Das Programm findet insgesamt 8 verschiedene Lösungen. Die Ausgabe der Lösungen (ein Beispiel unten) wurde bewusst recht abstrakt gehalten, so dass ein flüchtiger erster Blick darauf nicht ungewollt eine Lösung verrät.

Hier ist das Python-Programm zum Download:

📥 Solver herunterladen

Es folgt eine der gefundenen Lösungen als ASCII-Grafik: Die schwarzen Blöcke entsprechen den Löchern.

 

 █  ░  █  █  █ 

 ░  ░  ░  █  ░ 

 █  ░  ░  █  █ 

 ░  ░  █  ░  █ 

 █  █  ░  ░  ░ 

2x2x2 Zauberwürfel als Tiger

Von der chinesischen Firma YuXin gibt es eine ganze Serie von 2x2x2-Zauberwürfeln in der Form von Cartoon-Tieren. Diese Tiere gibt es in verschiedenen Größen, der hier vorgestellte Tiger hat die stattliche Größe von 13cm.

Schwierigkeit: Bei Drehungen verändert der Tiger seine Form, aber die acht Teile sind deutlich zu unterscheiden, so dass man leicht den Überblick behält, welches Teil in welcher Orientierung man vor sich hat. Die Schwierigkeit ist damit identisch zum 2x2x2-Zauberwürfel. 

Mechanisch sind  ist die ganze Serie für solche "Spaß-Würfel" überraschend gut und leichtgängig konstruiert.

Ähnliche Geduldspiele: In der Serie der YuXin Animal Twisty Puzzles gibt es noch mehr Tiere, beispielsweise Panda, Hase, Schlange, Pinguin und Maus.

Hersteller:  YuXin
Erscheinungsjahr: ca. 2019

Google: YuXin 2x2 Animal Twisty Puzzle
Shopping: Lieferbar, Preis ca. 10€

Cast Medallion

Kategorie: Labyrinthe

Cast Medallion ist eines dieser Puzzles, bei denen sich eine edle Optik mit einer gnadenlos vertrackten, mathematischen Pfadsuche paart. Es präsentiert sich in der Form einer antiken Münze oder eines schweren, edlen Schmuckstücks. Auf beiden Seiten trägt ein ein goldenes bzw. ein silbernes Labyrinth.

Aus der Sicht des Puzzlers handelt es sich um zwei verschiedene, unabhängig voneinander bewegliche Labyrinth-Scheiben. Der innen liegende Rahmen, welcher auch aus zwei Teilen besteht, hat auf jeder Seite zwei Stifte, die durch die Labyrinthe bewegt werden müssen. Dazu kann man nicht nur die Scheiben drehen, sondern auch noch den Rahmen schrittweise immer weiter auseinanderziehen.

Hier das zerlegte Medallion:

Schwierigkeit: Hanayama stuft das Cast Medallion auf einem sehr anspruchsvollen Level 5 von 6 (Expert) ein. Die Schwierigkeit ist verbunden mit der Frustrationstoleranz: Man hat oft das Gefühl, fast am Ziel zu sein, nur um dann festzustellen, dass man den falschen Abzweig genommen hat und komplett von vorne beginnen muss. Der Zusammenbau ist, wie so oft bei diesen Modellen, fast noch schwieriger als die Demontage.

Cast Medallion ist mit einen Durchmesser von ca. 7cm etwas größer als andere Cast Puzzles und besitzt auch eine entsprechend größere Verpackung.

Design:  Oskar van Deventer
Hersteller:  Hanayama
Erscheinungsjahr: 2011

Google: Hanayama Cast Medallion
Shopping: Lieferbar, Preis ca. 25€

Komplizierte Schiebespiele 3x4 mit zwei äußeren Zinnen

Kategorie: Schiebepuzzles mit Polyominos (systematisch)

Wir untersuchen die Schiebespiele mit Zinnen auf dem 3x4-Rechteck, hier mit zwei äußeren Zinnen. 

Der Rahmen des Spiels enthält 14 Felder. Nimmt man die fehlenden Randfelder in der oberen Reihe hinzu, wird das Feld größer. Für dieses vollständige 4x4-Quadrat wurden die interessantesten Schiebespiele 4x4 bereits vorgestellt, hier wird es eher einfacher, allerdings nicht viel. 

Schwierigkeit: Ganz einfach sind diese Aufgaben nicht mehr, die schwierigsten benötigen mehr als 100 Züge für die Lösung.

Wie immer konzentrieren wir uns auf optisch oder konzeptionell interessante Spiele. Die Bilder zeigen jeweils die Start- und Zielkonfiguration eines Schiebespiels, darüber steht die Anzahl der benötigten Züge (jeweils ein Stein wird um eine Position bewegt). Die Beschreibung dazu erklärt den Typ des Spiels, ist aber keine vollständige Beschreibung.

Aufgabe 1 - Schwierigste Aufgabe; Wandern: Dies ist die Aufgabe mit den meisten Zügen. Im Wesentlichen besteht die Aufgabe darin, einen senkrechten Dominostein an dem waagerechten Dominostein vorbeizubringen.

Aufgabe 2 - Spiegeln: Eine sehr schöne und schwierige Aufgabe mit gespiegelten Positionen.

Aufgabe 3 - Sortieren: Die schwierigste Aufgabe mit dem L-Tromino.

Aufgabe 4 - Spiegeln: Die schwierigste Aufgabe mit zwei L-Trominos.

Aufgabe 5 - Sortieren: Hier müssen alle Steine bis auf einen an den zwei senkrechten Dominos vorbei.

Aufgabe 6 - Spiegeln: Wieder eine sehr schöne Spiegelung. Diesmal mit nur zwei Leerfeldern.

Aufgabe 7 - Umsortieren: Die drei Elementarquadrate müssen nach oben.

 

Aufgabe 8 - Spiegeln: Die schwierigste Aufgabe mit dem liegenden I der Länge 3.

Aufgabe 9 - Spiegeln: Die schwierigste Aufgabe mit dem 2x2-Quadrat.

Aufgabe 10 - Sortieren: Die schwierigste Aufgabe mit dem L-Tetromino. Zwei Elementarquadrate müssen nach rechts vorbei am stehenden Domino..

Aufgabe 11 - Spiegeln: Die schwierigste Aufgabe mit dem L-Tetromino. Optisch sehr schön.

Aufgabe 12 - Umsortieren: Die schwierigste Aufgabe mit dem stehenden I der Länge 3. Dieser Stein kann sich kaum bewegen, das macht die Aufgabe recht einfach.

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.

Programmieren von Puzzlesolvern mit KI in Python

Programmieren ist für uns Menschen aufwändig und deshalb werden Lösungsprogramme für Geduldspiele eigentlich nur geschrieben, wenn sie sich hinterher auf möglichst viele Puzzles anwenden lassen. Die Situation ändert sich, wenn wir eine KI zur Verfügung haben, die uns das Programm schreibt. Wenn wir Glück haben, geht das blitzschnell und ganz einfach. Wir beschreiben hier das aktuelle Vorgehen bei Gemini im Sommer 2026. Dies reduziert die Zeit zur Erstellung eines Lösungsprogramms von vielen Stunden beim traditionellen Programmieren auf wenige Minuten mit Hilfe der KI.

Im günstigsten Fall kennt Gemini das Puzzle und wir müssen nicht viel erklären. Als Aufforderung reicht etwa folgender Prompt: Schreibe ein Python-Programm, welches die 12 Pentominos in ein 6x10-Rechteck und die Lösung als ASCII-Grafik zeichnet. 

Binnen weniger Sekunden erhält man ein fertiges Python-Programm. Bei Bedarf kann man das Programm entweder selbst ändern oder Gemini um eine Änderung bitten. Das genaue Vorgehen ist im Post 12 Pentominos in ein 6x10 noch einmal ausführlich beschrieben.

Etwas mehr Erklärung ist bei Puzzles nötig, die Gemini nicht kennt. Aber auch hier kann auf globales Wissen wie Edge Matching Puzzle oder Polyominos zurückgreifen. In der Regel sind mehrere Iterationsschritte nötig, bis das Programm zur Zufriedenheit läuft.

Solange man mit dem erzeugten Programm nicht ganz zufrieden ist, kann man Verbesserungsvorschläge machen. Falls Gemini diese für sinnvoll hält, werden Sie für den Vorschlag gelobt und der Vorschlag wird im Programm realisiert. Beispiele sind:

1. Stelle sicher, dass Gemini das Puzzle richtig interpretiert. Manchmal gibt es Missverständnisse.
2. Sehr nützlich ist, wenn man das entsprechende Puzzle vor sich hat. In vielen Fällen muss die konkrete Form der Puzzleteile noch eingefügt werden.
3. Wenn man eine Lösung kennt, kann man einfach überprüfen, ob diese Lösung auch gefunden wird.
4. Z3 sucht als SMT-Solver immer nur nach einer Lösung. Sie können auch nach mehreren oder allen Lösungen suchen lassen. Achtung, das können sehr viele sein. Vielleicht wollen Sie nur deren Anzahl wissen.
5. Unter den Lösungen finden sich manchmal Dubletten. Es sollen nur wirklich verschiedene Lösungen berücksichtigt werden. Hier ist es ratsam zu überprüfen, ob wirklich alle Dubletten entfernt werden. Auf Nachfrage macht Gemini auch Vorschläge für Änderungen am Algorithmus.
6. Die Ausgabe der Lösungen sollte so geändert werden, dass sie für uns Menschen optisch ansprechend sind. 

Welche Puzzles lassen sich auf diese Art mit einem Programm von Gemini lösen?

Nützlich (aber nicht unbedingt notwendig) sind die folgenden Eigenschaften:

• Das Puzzle besteht aus einfachen geometrischen Objekten (z.B. Rechtecke, Quader, ...)
• Diese Objekte sollen auf einfache Art zusammengefügt werden (z.B. passende Kanten aneinanderstoßen, auch mit zusätzlichen Bedingungen wie passenden Bildern).
• Die Komplexität des Puzzles sollte nicht zu hoch sein. Also beispielsweise von Menschen lösbar oder auch etwas komplizierter. (Puzzles mit Hexominos sind maschinell gut lösbar, bei Oktominos ist es schnell zu komplex)

3x3 Kugellabyrinth

Dieses schon ältere Kugellabyrinth besteht aus 9 Kästchen, angeordnet als 3x3. Darin befinden sich 8 Stahlkugeln vielleicht waren es irgendwann einmal 9). Manche der benachbarten Kästchen haben kleine Durchgänge, durch welche die Kugeln ins Nachbarkästchen gelangen können.

Die Aufgabe besteht wahrscheinlich darin, die Kugeln in verschiedenen Kästchen unterzubringen, und nicht mehrere in einem Kästchen. 

Schwierigkeit: Dies ist ein reines Geschicklichkeitsspiel, Nachdenken ist kaum gefordert. Für Kinder gut geeignet. 

Design:  unbekannt

Shopping: Nicht lieferbar.

Unwiderstehlich-Puzzle: Kleines einfarbiges Quadrat

Für eine allgemeine Beschreibung der Unwiderstehlich-Puzzles gibt es einen längeren Post. Deshalb hier nur die Details zu diesem Geduldspiel. Der Rahmen des Geduldspiels hat die Form eines Quadrates mit einer Seitenlänge von etwa 9cm. Und ca. 45 Teile aus naturbelassenem Holz sollen dort eingeordnet werden.  

Schwierigkeit: Einfach wegen der relativ kleinen Anzahl von Puzzleteilen. Gut geeignet für Anfänger, um für größere Rahmen zu üben.

Design:  Puzzle-Werkstatt Unnerstall
Hersteller:  Puzzle-Werkstatt Unnerstall

Google: Unwiderstehlich Puzzle Unnerstall
Shopping: Gebraucht selten lieferbar, Preise ca. 15€.

Aufgaben für Hexominos (Nr. 31-40)

Kategorie: Aufgaben für Polyominos

Hier weitere 10 Aufgaben für die 35 verschiedenen Hexominos, die Rahmen haben rechteckige Form mit einem zentralen rechteckigen Loch und bestehen aus jeweils aus insgesamt 210 Elementarquadraten.

Schwierigkeit: Schwierig, aber für ambitionierte Puzzler sind diese Geduldspiele trotzdem von Hand lösbar. Es gibt jeweils sehr viele verschiedene Lösungen. Hier soll jeweils eine Lösung angegeben werden, da es praktisch unmöglich ist, sich eine solche Lösung schnell einzuprägen. Man wird also automatisch nach einer anderen Lösung suchen.

3D-Druck: Ein Satz Hexominos lässt sich mit 3D-Druck herstellen: Im Post Pentominos und Hexominos in Box finden Sie die Links zur Sammlung zum Blog auf Thingiverse sowie zu Printables.

Lösung mit Computer: Die hier vorgestellten Aufgaben bieten auch für die üblichen Lösungsprogramme keine Schwierigkeiten. PolySolver, mops.exe und Polycube benötigen für die Aufgaben (in den Standard-Einstellungen) maximal einige Sekunden, manchmal auch viel weniger. Die hier gezeigten Lösungen wurden mit mit Polycube Vers. 1.2.1 ermittelt, dazu wurde die Kommandozeile

polycube.exe -V -10 -p -- Eingabedatei > Ausgabedatei

verwendet. 

Die Struktur der Eingabedatei ist einfach, Beispiele gibt es zusammen mit dem Programm bei [1].

In den Aufgaben für Hexominos Nr. 3 und Nr. 24 wurden bereits zwei solche Rechtecke mit Loch der Größe 15x15-3x5 und 33x7-7x3 vorgestellt. Hier mehr solche Rechtecke.

Aufgabe 31: Rechteck 17x13 mit einem Loch der Größe 11x1.

Aufgabe 32: Rechteck 17x15 mit einem Loch der Größe 5x9.

Aufgabe 33: Rechteck 17x15 mit einem Loch der Größe 9x5.

Aufgabe 34: Rechteck 19x15 mit einem Loch der Größe 15x5.

Aufgabe 35: Rechteck 21x11 mit einem Loch der Größe 3x7.

Aufgabe 36: Rechteck 21x11 mit einem Loch der Größe 7x3.

Aufgabe 37: Rechteck 21x13 mit einem Loch der Größe 7x9.

Aufgabe 38: Rechteck 21x13 mit einem Loch der Größe 9x7.

Aufgabe 39: Rechteck 21x15 mit einem Loch der Größe 15x7.

Aufgabe 40: Rechteck 25x11 mit einem Loch der Größe 13x5.

Dael 'O' Ring Easy Yellow

Kategorie: Labyrinthe

Dieses Dael 'O' Ring Puzzle mit dem gelben Ring ist wahrscheinlich das einfachste Puzzle der gesamten Serie der Dael 'O' Ring Puzzles. Diese wurde bereits ausführlich besprochen, hier nur die wichtigen Details für diese Variante mit dem gelben Ring:

Im Inneren des Rings befindet sich ein verstecktes Labyrinth, welches durchlaufen werden muss, um den Ring zu befreien.

Schwierigkeit: Die Schwierigkeit des Geduldspiels hängt von der Schwierigkeit des Labyrinths ab. Der Weg ist vergleichsweise lang, deshalb bleibt wenig Platz für Sackgassen und diese sind meist kurz. Wenn man sich in solch einer Sackgasse wiederfindet, findet man schnell zum Hauptweg zurück.

Design: Cor Vissers, Gert Santman
Hersteller:  Recent Toys
Erscheinungsjahr: ca. 2010

Google: Dael O Ring Puzzle
Shopping: Gebraucht lieferbar.

Bitten Biscuits / Die angebissene Symmetrie

Was macht man mit drei Keksen, in die bereits jemand hineingebissen hat? In der Welt der Geduldspiele isst man sie nicht auf, sondern versucht, eine perfekte Anordnung der drei angebissenen Keksteile zu finden. Bitten Biscuits ist ein charmantes, aber hinterlistiges Symmetrie-Puzzle, das unsere visuelle Erwartungshaltung gnadenlos ausnutzt. Es gibt dieses Geduldspiel in verschiedenen Varianten aus Holz, aus Acryl oder wie hier 3D-gedruckt.

Die Aufgabe besteht darin, die drei Keksteile zu einer symmetrischen Form zusammenzufügen. Dabei müssen alle Teile flach auf dem Tisch liegen und dürfen sich nicht überlappen.

Die abgebissenen Teile der Keksstücken haben als Ränder Stücke von Kreisbögen, und diese haben den gleichen Radius wie die Kekse selbst. Damit passen die drei Keksstücken auf viele verschiedene Arten aneinander und man kann lange nach der Lösung suchen.

Schwierigkeit: Vielleicht sehen Sie die Lösung sozusagen auf den ersten Blick, dann ist alles ganz einfach. Das klappt aber nur bei sehr wenigen Puzzlern. Alle anderen müssen lange suchen und das kann sehr zermürbend sein.

Bitten Biscuits erstmals auf der 34. International Puzzle Party 2014 in London und war das Austauschpuzzle von Tomas Lindén, 

Lösungshinweis: Ein hilfreicher Lösungsalgorithmus besteht darin, die Bissmarken nicht als Fehler zu betrachten, der versteckt werden muss, sondern als aktives Designelement der neuen, symmetrischen Außenkontur. Man muss die Teile so kombinieren, dass die runden Aussparungen auf völlig unerwartete Weise eine neue Geometrie bilden.

 

Design:  Vesa Timonen
Hersteller:  Verschiedene
Erscheinungsjahr: 2014

Google: bitten biscuits puzzle
Shopping: Nicht lieferbar

3D-Druck: Es gibt mehrere fast identische Versionen dieses Geduldspiels. Die dazugehörigen STL-Dateien findet man bei Thingiverse und Printables.