Mehrere gleiche oder ähnliche Figuren aus einem Satz Polyominos legen

Kategorie: Aufgaben für Polyominos

Wir haben schon Hexominos und Heptominos in Kisten gepackt, indem wir mehrere Quadrate gelegt haben und diese übereinander in eine Box packten. Wir hatten 

• Heptominos in einer 8x8-Box, gestapelt in 12 Schichten mit jeweils einem Loch an der gleichen Stelle, sowie
• Pentominos und Hexominos in einer 6x9-Box, gestapelt in fünf Schichten.

Die Überlegungen hier wollen wir später benutzen, um (wie im Bild) sechs Rahmen der Größe 6x6 mit Hexominos und Trominos zu füllen.

Wenn man keine Lösung kennt, wie findet man eine? Und wie findet man weitere Lösungen? Von Hand sind solche Aufgaben wirklich kaum mehr zu schaffen, und auch der Computer bekommt Probleme. Im Unterschied zu den üblichen Aufgaben mit nur einem großen Rahmen gibt es hier viel weniger Lösungen, und deshalb müssen viel mehr Möglichkeiten durchprobiert werden, bevor die erste Lösung gefunden wird. Die bisher betrachteten Algorithmen und Lösungsstrategien führen in vertretbarer Zeit nicht zum Ziel, weil die entsprechende Software mit der Komplexität der Aufgabe überfordert war oder auch nur nicht die passenden Einstellungen gefunden wurden.

Aber wir können noch einen zusätzlichen Trick anwenden und die schwierige Aufgabe, mehrere gleiche Rahmen mit allen Steinen zu füllen, in zwei einfachere Teilaufgaben zerlegen, von denen jede viel einfacher gelöst werden kann.

Angenommen, wir haben n gleiche Rahmen, die mit den Steinen gefüllt werden sollen.

1. Teilaufgabe: Fülle nur einen Rahmen vollständig mit Steinen und suche dafür nach allen Lösungen. Für jede Lösung notieren wir nur die verwendeten Steine, nicht deren tatsächliche Anordnung im Rahmen. Danach sortieren wir diese Liste der Lösungen und entfernen dabei Dubletten. Das Ergebnis ist eine Liste L aller Teilmengen von Steinen, mit denen sich ein Rahmen füllen lässt. Diese erste Teilaufgabe lässt sich mit verschiedenen Computerprogrammen schnell lösen.

2. Teilaufgabe: Suche in der Liste L nach n verschiedenen Zeilen, so dass insgesamt kein Stein doppelt vorkommt. Wenn wir n solche Zeilen finden, dann haben wir genügend verschiedene Steine, um alle n Rahmen zu füllen. Dabei müssen wir auch alle unsere Steine verwenden, da keine überzähligen Steine vorhanden sind. 

Für die zweite Teilaufgabe finden wir keine vorgefertigte Lösungssoftware und wir müssen selbst programmieren. Zur Auswahl stehen (mindestens) zwei verschiedene Lösungsansätze: Wir können wieder einmal einen SMT-Solver einsetzen. Als zweite Möglichkeit bietet sich an, die Aufgabenstellung als Problem der exakten Überdeckung (siehe [1]) zu betrachten. Auf dieses Exact Cover Problem und den dazugehörigen Algorithmus X von Donald Knuth soll in einen eigenen Post eingegangen werden.

Zur Lösung mit einem SMT-Solver verwenden wir die Liste L. in jeder Zeile stehen die Namen einiger Steine, die zusammen den Rahmen füllen. Wir benutzen die Namen der Steine als Variablen und wollen jeder von ihnen als Wert eine Zahl zwischen 1 und n zuweisen, je nachdem, im wievielten Rahmen der Stein verwendet wird. Dazu nehmen wir n Kopien unserer Liste L und nennen sie L1, L2, .. Ln. Nun machen wir folgendes. Wir suchen mit dem SMT-Solver nach einer Belegung der Variablen mit den Werten 1,..., n mit den folgenden Bedingungen.

(Alle Variablen in der ersten Zeile von L1 haben den Wert 1
ODER alle Variablen in der zweiten Zeile von L1 haben den Wert 1
ODER ...
ODER alle Variablen in der letzten Zeile von L1 haben den Wert 1)
UND
(Alle Variablen in der ersten Zeile von L2 haben den Wert 2
ODER alle Variablen in der zweiten Zeile von L2 haben den Wert 2
ODER ...

ODER alle Variablen in der letzten Zeile von L2 haben den Wert 2)
UND
...
UND
(Alle Variablen in der ersten Zeile von Ln haben den Wert n
ODER alle Variablen in der zweiten Zeile von Ln haben den Wert n
ODER ...
ODER alle Variablen in der letzten Zeile von Ln haben den Wert n)

Mit anderen Worten lassen wir den Solver nach einer Belegung mit Werten, so dass es für jede Zahl zwischen 1 und n eine Zeile in der Liste gibt, deren Variable alle diesen gleichen Wert haben. Mit diesen n Zahlen haben wir n disjunkte Lösungen für unsere n Rahmen. Jeder Stein wird nur einmal verwendet, da jede Variable mit nur einem Wert belegt werden kann.

Das Verfahren soll an einigen Aufgaben demonstriert werden:

• Hexominos und Trominos in 6 Rahmen 6x6
• Spezielle Hexomino-Lösung in 6 Teilen

Mehr Infos

[1] https://en.wikipedia.org/wiki/Exact_cover

Gittersprünge und Tridrafter-Aufgaben

Die 14 Tridrafter wurden so ausgewählt, dass man jeden Tridrafter so in das Dreiecksgitter legen kann, dass er aus drei halben Dreiecken des Dreiecksgitters besteht. Das so entstanden Gitter heißt Drafter-Gitter. Aber es gibt das folgende Problem: Wir können einen relativ einfachen Rahmen auf zwei verschiedene Arten komplett mit Tridraftern füllen:

Im Drafter-Gitter können wir zwei unterschiedliche Bereiche mit dieser Form finden. Packen wir die linke Figur oben in die linke Gitterfläche und die rechte Figur in die rechte Gitterfläche, so passt alles perfekt, die gemeinsamen Kanten der aneinandergefügten Steine entsprechen den Gitterlinien.

Wenn wir die Figuren über Kreuz n die Gitterflächen packen, so stimmen die gemeinsamen Kanten  nicht mehr mit den Gitterlinien überein. Solch ein Übergang wird als Gittersprung bezeichnet und kommt bei Tridrafter-Aufgaben relativ häufig vor. 

Die zwei folgenden Bilder zeigen einen Rahmen in Form eines Hauses [1], der sich mit allen 14 Tridraftern füllen lässt. Dafür gibt es sogar Lösungen ohne (links) und mit (rechts) Gittersprüngen. Die gelben Steine liegen nicht in im gleichen Draftergitter wie die roten Steine.

Da das zugrundeliegende Draftergitter eine Sechsecksymmetrie besitzt, kann man nach Rahmen mit entsprechender Symmetrie suchen [2]. Bob Harris fand zwei solche Rahmen. Neben dem Sägeblatt ist dies die Pinnwheel (Windrad) genannte Figur unten. Für Pinwheel gibt es 10 verschiedene Lösungen (George Sichermann). Weitere solche symmetrischen Rahmen für die 14 Tridrafter gibt es nicht (Patrick Hamlyn).

Frage: Finden Sie die Gittersprünge bei Pinwheel?

Eine andere Aufgabe ist die Suche nach konvexen Rahmen, die mit den 14 Tridraftern gefüllt werden können. Eine ähnliche Frage gab es bei Tangram-Figuren.

Wie Miroslav Vicher [3] herausgefunden hat, gibt es insgesamt 1516 verschiedene konvexe Rahmen mit einer Fläche passend für die 14 Tridrafter, davon lassen sich aber nur 75 mit Tridraftern füllen. Neun dieser Rahmen sind symmetrisch und liefern damit interessante Aufgaben.

Hier ist die einfachste konvexe Tangram-Aufgabe (Nr. 22 bei Miroslav Vicher). Dafür gibt es 18 verschiede Lösungen, viele der anderen Aufgaben haben dagegen nur eine oder zwei Lösungen.

Mehr Infos:

[1] https://www.pentoma.de/tridrafter/

[2] http://www.recmath.com/PolyCur/dr3galaxy/index.html

[3] https://www.vicher.cz/puzzle/polyform/tridr/triddr.html

Symmetrie im quadratischen Gitter

Bei Symmetriepuzzles müssen einige wenige Teile (meist 2-4) so aneinandergelegt werden, dass sich insgesamt eine symmetrische Form ergibt. Dabei müssen alle Teile flach auf dem Tisch liegen und dürfen sich nicht überlappen. Wir wollen hier solche Symmetriepuzzles auf dem quadratischen Gitter untersuchen. Dabei bestehen die Teile aus mehreren Elementarquadraten und diese sollen entlang des quadratischen Gitters liegen.

Damit dürfen alle Teile gespiegelt oder um Vielfache von 90 Grad gedreht werden. Wir wollen hier die verschiedenen Lagen der Symmetrieachse bzw. des Mittelpunktes der Drehung betrachten und dazu jeweils Beispiele für entsprechende Symmetriepuzzles aus Pentominos betrachten. 

Wenn Sie Pentominos zur Hand haben oder mit 3D-Druck selber drucken wollen (Sie finden die STL-Files für Pentominos und Hexominos in der Sammlung zum Blog auf Thingiverse sowie bei Printables), können Sie die Beispiele unten als zu lösende Symmetriepuzzles verwenden.

Spiegelsymmetrie

Die Symmetrieachse kann entweder parallel oder in einem Winkel von 45 Grad zu einer Gitterlinie verlaufen. Betrachten wir zunächst die Spiegelung parallel zu einer Gitterlinie. Wir müssen nur  Spiegelsymmetrie entlang einer senkrechten Symmetrieachse betrachten, im Fall einer waagerechten Symmetrieachse können wir das ganze Gitter um 90 Grad drehen. 

Im einfachsten Fall ist die Symmetrieachse gleich einer Gitterlinie, dann ist die breite der Figur geradzahlig:

Die Symmetrieachse kann aber auch um eine halbe Gitterbreite verschoben sein, dann ist die breite der Figur ungerade:

Verläuft die Symmetrieachse schräg, so muss dies in einem Winkel von 45 Grad sein und die Symmetrieachse muss durch Gitterpunkte verlaufen. Höhe und Breite der Figur sind gleich.

Rotationssymmetrie

Wie wollen uns nur für Rotationssymmetrie bei Drehung um 180 Grad interessieren. Zwar würde das Quadratgitter in einigen Fällen auch Drehungen um 90 Grad zulassen, aber da zweimalige Drehung um 90 Grad einer Drehung um 180 Grad entspricht, besitzen alle rotationssymmetrischen Lösungen automatisch eine 180-Grad-Symmetrie.

Auch hier ist es nur der einfachste Fall, dass der Mittelpunkt der Drehung in einem Gitterpunkt liegt. Höhe und Breite der Figur sind dann geradzahlig.

Als zweite Möglichkeit kann der Mittelpunkt der Drehung auch in der Mitte eines Gitterquadrates liegen. Höhe und Breite der Figur sind beide ungerade.

Es gibt noch eine dritte Möglichkeit, nämlich dass der Mittelpunkt der Drehung in der Mitte einer Gitterkante liegt. Dann sind von Höhe und Breite eine geradzahlig, die andere ungerade.

Acht Elementarwürfel zusammenstecken

Aus acht Elementarwürfeln kann man neben dem 2x2x2-Würfel noch weitere Formen legen. Im Folgenden soll eine Übersicht über solche Formen gegeben werden, da bei verschiedenen Geduldspielen aus acht Elementarwürfeln immer wieder Aufgaben gestellt werden, solche Figuren zu legen. Hier eine Liste derartiger Geduldspiele aus unserem Blog.

Geduldspiele aus einzelnen Elementarwürfeln. Hier ist jede zusammenhängende Form aus acht Würfeln denkbar, aber natürlich nicht unbedingt lösbar.

• Perplexing Python-Puzzle
• Endlosband

Geduldspiele aus verketteten Halbwürfeln. Hier werden immer zwei Steine zu einer Art geschlossener Kette zusammengehängt und der letzte Halbwürfel muss im ersten hängen.

• Nob's Never Ending Puzzle
• Handed Halfcubes
• Cube Plus
• Double Half Cubes

Und noch mehr werden folgen.

Wir wollen hier nur den zweiten Fall der verketteten Halbwürfel betrachten. Welche Formen lassen sich aus acht in einem Ring zusammenhängenden Einzelwürfeln bilden? Dies sind genau die folgenden 11 Möglichkeiten:

Die Formen G, H und I lassen sich nicht durch Rotation in die jeweils gespiegelte Form überführen. Damit müssen die gespiegelten Formen zusätzlich betrachtet werden, falls die Menge der Halbwürfel des entsprechenden Geduldspiels nicht zu jedem Halbwürfel auch sein Spiegelbild enthält. 

Aus mathematischer Sicht ist die Lage folgendermaßen: Zunächst konstruieren wir aus der aus acht Würfeln zusammengesetzten Form einen Graphen. Wir betrachten statt der acht Würfel im quadratischen Gitter jeweils nur deren Mittelpunkte und verbinden die Mittelpunkte von je zwei Würfeln, die eine Seitenfläche gemeinsam haben, da diese Würfel in der Kette benachbart sein könnten. In diesem Graphen suchen wir nach einem sogenannten Hamiltonschen Zyklus: Das ist ein geschlossener Weg in dem Graphen, der jeden Knoten genau einmal enthält. Im Bild links finden wir einen solchen Hamiltonschen Zyklus, im rechten Bild nicht.

Finden wir keinen solchen Hamiltonschen Zyklus wie im Bild rechts, dann kann das Geduldspiel mit verketteten Halbwürfeln keine Lösung haben.

Auch sonst lassen sich nicht notwendigerweise alle denkbaren Formen aus den konkret vorgegebenen Halbwürfeln eines Geduldspiels legen. Für die Halfcube-Puzzles von Vinco gibt es die schöne Zusammenstellung aus [1], gezeigt mit freundlicher Genehmigung von Vinco. Für die verschiedenen Geduldspiele aus Halbwürfeln wird gezeigt, wie viele verschiedene Lösungen es für die einzelnen Aufgaben gibt.

Mehr Infos:

[1] https://www.vinco.cz/getFile/id:43392

Volumentest: Schwierigere Aufgaben für Hexominos (Nr. 11-13)

Kategorie: Aufgaben für Polyominos

Obwohl einige Aufgaben nicht schwieriger aussehen als andere, bereiten sie manchen Computerprogrammen große Schwierigkeiten. Wir erwarten eine Lösungszeit innerhalb von Sekunden, erhalten aber auch nach einer Stunde noch keine einzige Lösung. Wohlgemerkt sprechen wir durchaus von lösbaren Aufgaben, die auch eine vergleichbar große Anzahl von Lösungen haben

Wir wollen uns das Problem an einem Beispiel und dem Lösungsversuch mit dem PolySolver anschauen.

Aufgabe 11: Rechteck 15x15 mit U-förmigem Loch der Breite 13

Im 15x15-Quadrat bleiben 15 Elementarquadrate durch Hexominos unbelegt, wie wir bereits bei den Aufgaben 3-7 aus den Aufgaben für Hexominos (Nr. 1-10) gesehen haben. Diesmal formen wir aus den 15 überzähligen Elementarquadraten ein U-förmiges Loch der Breite 13 (im Bild schwarz) und versuchen den verbleibenden Platz mit den Hexominos zu füllen. Obwohl der PolySolver normalerweise weniger als 10 Sekunden für eine derartige Aufgabe benötigt, wird hier so schnell keine Lösung gefunden. Zwischendurch sieht der Zustand beispielsweise folgendermaßen aus:

Wenn keine Steine mehr einzufügen gehen, macht das Programm Backtracking. Dabei werden die zuletzt eingefügten Steine wieder entfernt und es wird anders versucht, die jetzt größeren Lücken zu füllen.

Wo ist das Problem? Schauen Sie sich die Größe der beiden verbliebenen Restflächen an: Diese betragen 11 (oben) bzw. 13 (unten). Sie lassen sich nicht mit Steinen der Größe 6 füllen, auch wenn man einige Steine herausnimmt und umsortiert. Man müsste mindestens soviel Steine herausnehmen, so dass die beiden Restflächen verschmelzen. Erst dann hat man wieder eine Chance. Wenn man die beiden dünnen Lücken unten am rechten und linken Rand aber gleich zu Beginn des Lösungsprozesses verschließt, kommt man beim klassischen Backtracking in vertretbarer Zeit nie wieder dahin zurück. Deshalb löst der PolySolver dieses Geduldspiel nicht.

Welcher zusätzliche Schritt würde hier helfen? Wir könnten aufpassen, dass auftretende Restflächen immer ein Vielfaches von 6 als Größe besitzen und sonst sofort abgebrochen und mit dem Backtracking begonnen wird. Dieser zusätzliche Schritt wird Volumentest genannt (weil er analog auch für dreidimensionale Probleme funktioniert) und ist ist bei einigen Solvern implementiert. Bei Polycube [1] gibt es auf der Kommandozeile den Parameter -v, und -v10 schaltet beispielsweise den Volumentest ein, sobald die Restfläche kleiner als 10 Steine groß ist. Mei mops.exe kann man im Menü Pack ein Häkchen bei Void Check setzen, um den Volumentest einzuschalten. Danach finden beide Programme wie erwartet Lösungen innerhalb Sekunden.

Aufgabe 12: Rechteck 33x7 mit Loch der Größe 7x3 in der Mitte

Hier ist die Situation analog zur Aufgabe 11: Das 33x7-Rechteck wird durch das große leere Rechteck in der Mitte nur durch zwei dünne Verbindungen (diese haben hier die Breite 2) oben und unten zusammengehalten. Wenn diese geschlossen werden und nicht auf die Größe der verbleibenden Restflächen geachtet wird, landet man schnell in einer Sackgasse. Mit dem Volumentest gibt es aber kein Problem.

Aufgabe 13: Rechteck 15x15 mit 15 Löchern in Fünfergruppen auf der Diagonale

Bei dieser Aufgabe ist nicht klar, ob der Volumentest hilft. Aber ein einfacher Versuch zeigt: Ohne Volumentest findet Polycube so schnell keine Lösung, mit Volumentest geht es blitzschnell.

Mehr Infos:

[1] www.mattbusche.org

Das Kriterium von N. de Bruijn für beliebige Klötzer

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Das Packproblem für harmonische Klötzer (das sind solche mit Seitenlängen a, ab und abc) in eine quaderförmige Box wird durch das Theorem von de Bruijn vollständig gelöst. Aber wie ist das mit allgemein Klötzern mit ganzzahliger Seitenlänge?

Der allgemeine Fall ist nicht vollständig gelöst, aber es gibt das folgende Kriterium von de Bruijn, welches erfüllt sein muss, damit es überhaupt möglich sein könnte, eine Box vollständig zu füllen.

Damit eine Box mit den Seitenlängen A, B und C sich vollständig mit Klötzern der Seitenlängen a, b und c füllen lässt, muss folgendes gelten:

• eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von a, 
• eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von b und 
• eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von c.

Dabei kann durchaus beispielsweise C Vielfaches sowohl von a und b sein und weder A noch B Vielfache von a oder b. So kann man fünf Klötzer der Größe 1x2x3 in eine Box der Größe 1x5x6 packen:

Hier haben die Seitenlängen 2 und 3 des Klotzes als gemeinsames Vielfaches die Seitenlänge 6 der Box.

Andererseits ist reicht das Kriterium nicht aus, um die Lösbarkeit auch sicherzustellen. Ein einfaches Gegenbeispiel dafür ist ein 1x2x3-Klotz, den man nicht in eine 1x1x6-Box packen kann, obwohl das Kriterium erfüllt ist.  

Mehr Infos: 

[1] Wikipedia

Harmonische Klötzer packen: Das Theorem von N. de Bruijn

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Das folgende Theorem von Nicholas G. de Bruijn [1] kann man als dreidimensionale Verallgemeinerung des Theorems von Klarner für den zweidimensionalen Fall betrachten. Allerdings gilt es nur für sogenannte harmonische Klötzer, das sind solche mit Seitenlängen a, ab und abc für natürliche Zahlen a, b und c. Bei solchen harmonischen Klötzern ist die nächstlängere Seitenlänge also immer ein ganzzahliges Vielfaches der nächstkürzeren Seite. Beispiele sind Stäbe mit den Seitenlängen 1, 1 und 4 oder Klötzer mit den Seitenlängen 1, 2 und 4.

Das Theorem von de Bruijn klärt nun, wann genau eine Box vollständig mit solchen harmonischen Bricks gefüllt werden können:

Eine Box kann genau dann mit harmonischen Klötzern der Größe a x ab x abc gefüllt werden, wenn sie die Größe ap x abq x abcr für irgendwelche ganzzahlige p, q, r hat, d.h. die Box in jeder Richtung ein Vielfaches des Klotzes ist.

Damit lässt sich die Box auch auf ganz einfache Weise füllen, ohne Klötzer irgendwie drehen zu müssen. Die Aussage des Theorems ist also genau wie beim Theorem von Klarner: Wir können die Box entweder auf eine ganz einfache Weise mit harmonischen Klötzern füllen oder es geht gar nicht. Im ersten Fall, also wenn es klappt, kann man die Box manchmal auch auf eine komplizierte Art füllen. Aber immer, wenn es kompliziert möglich ist, dann ist es auch einfach möglich.

Das folgende Foto zeigt 24 harmonische Klötzer der Größe 1x2x4 gestapelt zu 4x6x8, links einfach, rechts komplizierter.

Aber Achtung, damit ist das Problem des Kistenpackens noch nicht vollständig gelöst, denn es gibt ja noch die nicht-harmonischen Klötzer (z.B. 1x2x3), für die das Theorem nichts aussagt. Es bleiben also noch eine Menge Aufgaben. Ein Beispiel ist das Singmaster Packing mit nicht-harmonischen Steinen der Größe 1x3x4

Das Theorem von de Bruijn lässt sich übrigens auch in höheren Dimensionen formulieren und gilt dort analog. Mangels Relevanz für Geduldspiele soll das hier aber nicht weiter betrachtet werden.

Mehr Infos: 

[1] Wikipedia

Verschwinden und Erscheinen durch Drehung um 45 Grad

Was ist der Unterschied zwischen den zwei Bildern? Wurden die gleichen roten Dreiecke nur zweimal in dasselbe große Rechteck eingepackt, dazwischen aber um 45 Grad gedreht? 

Nun, so einfach ist es nicht. Es stimmt, dass die roten Dreiecke alle die gleiche Größe haben. Denn später sollen Geduldspiele entstehen und mit den kleinen Dreiecken (oder Steinen bestehend aus mehreren solchen Dreiecken) soll hantiert werden. Richtig ist auch, dass sie beiden mit den Rechtecken gefüllten Formen optisch kaum unterscheidbar sind.

Nachzählen ergibt aber, dass das linke Quadrat aus 16 Dreiecken besteht, das rechte aus 18 Stück. Wieder entsteht der Eindruck, dass durch eine Drehung (diesmal um 45 Grad) die Größe der Fläche verändert werden kann. Das ist natürlich Unsinn, aber wenn wir das verstanden haben, wird der Mechanismus hinter weiteren sogenannten Melting Block Puzzles etwas klarer. Bevor wir uns diesen Mechanismus etwas genauer ansehen, hier die Regel zur Lösung solcher Geduldspiele:

Voraussetzung: Die Kanten zwischen den Steinen laufen entweder 45 Grad geneigt zu einer Außenkante des Rahmens, oder parallel zu einer Außenkante.

Regel: Ist ein Rahmen gefüllt mit Steinen bestehend aus gleichgroßen, gleichschenklig-rechtwinkligen Dreiecken (also aus halbierten Quadraten), wobei die langen Dreieckseiten alle entweder parallel zu den Außenseiten (wie links im Bild) oder parallel zu einer Diagonale (wie rechts im Bild) verlaufen. Dann kann man versuchen, alle Steine um 45 Grad zu drehen und so deren Orientierung zu ändern und die Steine dann wieder in den Rahmen zu packen. Wenn das klappt, entsteht möglicherweise mehr Platz im Rahmen für einen zusätzlichen kleinen Stein.

Wieso kann das funktionieren? Berechnen wir einmal die Seitenlängen der beiden Quadrate oben. Fangen wir der Einfachheit halber rechts an: Das rechte Quadrat hat eine Seitenlänge von 3, damit eine Fläche von 9 und besteht deshalb aus 18 Halbquadraten. Das linke Quadrat dagegen hat als Seitenlänge die doppelte Länge der Diagonale eines Einheitsquadrates. Da die Länge der Diagonale eines Einheitsquadrates √2 ≈1.414 beträgt, ist die Seitenlänge des linken Quadrates nur rund 2.828 statt 3. Das sind nur 5.7% weniger als beim rechten Quadrat und sorgt für die kleinere Fläche von 8 statt 9.

Dieser Trick klappt immer, wenn ein Vielfaches von √2 nahezu ganzzahlig ist. Falls Ihnen also der Unterschied oben zu auffällig ist, suchen wir nach weiteren Möglichkeiten. Sehr gut ist die folgende Näherung mit nur einem Prozent Abweichung: 7√2 ≈ 9.90. Diesen Unterschied kann man mit dem bloßen Auge nicht mehr wahrnehmen.

Wie wird daraus ein Geduldspiel?  Wir nehmen zunächst den kleineren Rahmen und setzen mehrere der kleinen Dreiecke zu Steinen für das Geduldspiel zusammen. Dabei müssen wir aufpassen, dass sich die Steine auch in dem größeren, um 45 Grad gedrehten Rahmen einfügen lassen. Dabei bleibt dann automatisch Platz von zwei zusätzlichen kleinen Dreiecken. Wenn Sie Glück haben, liegen diese unmittelbar nebeneinander und wir können ein größeres Dreieck, bestehend aus zwei kleinen Dreiecken, einfügen.

Hier einige Beispiele aus dem Blog:

Das einfache Schema (Bild oben) wird verwendet beim Überflüssigen Dreieck.
Das kompliziertere Schema (Bild unten) wird verwendet beim Magic Square (Aluminium) und bei Square+.

Legespiele lösen mittels SAT- / SMT-Solver

Um ein Puzzle mit dem Computer lösen zu können, benötigen wir Programm, das eine Lösung (oder alle Lösungen) für dieses Puzzle erzeugt. Leider können wir oft kein fertiges Programm für diesen Zweck finden und müssen selbst programmieren. Ganz einfach ist das nicht, da für eine Lösung eines Puzzles häufig extrem viele Positionen untersucht werden müssen. Diese Zahl ist oft so groß, dass ein einfaches Durchprobieren aller Möglichkeiten zwar zum Ziel führen würde, aber viel zu lange dauert. Deshalb benötigt man weitere clevere Algorithmen wie Backtracking, um das vollständige Durchprobieren drastisch abzukürzen. Dadurch wird die Bearbeitungszeit akzeptabel, aber der Programmieraufwand steigt, da das abstrakte Backtracking an das vorliegende Puzzle angepasst werden muss.

Wünschenswert wäre es doch, statt der Programmierarbeit das Puzzle nur mit abstrakten Mitteln zu beschreiben. Kann es für solch eine abstrakte Beschreibung ein allgemeines Lösungsverfahren geben? Die Antwort ist 'ja' und damit kommen wir zu SAT- / SMT-Solvern.

SAT- / SMT-Solver

 SAT- / SMT-Solver sind sehr mächtige Werkzeuge, die sich für viele Probleme in der Informatik einsetzen lassen. Lösungen für Geduldspiele sind hier hier nur ein Nebenprodukt.

Die Aufgabe eines SAT- / SMT-Solvers besteht darin, für eine gegebene mathematische Formel festzustellen, ob sie eine Lösung besitzt und diese anzugeben. Bei einem SAT-Solver muss es sich um eine aussagenlogische Formel handeln wie (x ∨ ¬y) ∧ (¬x ∨ y ∨ z) ∧ ¬x, bei SMT-Solvern sind zusätzlich einige weitere Formeltypen wie arithmetische Gleichungen (wie u=3*v) oder Ungleichungen (wie u+v<10) möglich. Der genaue Umfang möglicher Formeln hängt vom jeweiligen SMT-Solver ab. Die Beschreibung der Problemstellung (hier also des Geduldspiels) wird recht einfach, und um den Lösungsweg, mit dem der SAT- / SMT-Solver seine Lösung findet, müssen wir uns keine Gedanken machen, dies passiert völlig automatisch. Intern werden wieder Backtracking und ähnliche Verfahren angewendet, aber darum müssen wir uns nicht mehr kümmern.

So viele Vorteile gibt es allerdings nicht ohne Nachteile: Das allgemeine Lösungsverfahren eines SAT- / SMT-Solvers arbeitet langsamer als ein problemangepasstes Backtracking, wir werden also keine rekordverdächtig großen Puzzles mit minimalem Programmieraufwand lösen können. Aber an der Weiterentwicklung von  SAT- / SMT-Solvern wird weltweit gearbeitet, so dass demnächst ihre Geschwindigkeit steigt.

Beschreibung von quadratischen 3x3-Legespielen für einen SMT-Solver

Wie lässt sich ein Legespiel mit derartigen Formeln beschreiben? Hier sollen zumindest verbale Beschreibungen für diese Formeln gegeben werden. Dazu betrachten wir die üblichen 3x3-Legespiele, bei denen neun quadratische Karten zu einem 3x3-Quadrat gelegt werden sollen, so dass immer passende Kanten aufeinandertreffen. 

Wir können das Spiel wie folgt beschreiben:

• Das Spiel besteht aus neun vorgegebenen Karten mit je vier Kanten. 
• Die Kanten der Karten haben je einen Namen (z.B. "brauner Hund, Kopf")
• Dazu gibt es einen zunächst leeren Rahmen mit sieben Positionen, der die Karten aufnehmen soll.
• Die Positionen sind durchnummeriert und die Kanten an jeder Position haben jeweils Variablen für Farbe und Körperteil. Legt man eine Karte an eine Position, übernehmen diese Variablen die Werte (d.h. Farbe und Körperteil) von den Kanten dieser Karte.

Nach der Beschreibung des Spiels erfolgt die Beschreibung einer Lösung:

• Jede Karte hat vier mögliche Orientierungen, darf also mehrfach um 90 Grad gedreht werden. 
• Jede Karte wird an eine Position im Rahmen gelegt. Daraus ergeben sich die Farben und Körperteile an den Kanten der Positionen im Rahmen. 
• Die Positionen der Karten sind alle verschieden. (Damit wird erreicht, dass keine zwei Karten übereinanderliegen und alle Positionen im Rahmen belegt werden)
• Gemeinsame Kanten benachbarter Positionen haben zueinander passende Namen, (z.B. "brauner Hund, Kopf" und "brauner Hund, Schwanz"). Es gibt 12 derartige Paare benachbarter Kanten, daraus entstehen jeweils 12 Bedingungen für gleiche Farben und unterschiedliche Körperteile.

Der große Vorteil besteht in der Kompaktheit der Beschreibung und der Einfachheit, die Beschreibung an andere Legespiele anzupassen. Mögliche Veränderungen wären:

• Dreieckige oder sechseckige Karten statt quadratischer Karten.
• Die Karten dürfen nicht gedreht werden.
• Die Karten tragen auf der Rückseite die gleichen Bilder und dürfen zusätzlich gewendet werden.
• Corner Matching statt Edge Matching.

Zusätzlich können wir SMT-Solver auch für ganz andere Typen von Geduldspielen einsetzen: Für Packprobleme (wie Pentominos) und sogar für Geduldspiele, die ganze Zugfolgen erfordern wie Zauberwürfel. 

Anleitung zum Verwenden eines SAT- / SMT-Solvers

Für mehrere SAT- / SMT-Solver gibt es eine Schnittstelle zur Programmiersprache Python. Dann kann man mit 1/2 bis 1 Seite Quelltext die Variablen und die Anforderungen an die Lösung für das Geduldspiel in Python beschreiben und anschließend den SAT- / SMT-Solver aufrufen, der dann die restliche Arbeit erledigt. Eine sehr schöne Anleitung gibt es von Dennis Yurichev [1]. Das Buch enthält auch sofort lauffähigen Quellcode für mehrere Geduldspiele, darunter Pentominos.

Mehr Infos:

[1] Dennis Yurichev: SAT/SMT by Example, 2024

Verschwinden und Erscheinen durch Drehung um 90 Grad

Was ist der Unterschied zwischen den zwei Bildern? Wurden die gleichen blauen Rechtecke nur zweimal in dasselbe große Rechteck eingepackt, einmal für hoch und einmal für quer? 

Nein, so einfach ist es nicht. Es stimmt, dass die kleinen blauen Rechtecke alle die gleiche Größe haben. Denn später sollen Geduldspiele entstehen und mit den kleinen Rechtecken (oder Steinen bestehend aus mehreren solchen Rechtecken) soll hantiert werden. Richtig ist auch, dass sie beiden mit den Rechtecken gefüllten Formen optisch kaum unterscheidbar sind.

Nachzählen ergibt aber, dass das linke große Rechteck aus 8x6=48 kleinen Rechtecken besteht, das rechte aus 7x7=49 Stück. Wie kann durch eine Drehung um 90 Grad eines der Rechtecke erscheinen bzw. verloren gehen? Wenn wir das verstanden haben, wird der Mechanismus hinter mehreren sogenannten Melting Block Puzzles etwas klarer. Bevor wir uns diesen Mechanismus etwas genauer ansehen, hier die Regel zur Lösung solcher Geduldspiele:

Regel: Ist ein Rahmen gefüllt mit Steinen bestehend aus gleichgroßen Rechtecken, die alle die gleiche Orientierung haben (also alle für hoch oder alle für quer), dann kann man versuchen, bei allen Steinen die Orientierung zu ändern (also quer statt hoch oder umgekehrt) und die Steine dann wieder in den Rahmen zu packen. Wenn das klappt, entsteht möglicherweise mehr Platz im Rahmen für einen zusätzlichen kleinen Stein.

Wieso kann das funktionieren? Beginnen wir mit kleinen Quadraten statt Rechtecken und bilden daraus ein 6x8-Rechteck und ein 7x7-Quadrat.  

Jetzt kommt der Trick: Das linke 6x8-Rechteck ist breiter als hoch. Wir stauchen die beiden nebeneinanderliegenden Flächen in der Breite ein wenig. Dadurch wird das rechts befindliche Quadrat verformt und des entsteht ein hochstehendes Rechteck, dass schmaler wird und sich immer weiter von der quadratischen Form entfernt. Das linke, liegende Rechteck verformt sich auch und wird einem Quadrat immer ähnlicher. Wir hören mit der Stauchung auf, wenn beide Rechtecke dasselbe Seitenverhältnis haben.   

Da wir die kleinen Quadrate ebenfalls auf einheitliche Weise gestaucht haben, sehen wir dass trotz der gleichen Proportionen das linke Rechteck eine Fläche von 48 kleinen Rechtecken hat, das rechte statt dessen 49. Damit ist das linke Rechteck um rund 2% kleiner als die rechte, die Seitenlängen der beiden Rechtecke unterscheiden sich um rund 1%. Wenn in einem letzten Schritt noch das rechte große Rechteck um 90 Grad gedreht wird, erhält man das Bild ganz oben: Zwei scheinbar gleichgroße Rechtecke mit unterschiedlicher Fläche.

Wie wird daraus ein Geduldspiel?  Wir nehmen den Rahmen für das 7x7-Rechteck wie oben links abgebildet und ordnen 48 Rechtecke in der "falschen" Orientierung ein wie im Bild oben links. Die Rechtecke sitzen nicht ganz straff, es bleibt etwa 1% Spiel, welches aber benötigt wird. Dazu gibt es ein zusätzliches kleines Rechteck, welches auch noch mit in den Rahmen eingeordnet werden soll, sozusagen hineinschmelzen soll in die kleinen Ritzen. Ein Beispiel ist das Puzzle Nr. 49.

Zum Schluss benötigen wir noch die genauen Maße für Steine und Rahmen. Zu Beginn haben die kleinen Quadrate die Größe 1x1, die Rahmen sind 8x6 bzw. 7x7. Multiplizieren wir bei der Stauchung alles in x-Richtung mit dem Faktor q, so haben die kleinen Quadrate die Größe qx1, die Rahmen sind 8qx6 bzw. 7qx7. Wenn wir nun fordern, dass die beiden Rechtecke dasselbe Seitenverhältnis haben, dann muss gelten: 8q/7=6/(7q), also q²=3/4 und schließlich q=½√3 ≈ 0,866.

Wenn unsere kleinen Rechtecke oben im Bild sie Größe von 0,866x1 haben, dann hat das linke Rechteck die Maße 6,928x6,000. Das rechte hat die Maße 7,000x6,062. Das ist mit bloßem Auge nicht zu unterscheiden.

Wir können natürlich auch andere Zahlen statt 48 und 49 nehmen, ganz allgemein können wir die Formel (n-1)*(n+1)+1=n² verwenden. Auch größere Flächenunterschiede sind möglich

Hier einige Beispiele aus dem Blog:

Wunderpuzzle 16: 3x5 bzw. 4x4
Wunderpuzzle 25: 4x6 bzw. 5x5
Nummer 49: Größe 6x8 bzw. 7x7 wie hier beschrieben.
Ormazd: 7x9 bzw. 8x8
Impossible Puzzle Style E: 9x10 bzw. 7x13
Pentaparadox-21: 10x10 bzw. 7x15

Tangram-Zwillinge

Nach den konvexen Tangram-Figuren ist dies die zweite Gruppe von Tangram-Aufgaben, bei denen keine konkreten Figuren vorgegeben werden, sondern mehrere Lösungen für eine Art Textaufgabe gefunden werden sollen.

Diesmal sollen aus den sieben Tangram-Steinen zwei identische Figuren gelegt werden, die dann Tangram-Zwillinge genannt werden. Mindestens zwei davon sind uns schon begegnet: Sind die sieben Tangramsteine als Quadrat verpackt, kann man das große Quadrat entlang einer Diagonale in zwei Teile zerlegen und erhält zwei kongruente Dreiecke als Tangram-Zwillinge. Manchmal sind die Tangram-Steine auch als Rechteck verpackt, welches sich dann in zwei kleinere Quadrate zerlegen lässt.

Hier vier solche Tangram-Zwillinge:

Noch mehr Vorlagen gibt es bei [1]

Die Aufgabe für Fortgeschrittene besteht darin, eigene Tangram-Zwillinge zu finden. Wenn man etwas systematisch vorgehen will, kann man das folgendermaßen tun: Beide Zwillinge müssen die gleiche Größe haben, also können wir die sieben Tangramsteine erst einmal in zwei flächengleiche Mengen aufteilen. Wenn die zwei kleinen Dreiecke (D1) eine Fläche von jeweils 1 haben, dann haben Quadrat (Q), Parallelogramm (P) und das mittelgroße Dreieck (D2) je eine Fläche von 2 und die zwei großen Dreiecke (D4) eine Fläche von 4. Bei einer Gesamtfläche von 16 muss jeder Zwilling eine Fläche von 8 haben, dafür gibt es nur die folgenden Möglichkeiten.

• D4+D4  /  D1+D1+D2+Q+P
• D4+Q+P  /  D4+D1+D1+D2
• D4+D2+Q  /  D4+D1+D1+P
• D4+D2+P  /  D4+D1+D1+Q

Bei genauerer Betrachtung der Zwillinge oben sieht man, dass sie zu diesen vier verschiedenen Klassen gehören. Mehr Beispiele gibt es bei [2] und [3].

Google: Tangram Zwillinge

Mehr Infos:

[1] https://legepuzzle.de/tangram-vorlagen-zwillinge.html 

[2] https://www.math.uni-bielefeld.de/~ringel/puzzle/puzzle02/tangram.htm 

[3] https://ordoglakat.blog.hu/2021/04/11/tangram_azonossagok

Konvexe Tangram-Figuren

Üblicherweise bestehen Tangram-Aufgaben darin, vorgegebene Figuren nachzulegen. Aber es geht auch anders: Wir können uns Eigenschaften der Figuren vorgeben und dann versuchen, alle möglichen Figuren mit dieser Eigenschaft zu legen.

Eine interessante Eigenschaft ist die Konvexität. Eine ebene Figur ist konvex, wenn ein darum herum gespannter Gummiring überall am Rand der Figur anliegt, die Figur also keine Einbuchtungen nach innen besitzt. Außerdem darf die Figur keine Löcher enthalten.

Hier ein Beispiel für eine nicht-konvexe Tangram-Figur mit Gummiring.

Aufgabe: Nehmen Sie die Tangram-Steine und legen Sie aus den sieben Steinen nacheinander möglichst viele verschiedene konvexe Figuren!

Es bleibt die Frage, wie viele konvexe Tangram-Figuren es überhaupt gibt. Um das herauszufinden, gibt es zwei Wege, die Sie nacheinander gehen können: 

1. Sie versuchen, aus den sieben Steinen nacheinander möglichst viele konvexe Figuren zu legen. Wenn Sie ein wenig systematisch vorgehen wollen, versuchen Sie es nacheinander mit einem Dreieck aus sieben Steinen (das ist einfach), mehreren verschieden geformten Vierecken, mehreren Fünfecken und auch mehreren Sechsecken. Haben Sie mehr als 10 verschiedene Figuren geschafft?
2. Zweitens können Sie versuchen sich zu vergewissern, dass Sie wirklich alle Lösungen gefunden haben. Manche Paare von Kanten treffen in verschiedenen Figuren immer wieder aufeinander, andere nie. Sehen Sie den Unterschied? 

Lösungshinweis: Die Anzahl verschiedener konvexer Tangram-Figuren ist recht übersichtlich, es gibt genau 13 Stück. Der mathematische Beweis stammt von Wang und Hsiung aus dem Jahr 1942 [1]. Er benutzt die Tatsache, dass die Seitenlänge eines Quadrates zur Länge der Diagonale ein irrationales Verhältnis hat. In der Ausgangsfigur bestehend aus einem großen Einheitsquadrat  haben alle senkrecht verlaufenden Kanten die rationalen Längen 1 oder ½, alle schräg verlaufenden Kanten die irrationalen Längen ½√2 oder ¼√2. Um konvexe Figuren zu bilden, müssen nun rationale Kanten an andere rationale Kanten stoßen und irrationale an irrationale, sonst treten irgendwo zusätzliche Ecken hervor und die Konvexität geht verloren. Es ergeben sich die folgenden 13 Möglichkeiten:

 

Google: convex tangram figures

Mehr Infos:

[1] Wang, F.T., Hsiung, C.-C.: A theorem on the tangram. Am. Math. Mon. 49(9), 596–599 (1942)

Das Problem von Heesch

Kategorie: Gleiche Steine in flache Rahmen packen

Der deutsche Mathematiker Heinrich Heesch (1906-1995) interessierte sich für folgendes Parkettierungsproblem. Möglichst viele Exemplare einer einzigen Figur sollen folgendermaßen angeordnet werden: Man beginnt in der Mitte mit einem dieser Steine. Darum herum soll ein lückenloser Ring aus den gleichen Steinen gelegt werden. Jeder solche Stein soll den Ausgangsstein (zumindest in einer Ecke) berühren. Dabei dürfen sich die Steine nicht überlappen und es darf keine Lücke bleiben. Allerdings dürfen die Steine gedreht und gewendet werden. Solch ein Ring wird auch als Corona bezeichnet. Allgemein betrachtet ist der Stein in der Mitte seine eigene Corona nullter Ordnung. Die Steine der Corona (n+1)ter Ordnung umschließen die Corona n-ter Ordnung vollständig und lückenlos, wobei jeder Stein die Corona n-ter Ordnung berührt.

Wieviele solche Corona-Ringe lassen sich um den mittleren Stein legen? Die Maximalzahl der möglichen solchen Ringe wird als Heesch-Zahl der Figur bezeichnet. Viele Figuren haben die Heesch-Zahl null. Ein Beispiel dafür ist eine Kreisscheibe, um die herum man zwar sechs weitere Kreise legen kann, aber es bleiben Lücken im Inneren des Gebildes, die man nicht schließen kann. Das andere Extrem ist die Heesch-Zahl unendlich, beispielsweise für ein Quadrat. Hier lassen sich ganz einfach immer weitere Ringe bilden.

Die interessanten Fälle sind Figuren mit Heesch-Zahlen zwischen null und unendlich. Zunächst ist nicht einmal klar, ob es so etwas gibt und welche Heesch-Zahlen möglich sind. Einige Mathematiker vermuten, dass jede natürliche Zahl als Heesch-Zahl möglich ist. Aber dies ist noch nicht bewiesen und auch nur für die Zahlen von eins bis sechs sind Figuren mit den entsprechenden Heesch-Zahlen bekannt. 

Die folgende Figur mit Heesch-Zahl 1 stammt von Walter Lietzmann [1]. Es gibt also nur eine Corona.

Bildquelle: [1]

Die Figur mit Heesch-Zahl 2 stammt von Anne Fontaine [1].

Bildquelle: [1]

Einige dieser Figuren sind interessant, weil sie sich auf recht verschiedene Arten aneinanderlegen lassen und sich deshalb für Geduldspiele anbieten. 

Mehr Infos:

[1] Wikipedia

Komplizierte Schiebespiele finden

Kategorie: Schiebepuzzles mit Polyominos (systematisch)

Wir wollen uns auf die Suche nach den schwierigsten Schiebespielen begeben. Diese Schiebespiele bestehen jeweils aus einer Anfangs- und einer Endstellung, erlaubt sind nur achsenparallele Züge der Steine.

Dank der Computer können wir große Mengen von Schiebespielen systematisch untersuchen. Vorher müssen wir aber unsere Aufgabe genau beschreiben. Für den Vergleich verschiedener Schiebespiele wählen wir eine feste Größe des Rahmens aus, in den Beispielen dieser Einführung wird das die Größe 3x4 sein. Als Steine für die Schiebespiele lassen wir alle Formen bestehend aus einem bis vier Elementarquadraten zu, von jedem Stein dürfen auch mehrere Exemplare (in jeder möglichen Orientierung) verwendet werden. Diese Steine dürfen während des Spiels nur achsenparallel um ganze Längeneinheiten verschoben werden. Auch wenn genügend Platz auf dem Spielfeld ist, dürfen die Steine beispielsweise nicht um 90 Grad gedreht werden. 

Ein einzelnes Schiebespiel besteht nun aus der Rahmengröße und einer Menge von Steinen (mit vorgegebener Orientierung), die verwendet werden soll. Dann werden alle Stellungen ermittelt, die diese Steine im vorgegebenen Rahmen einnehmen können. Dabei wird zusätzlich gespeichert, welche Stellungen jeweils durch die Verschiebung eines einzelnen Steines ineinander überführt werden können. Daraus wird der Graph des Schiebespiels aufgebaut. Aus der größten Zusammenhangskomponente des Graphen werden nun zwei Stellungen mit maximalem Abstand ermittelt und diese werden als schwierigste Aufgabe des Schiebespiels bezeichnet. Es kann weitere Paare von Stellungen mit maximalem Abstand geben und in seltenen Fällen könnten sich auch in anderen Zusammenhangskomponenten noch schwierige Aufgaben verstecken.

Die Schwierigkeit eines Schiebespiels soll gemessen werden durch die minimalen Anzahl der nötigen Züge, wobei bei jedem Zug ein Stein jeweils um eine Position verschoben wird. 

Statt einfach nur eine Liste der allerschwersten Spiele anzugeben, sollen die Schiebespiele in verschiedene Typen eingeteilt werden und von jedem solchen Typ schwierige Spiele vorgestellt werden.

Die nachfolgenden Beispiele der Größe 3x4  sind noch nicht wirklich schwer, aber sehr gut für Anfänger geeignet. 

3D-Druck: Steine und Rahmen finden sich im Baukasten für mehr als 50 Schiebespiele.

Übersicht über die verschiedenen Typen

Typ: Rotation des gesamten Spiels

Dies ist das schwierigste Spiel der Größe 3x4 und benötigt 94 Züge. Die Stellung im Ziel geht aus der Ausgangsstellung durch eine Rotation um 180 Grad hervor. Dies lädt allerdings zu Mogeln ein: Man macht beginnend mit der Ausgangsstellung einige Züge, dreht dann heimlich das gesamte Brett um 180 Grad und macht die ersten Züge wieder rückgängig. Dann ruft man "Hurra, ich hab's geschafft." 

Deshalb werden uns solche rotationssymmetrischen Spiele kaum noch interessieren.

Typ: Sortieren

Bei diesen Schiebespielen zeichnet sich das Ziel dadurch aus, dass gleiche Steine sich möglichst geordnet beieinander finden.

Typ: Spiegeln

Start und Ziel sind horizontal oder vertikal gespiegelt.

Typ: Ein Stein muss wandern

Start und Ziel unterscheiden sich (fast) nur dadurch, dass einer der Steine (hier das gelbe Quadrat weit von der Ausgangsposition weg gewandert ist, die anderen Steine aber wieder (fast) an ihrer Startposition sind.

Typ: Start und Ziel jeweils gemischt ohne auffällige Eigenschaften

Das zweitschwierigste Spiel der Größe 3x4 kommt recht unauffällig daher:

Dies passiert relativ häufig, solche Spiele sind auf den ersten Blick uninteressant.

Schiebespiele als Graphen

Wenn man Schiebespiele analysieren möchte, bieten sich Graphen an. Dazu betrachtet man alle Möglichkeiten, die Steine in den dazugehörigen Rahmen zu packen. Diese sollen als Stellungen bezeichnet werden. Jede solche solche Stellung bildet einen Knoten des Graphen. Jeweils zwei Knoten werden durch eine Kante verbunden, wenn sich eine Stellung durch einen einzelnen Zug in die andere Stellung überführen lässt. Diese Kanten sind nicht gerichtet, da jeder Zug auch in der umgekehrten Richtung ausgeführt werden kann.

Das Bild zeiht einen Ausschnitt aus dem Graphen für das einfache Schiebespiel von F.C. Hughes. Links im Graphen findet sich die Startposition. Zwei Positionen sind so verbunden, dass man jeweils den zu bewegenden Stein erkennt. Man sieht sehr schön, dass man sich oben in der Mitte in seiner Sackgasse befindet und nur Züge rückgängig machen kann.

Frage: Welche Position befindet sich unten in dem Rechteck mit dem Fragezeichen? 

Was kann der Graph eines Schiebespiels uns über das entsprechende Schiebespiel aussagen? Er kann uns bei der Such nach einer Lösung helfen, allerdings meist nur mit Hilfe eines Computers. Da es für die meisten Schiebespiele recht viele Stellungen gibt (einige Tausend bis viele Millionen), können wir den Graphen nicht einfach auf ein Stück Papier zeichnen und einfach so analysieren. Der Computer kann uns auch für größere Graphen noch helfen, stößt aber irgendwann wegen der schieren Größe der Graphen auch an Grenzen.

Hier eine Zusammenstellung von Aufgaben für die Suche im Graphen. Zunächst zwei Fragen, die für die Lösung konkret gegebener Schiebespiele von Bedeutung sind:

Aufgabe 1: Finde den (oder genauer gesagt: einen) kürzesten Weg von einer ersten vorgegebenen Stellung (als Start) zu einer zweiten Stellung als Ziel. Diese Aufgabe wird beispielsweise bei dem Schiebespiel von L. W. Hardy (1909) gestellt, ebenso beim Moving Day Puzzle (hier ist die Lage der übrigen drei kleinen Quadrate zwar nicht explizit vorgegeben, aber es besteht kaum eine Auswahl. Abstrakt betrachtet muss man in dem Graphen einen kürzesten Weg (oder wenigstens überhaupt ein Weg) zwischen den zwei Knoten zu Start und Ziel finden.

Aufgabe 2: Finde den kürzesten Weg von einem Startknoten zu einer Menge von möglichen Zielknoten. Solch eine Menge von Zielknoten wird beim Eselspuzzle und vielen anderen verwendet: Zu der Menge gehören hier alle Knoten, bei denen sich der quadratische Stein der Größe 2x2 an einer bestimmten Position, nämlich unten in der Mitte, befindet.

Für beide Aufgaben ist es nicht unbedingt notwendig, den ganzen Graphen zu kennen. Man kann den Graphen während der Suche nach dem kürzesten Weg sukzessive aufbauen und so bei kurzen Wegen auch relativ schnell eine Lösung finden. Die benötigte Zeit wächst allerdings mit der Länge des Weges stark an. 

Für die folgenden Aufgabenstellungen benötigt man den ganzen Graphen: Sie dienen dazu, ein Schiebespiel besser zu verstehen und neue, schwierige Aufgaben für dieses Schiebespiel zu stellen.

Aufgabe 3: Wie viele Stellungen sind mit den gegebenen Steinen im vorgegebenen Rahmen überhaupt möglich? D.h. aus wie vielen Knoten besteht der gesamte Graph?  

Aufgabe 4: Es ist in der Regel nicht möglich von einer beliebigen Stellung zu jeder anderen möglichen Stellung zu gelangen. Einige Stellungen sind einfach nicht über Züge aus einer oder mehreren Kanten verbunden. Mathematisch gesprochen besteht der Graph aus mehreren Zusammenhangskomponenten. Große Zusammenhangskomponenten ermöglichen eine Vielzahl von Zügen und machen ein Schiebespiel interessant. Aus wie vielen Knoten bestehen die größten Zusammenhangskomponenten? Bei anspruchsvollen Geduldspielen ist die Situation meist folgendermaßen: Neben vielen kleinen Zusammenhangskomponenten (das sind Stellungen, von denen aus nur ganz wenige Züge möglich sind) gibt es meist eine einzige große Zusammenhangskomponente oder auch zwei oder vier Zusammenhangskomponenten exakt gleicher Größe. Im ersten Fall sind in der Regel waagerecht und senkrecht gespiegelte Stellungen in dieser Zusammenhangskomponente verbunden, bei zwei großen Komponenten nur ist nur eine Spiegelung (oder Drehung um 180 Grad) möglich, bei vier Komponenten gar keine.

Aufgabe 5: Wie groß ist der Durchmesser der größten Zusammenhangskomponente? Für den Durchmesser betrachtet man die jeweils kürzesten Wege zwischen zwei Knoten und sucht dann ein Paar von Knoten, für das dieser Abstand maximal ist. Dieses Paar entsprechen im betrachteten Schiebespiel zwei Stellungen, die als Start und eine Ziel den maximal möglichen Abstand haben und deshalb eine maximale Anzahl von Zügen benötigen. Damit finden wir komplizierte Aufgabenstellungen.

Der Zusammenhang zwischen der Größe eines zusammenhängenden Graphen und seinem Durchmesser ist nicht so einfach, wie man vermuten könnte. Zwar haben größere Graphen tendenziell einen größeren Durchmesser, aber es gibt auch relativ kleine Schiebespiele mit verblüffend großem Durchmesser.

Wegen der symmetrischen Form sowohl des Rahmens wie auch der konvexen Steine unterscheiden sich maximal entfernte Positionen eines Schiebespiels oft nur durch eine Drehung oder Spiegelung. Hier einige solche Aufgaben zum Nachspielen, beispielsweise mit dem Baukasten für mehr als 50 Schiebespiele.

Eine Variante  einfachen Schiebespiels von Hughes mit einer Spiegelung:

Viel komplizierter ist die Variante von Blockado mit einer Drehung um 180 Grad.

Bei der folgenden Variante des Happy Couple liegt die Symmetrie in der Vertauschung der beiden 2x2-Quadrate:

Variationen am Trapez

Verschiedene Drahtpuzzles unterscheiden sich gelegentlich nur in Details. Dadurch sehen die Geduldspiele verschieden aus. Die Lösungsschritte können für solche Geduldspiele völlig gleich oder total verschieden sein. Das klassische solche  Paar sind die erste Variante des Geduldspiels Figure Eight (leicht lösbar) und die zweite Variante desselben Geduldspiels (unlösbar).

Hier wollen wir ein Teil eines klassischen Drahtpuzzles betrachten, dass öfters vorkommt und deshalb auch öfters variiert wird: das Trapez. Die bekannteste Verwendung ist bei der Herzbefreiung, hier hängt ein Herz im Trapez. Das wichtigste Teil des Herzen ist seine Zunge, die relativ lang ist und dünn genug, dass sie durch alle Ösen des Trapezes gesteckt werden kann. In den Abbildungen unten wird deshalb nur die Zunge als langegezogener Ring verwendet. 

Sie können diese Zunge aus dem Trapez befreien, wenn Sie genauso wie bei der Herzbefreiung vorgehen. Der wichtigste Schritt ist, die Zunge von Innen durch eine Öse des U-förmigen Teils zu schieben und über das äußere Ende der Trapezstange zu heben.

Jetzt wollen wir die Form des Trapezes vorsichtig ändern, so dass die Lösungsschritte fast gleich bleiben können. Und zwar verlängern wir die Trapezstange und biegen die Enden in einem Bogen nach innen. Die Enden versehen wir mit jeweils einem Haken und verschließen die beiden Haken durch einen Ring. Der Ring sollte locker sitzen, aber nicht abzuziehen sein. Außerdem sollte (wie immer) die Zunge (wenigstens von einer Seite) durch den Ring geschoben werden können. Dann haben wir unsere veränderte Trapezstange und können das U-förmige Teil zusammen mit der Zunge in den oberen oder unteren Teil der zusammengebogenen Trapezstange einhängen. Und fertig sind zwei neue Geduldspiele: Die Zunge kann befreit werden!

Und beide Geduldspiele gibt es auch wirklich: Satan's Stirrup und als Racing Wire Puzzle #3.

Ergänzung 03/2024:

Es gibt noch eine weitere Möglichkeit: Die durch den Ring verbundenen Haken können auch nach innen gebogen werden:

Auch dieses Geduldspiel gibt es unter dem Namen Master's Puzzle C oder auch Big Slick. Die Lösung ist sehr ähnlich.

Rektifizierung mit Polyominos

Wörtlich übersetzt heißt Rektifizierung "Verrechreckigung": Die Aufgabe besteht darin, ein Rechteck mit lauter identischen Steinen zu füllen, und als Steine sollen Polyominos benutzt werden. Wir müssen unsere Aufgabenstellung allerdings noch etwas genauer formulieren:

Gegeben sei ein bestimmtes Polyomino. (Wir werden uns weiter unten die Pentominos genauer ansehen.) Rechtecke welcher Größe lassen sich mit der passenden Anzahl von Exemplaren dieses Polyominos vollständig füllen? Falls es überhaupt ein solches Rechteck gibt, heißt das Polyomino rektifizierbar. In diesem Fall wollen wir uns natürlich für "alle" Rechtecke interessieren, die sich damit füllen lassen. Und auch diese Fragestellung müssen wir noch genauer spezifizieren. Bekannt wurde diese Fragestellung durch Martin Gardner [1], im englischen Original ab 1965.

Für ein gegebenes Polyomino kann die Fragestellung nach der Rektifizierbarkeit leicht zu beantworten sein, für andere ist es schwierig. Beispielsweise ist es einfach zu sehen, dass man Rechteck genau dann mit I-Pentominos füllen kann, wenn eine Seitenlänge ein Vielfaches von fünf ist: Diese Bedingung ist notwendig, weil die Gesamtfläche durch fünf teilbar sein muss und fünf eine Primzahl ist. Andererseits ist diese Bedingung auch hinreichend, weil sich das Rechteck mit gleich orientierten I-Pentominos füllen lässt, die alle auf der durch fünf teilbaren Seite „liegen“. Wir interessieren uns dann oft für das kleinste Rechteck (oder die kleinsten Rechtecke, falls es mehrere mit verschiedenen Seitenverhältnissen gibt), welches gefüllt werden kann. Beim I-Pentomino ist dies trivialerweise das 1x5-Rechteck und wir benötigen nur einen Stein. In vielen Fällen reichen zwei (beim L-  und P-Pentomino, jeweils für das 2x5-Rechteck) oder maximal vier Steine (beim T-Tetromino für das 4x4-Quadrat).

Hier ein Negativ-Beispiel: Mit mehreren X-Pentominos lässt sich niemals ein Rechteck füllen, da die Elementarquadrate in den Ecken des großen Rechtecks niemals durch ein X-Pentomino überdeckt werden können. Das X-Pentomino ist damit nicht rektifizierbar.

Doch zurück zu den rektifizierbaren Polyominos. Wenn wir für ein solches Polyomino ein füllbares Rechteck gefunden haben, dann können wir mehrere solche Rechtecke zu einem größeren zusammenfügen wie oben für das I-Pentomino erklärt. Umgekehrt kann man derartige größere Rechtecke in kleinere zerschneiden. Interessant ist der Fall der kleinsten solchen Rechtecke, die sich nicht weiter zerschneiden lassen. Solche Rechtecke heißen prime Rechtecke. Dieser Begriff lehnt sich an den Begriff der Primzahl an, die ebenfalls nicht weiter in ein Produkt kleinerer natürlicher Zahlen zerlegt werden können.

Betrachten wir also die etwas komplizierteren Fälle von rektifizierbaren Polyominos mit etwas komplizierteren primen Rechtecken. Wenn wir eine solche nichttriviale Rektifizierung gefunden haben, dann lässt sich daraus sofort ein Puzzle erzeugen, bei dem die entsprechend vielen identischen Bausteine in den vorgegebenen rechteckigen Rahmen eingeordnet werden sollen.

Für die einzelnen Tetrominos und Pentominos sieht die Situation folgendermaßen aus:

Rektifizierung der Tetrominos

Auf einfache Weise rektifizierbar (mit 1, 2 oder 4 Steinen) sind die folgenden Tetrominos: I, L O und T.
Nicht rektifizierbar ist das Z: Sie versuchen, die linke obere Ecke zu überdecken. Dazu gibt es (bis auf Spiegelung an der Hauptdiagonale) nur eine Möglichkeit. Danach kümmern Sie sich um den oberen Rand (von links nach rechts) und den linken Rand (von oben nach unten). Jeweils gibt es nur eine Möglichkeit, den nächsten Stein anzufügen. Die Eckfelder rechts oben und links unten können Sie so niemals überdecken. Damit ist das Z-Tetromino nicht rektifizierbar.

Rektifizierung der Pentominos 

Auf einfache Weise rektifizierbar (mit 1, 2 oder 4 Steinen) sind die Pentominos I, L und P. Dagegen sind die folgenden Pentominos nicht rektifizierbar: F, N, T, U, V, W, X und Z. Die Begründungen sind ähnlich wie beim Z-Tetromino.

Es bleibt das Y-Pentomino. Es wurde schon bei den allgemeinen Packproblemen mit dem Y-Pentomino verraten, dass sich ein 5x10-Quadrat aus 10 Y-Pentominos legen lässt. Dies ist nicht das einzige prime Rechteck. Hier ist die vollständige Liste der primen Rechtecke, zusammengestellt von Michael Reid [2]. Sie ist zeilenweise geordnet nach der Länge der kürzeren Seite:

• 5 × 10
• 9 × 20, 9 × 30, 9 × 45, 9 × 55
• 10 × 14, 10 × 16, 10 × 23, 10 × 27
• 11 × 20, 11 × 30, 11 × 35, 11 × 45
• 12 × 50, 12 × 55, 12 × 60, 12 × 65, 12 × 70, 12 × 75, 12 × 80, 12 × 85, 12 × 90, 12 × 95
• 13 × 20, 13 × 30, 13 × 35, 13 × 45
• 14 × 15
• 15 × 15, 15 × 16, 15 × 17, 15 × 19, 15 × 21, 15 × 22, 15 × 23
• 17 × 20, 17 × 25
• 18 × 25, 18 × 35
• 22 × 25

Das klingt nach einer großen Menge von Geduldspielen. Speziell beschäftigen wollen wir uns mit den Größen 15x15 und 25x25. Auch nicht-prime Rechtecke  (wie 25x25) können interessant sein, deshalb soll auch auf die Aufstellung "aller" möglichen Rechtecke zusammen mit vielen weiteren Aufgaben von Torsten Sillke [3] hingewiesen werden.

Übrigens gibt es zum zweidimensionalen Rektifizierungsproblem auch eine dreidimensionale Variante: Ein Würfel oder allgemeiner, ein Quader soll mit identischen Bausteinen gefüllt werden. Die Bausteine werden hier aus Elementarwürfeln zusammengesetzt. Dafür wird es noch einen eigenen Post geben.

Rektifizierung von Hexominos, Heptominos und noch größeren Polyominos

Auch mit größeren Polyominos bleibt die Rektifizierung spannend. Es gibt immer einige Steine, für die man relativ große Rechtecke für die Rektifizierung benötigt. Eine schöne Zusammenstellung der aufregenden Fälle findet man bei Andrew Clarke [4].

Quellen

[1] Martin Gardner: Mathematische Hexereien, Kapitel 13. Ullstein-Verlag 1988

[2] Michael Reid: https://cflmath.com/Polyomino/y5_rect.html

[3] Torsten Sillke: https://www.math.uni-bielefeld.de/~sillke/PENTA/qu5-y

[4] Andrew Clark: PolyPages