14.6.25

Eternity II

Eternity II ist der Nachfolger des legendären Puzzles Eternity. Wieder müssen viele Teile aneinandergefügt werden und wieder ging es um einen großen Preis für den Ersten, der das Geduldspiel vollständig löst.

Diesmal handelt es sich um ein ganz gewöhnliches Legespiel mit quadratischen Karten, die an jeder Kante ein Muster tragen. Die Karten müssen so zusammengelegt werden, dass jeweils zwei gleich gemusterte Karten zusammenstoßen. Das kennen wir von Legespielen der Größe 3x3, manchmal auch etwas größer bis zu 6x6, siehe die Übersichtsseite zu Legespielen. Vergleichsweise dazu ist dieses Puzzle gigantisch, es hat die Größe 16x16 mit 16*16=256 Karten. Zwar gibt es außen einen eine spezielle Randfarbe für die Kanten, aber das macht die Aufgabenstellung nicht wesentlich einfacher. Die 256 Steine sind alle verschieden, keiner der Steine ist rotationssymmetrisch. Zusätzlich ist im Inneren des Feldes die Position eines Steines vorgegeben (auf dem Feld I8). Auf dem folgenden Foto wird in einem Ausschnitt demonstriert, wie sich Steine anlegen lassen.

Eternity II wurde ebenso wie schon Eternity von Christopher Monckton entwickelt [1], dabei halfen Alex Selby and Oliver Riordan. Diese beiden Mathematiker hatten das erste Eternity-Puzzle erfolgreich gelöst und sollten hier eine angemessene Schwierigkeit sicherstellen. Für die erste Lösung des gesamten Puzzles wurde ein Preis von 2 Millionen Pfund ausgesetzt, allerdings nur, wenn die Lösung 31.12.2010 gefunden wurde. Dies ist nicht passiert, so dass der Preis verfallen ist. Auch bis heute ist keine Lösung bekannt, man kann also immer noch berühmt werden, auch wenn es kein Preisgeld gibt. 

Auch wenn wir den Computer hinzuziehen, lässt sich das Puzzle heute nicht lösen. Ein reines Computerprogramm (ohne menschliche Unterstützung) gibt es beispielsweise bei [2]. Bei einem Probelauf wurden nach mehreren Stunden 214 der 256 Steine korrekt eingeordnet:

Derartige Spielstände lassen sich mit Hilfe von https://e2.bucas.name/ [3] einfach visualisieren.

Wie ist der Stand im Jahr 2025? Das Geduldspiel kann "fast" gelöst werden, bei den allerletzten Steinen klappt es aber bisher nicht. Deshalb kann man die letzten Steine "so gut wie möglich" einfügen und dann zählen, bei wie vielen Kanten die Übereinstimmung fehlt. Bei einem Wert von 0 hätte man eine perfekte Lösung. Die momentan beste Lösung stammt von Joshua Blackwood, der Wert liegt bei 10. Die fehlerhaften Stellen sind im Bild markiert.

Es gibt auch ein Forum für Eternity II, welches die neuesten Informationen enthält [4].

Design:  Christopher Monckton
Hersteller:  Ertl Europe Company
Erscheinungsjahr: 2007

Google: eternity puzzle
Shopping: Gelegentlich gebraucht lieferbar, Preis ca. 20€


Das verflixte Gaudispiel

Kategorie: Quadratische 3x3-Legespiele

Wieder ein typisches 3x3-Anlegespiel mit Schweinen. Wie schon beim Anlegespiel Lass den Schweinkram stammt die Illustration von Klaus Oliv (Clov). Neun Karten mit jeweils vier Schweinehälften sind an jeder gemeinsamen Kante passend zu je einem der vier verschiedenen Schweine (Arme, Blickrichtung und Füße müssen zusammenpassen) zu einem 3x3-Quadrat zusammenzufügen. Auf den Rändern der Karten sind jeweils zwei Ober- und zwei Unterteile nebeneinander abgebildet, die Karten sind also orientiert. 


Schwierigkeit: Mittelschwer, da es keine orientierte Lösung gibt. Es gibt nur zwei Lösungsmöglichkeiten.

Hersteller:  Heye-Verlag
Erscheinungsjahr: 1997
Illustrator: Klaus Oliv (Clov)

Google: Heye verflixte Gaudispiel
Shopping: Selten gebraucht lieferbar.


Technischer Steckbrief:
3x3 Edge Matching Puzzle

Das verflixte
Gaudispiel 

Karten doppelt vorhanden? 1 Paar
Orientiertheit der Karten ja
Anzahl Lösungen 2
davon orientiert -
Anzahl Karten mit 4 Figuren 5
Anzahl Karten mit 3 Figuren 4
Anzahl Karten mit 2 Figuren 0
Schwierigkeit [*] 4893
Fingerabdruck [*] ABCD-ABCD-ABCb-AbBd-AdBc-AdCb-BacD-Dbda-abcd

[*] Schwierigkeit und Fingerabdruck wurden mit dem Online-Solver von A. Keilhauer berechnet.


11.6.25

Mehrere gleiche oder ähnliche Figuren aus einem Satz Polyominos legen

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:

Mehr Infos

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

Hexominos und Trominos in 6 Rahmen 6x6

Nimmt man zu den 35 Hexominos noch die zwei Trominos hinzu, so belegen diese 36*6+2*3 = 216 Elementarquadrate. Lässt sich daraus ein 18x12-Rechteck legen? Ja, aber diese Aufgabe ist uns heute viel zu einfach. Wir fragen uns: Lassen sich sechs Quadrate der Größe 6x6 mit den gegebenen Steinen füllen? Falls ja, brauchen wir diese 6 großen Quadrate nur in einem Rechteck der Größe 3x2 anzuordnen und fertig ist das 18x12-Rechteck mit einer sehr eleganten Unterteilung.

Um eine Lösung zu finden, gehen wir folgendermaßen in zwei Schritten vor, wie allgemein beschrieben, um mehrere gleiche oder ähnliche Figuren aus einem Satz Polyominos legen.

Für die erste Teilaufgabe erzeugen wir die Liste aller Lösungen für jeden einzelnen Rahmen. Da alle sechs Rahmen gleich sind, ergibt das nur eine Liste, die sich beispielsweise einfach mit mops.exe erzeugen lässt. Zuerst benötigt mops.exe die Steinmenge aus Trominos und Hexominos. Das geht am einfachsten, indem man zunächst die Hexominos als Steinmenge erzeugt und abspeichert. Danach erzeugt man die Trominos und lädt die Hexominos dazu. Damit verfügt man über die 37 Steine.

Als Rahmen (pattern) nimmt man ein 6x6-Quadrat und sucht nach allen Lösungen (>pack>all solutions). Dabei werden 2.574.456 Lösungen gefunden und diese werden automatisch abgespeichert. Danach wird die Liste mit einem kleinen Skript umformatiert, dass nur noch die Steinnummern enthalten sind und diese innerhalb der Zeile sortiert sind. Dann wird diese Liste zeilenweise sortiert und Dubletten werden entfernt (sort -u). Danach liegt die Liste L vor. Sie hat 84.614 Einträge.

Aus dieser Liste L erstellen wir nun die 6 Listen L1 bis L6 für die sechs Rahmen. Wir können ohne Beschränkung der Allgemeinheit die beiden Trominos in den ersten Rahmen packen, denn beide Trominos müssen ja in denselben Rahmen. Damit besteht L1 aus allen Einträgen von L, welche die Trominos enthalten, dies sind 70.904 Zeilen. Die Listen L2 bis L6 sind identisch und bestehen aus dem Rest von L, nachdem L1 entfernt wurde. Sie enthalten jeweils 13.710 Zeilen.

Für die zweite Teilaufgabe werden die Listen in eine logische Formel umgesetzt, für die später nach einer Lösung gesucht wird. Dies passiert genau wie in diesem Post beschrieben. Die Namen der Steine werden als Variablen betrachtet und ein langer logischer Ausdruck wird exakt genauso konstruiert:

(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)

Diesen Ausdruck übergeben wir dem SMT-Solver Z3 und hoffen, dass er in vertretbarer Zeit eine Lösung findet. Wenn wir die Größe des Ausdrucks betrachten, dann besteht er aus 768.174 UND-Verknüpfungen (jede ODER-Zeile hat weitere 5 bzw. 6 UND-Verknüpfungen) und 139448 ODER-Verknüpfungen mit 37 Variablen. Wir haben zunächst keinerlei Vorstellungen, ob die Laufzeit einige Minuten, einige Tage oder gar Jahre betragen wird. Versuchen wir, es herauszufinden: Wir starten den Versuch auf einem normalen PC und binnen einiger Minuten und auch Stunden passiert erst einmal gar nichts. Aber nach knapp drei Tagen Laufzeit kommt die erste Lösung. Hier die Nummern der Rahmen für die 37 Steine.

1 1 1 5 3 4 5 6 3 3 2 4 1 4 2 2 6 3 6 5 3 6 5 4 6 1 2 2 6 5 2 3 1 4 4 5 1 

Dies bedeutet: Stein Nummer 1 erscheint im Rahmen1, ebenso die Steine 2 und 3. Stein Nummer 4 erscheint in Rahmen 5, Stein Nr. 5 in Rahmen 3 usw. Nach weiteren knapp 2 Tagen gibt es eine weitere Lösung 

1 1 2 2 4 6 5 5 2 6 1 4 3 5 5 2 3 5 6 3 6 4 5 1 1 3 2 6 3 4 2 3 4 6 1 4 1

und gleich darauf eine dritte, die allerdings nur die Steine in den Rahmen 2 und 4 vertauscht. Danach wurde der Prozess abgebrochen.

Um diese Nummern in eine echte Lösung für die sechs Rahmen zu verwandeln, müssen wir noch einmal die vergleichsweise einfache Aufgabe lösen, die Steine tatsächlich in den entsprechenden Rahmen zu packen. Hier ist das Ergebnis für die erste Lösung:

Historisches: Die Aufgabe wurde 1999 von Michael Reid gestellt. Da wusste man schon, dass es nicht möglich ist, sechs Rahmen der Größe 6x6 mit den 35 verschiedenen Hexominos sowie einem weiteren, doppelt verwendeten Hexomino zu füllen. Deshalb vermutet man nur vergleichsweise wenige Lösungen für die gestellte Aufgabe. Die erste Lösung wurde von Patrick Hamlyn gefunden [1] 

Mehr Infos:

[1] https://www.mathpuzzle.com/6x6x6.html

8.6.25

Puzzlebox aus Klemmbausteinen: Rainbow Road

Kategorie: Trickboxen

Dies ist eine Puzzlebox zum Selberbauen: Aus 233 Klemmbausteinen muss zunächst die kleine Puzzlebox der Größe 8.2cm x 6.8cm x 4.8cm mit Hilfe einer ausgezeichneten Bauanleitung zusammengebaut werden. 

Danach hat man eine Trickbox mit einem ziemlich vertrackten Mechanismus vor sich. Zuerst findet man das Türchen mit einer Kurbel darin. 

Damit lassen sich innenliegende Zahnräder bewegen, und später lassen sich verschiedene Teile der Box verschieben, bis sich zum Schluss der Deckel öffnet. 

Schwierigkeit: Wenn man die Box selbst zusammengebaut hat, hat man bereits einige Vorstellungen, wo sich bewegliche Teile befinden. Trotzdem wird man noch seine Freude an der Box haben. Wenn Sie die Box gleich im zusammengebauten Zustand in die Hand bekommen, ist die Lösung noch spannender. Allerdings besteht immer die Gefahr, dass sich ungewollt Steine lösen und so nicht vorgesehene Bewegungen möglich werden oder die Box ganz zerbricht. Etwas Vorsicht ist also angebracht.

Ähnliche Geduldspiele: Es gibt weitere Puzzleboxen aus Klemmbausteinen, die ähnlich funktionieren. Geeignet für alle Freunde von Lego-Modellen, da schon der Zusammenbau eine anspruchsvolle Herausforderung darstellt und dabei viel Spaß macht.

Google: rainbow road puzzle box
Shopping: Lieferbar, Preis 15-30€

Karakuri Small Box #2

Kategorie: Trickboxen

Die Karakuri Creation Group ist ein Zusammenschluss japanischer Puzzlebox-Designer, die neue Trickkisten entwerfen und in hervorragender handwerklicher Qualität herstellen. Für jede solche Box muss der versteckte Mechanismus herausgefunden werden und die Box geöffnet.

Die kleine Trickbox hat eine Größe von nur 5.8cm x 4.6cm x 4.2cm und sieht aus wie ein kleiner, massiver Holzklotz. Zwar sind die sechs Außenwände einzeln erkennbar, aber man findet keine beweglichen Teile. Ober- und Unterseite der Box sind in einen Rahmen aus den Seitenwänden eingelassen, es gibt keinerlei Spalten. 

Anders als bei den Himitsu Bako-Trickkisten gibt es hier wirklich keine Schieber oder Riegel, die parallel verschoben werden müssen.

Schwierigkeit: Die Karakuri Box bleibt für eine längere Zeit völlig rätselhaft. Nichts bewegt sich oder klappert. Wenn Sie die erste Veränderung an der Box erreicht haben, gibt es einen schönen Aha-Effekt und es ist nicht mehr weit zum Ziel.

Leider können wir hier kein Bild der geöffneten Kiste zeigen, ohne zu viel zu verraten.

Ähnliche Trickboxen: In der Serie der Karakuri Small Boxen gibt es mittlerweile schon 8 Kistchen, und einige davon in mehreren Varianten aus verschiedenen Hölzern [1].

Design:  Karakuri Creation Group
Hersteller:  Karakuri Creation Group
Erscheinungsjahr: 2004

Google: Karakuri Small Box 2
Shopping: Lieferbar, Preis ca.60€

Mehr Infos: 
[1] https://www.puzzle-place.com/wiki/Category:Karakuri_Small_Boxes

7.6.25

Der Kreuz-Schlüssel

Aus nur vier Teilen soll ein Kreuz gelegt werden wie auf der Verpackung abgebildet. 

Schwierigkeit: Einfach, da nur vier Teile zusammen gelegt werden müssen.

Noch schwieriger wäre es gewesen, wenn an den Schnittkanten in der Mitte auch vier rechte Winkel aufeinandertreffen würden.

Design:  Bartl
Hersteller:  Bartl Minipuzzle Nr. 2285

Google: Bartl Kreuz-Schlüssel 
Shopping: Lieferbar, Preis ca. 3€.


Das Quadrat-Puzzle

Aus sieben Teilen soll ein Quadrat gelegt werden. Bei dem Geduldspiel handelt es sich um eine kleine Variante des Tangram. Viele weitere Informationen finden Sie bei den anderen Versionen des Tangram.

Design:  klassisch
Hersteller:  Bartl Minipuzzle Nr. 2077 und andere Hersteller.

Google: Bartl Quadrat-Puzzle 
Shopping: Lieferbar, Preis ca. 3€.


4.6.25

Übersicht: Symmetriepuzzles

Hier finden Sie alle systematischen Übersichten.

Symmetriepuzzles funktionieren anders als die meisten Geduldspiele: Man hat nur wenige Steine vor sich (meist zwei, drei oder vier) und soll daraus eine symmetrische Form legen, so dass alle Steine flach auf dem Tisch liegen und sich nicht überlappen. Anders als sonst kennt man die zu legende Form nicht, sondern man weiß nur, dass sie symmetrisch ist. Meist wird auch nicht gesagt, ob spiegelsymmetrisch oder rotationssymmetrisch. 

 Typen und Lösungsstrategien

Die meisten Symmetriepuzzles bestehen aus Steinen, die entsprechend eines Gitters angeordnet sind, und auch die Lösung soll gitterkonform sein. Meist handelt es sich um das übliche Quadratgitter, auch Dreiecks- oder Sechseckgitter sind möglich. Manchmal erkennt man das Gitter nicht sofort, aber trotzdem lohnt es sich, danach zu suchen. 
Symmetriepuzzles sind oft schwierig. Besonders schwierig ist es, alle Lösungen zu finden. Hier kann der Computer helfen.

Symmetriepuzzles auf dem Quadratgitter

Wegen der Vertrautheit mit dem Quadratgitter sind diese Symmetriepuzzles scheinbar einfacher als andere. Die Steine sind klassische Polyominos. Trotzdem sind hier einige recht schwere Puzzles dabei.

Foto von 
nothingyetdesigns.com  

Symmetriepuzzles auf anderen Gittern

Hier bestehen die Steine aus Dreiecken oder Sechsecken.
  • (Demnächst mehr.)


Puzzles mit scheinbar unregelmäßigen Steinen

Man erkennt kein zugrundeliegendes Gitter, und vielleicht ist auch keines vorhanden. 

Shinobi

Dieses Symmetrie-Puzzle besteht aus drei Hexominos.

Aus diesen drei Hexominos soll eine flache symmetrische Figur gelegt werden, ohne dass die Steine sich irgendwie überlappen.

Foto von nothingyetdesigns.com mit freundlicher Genehmigung

Die Steine sind aus lasergeschnittenem Acryl.

Der Name Shinobi weist auf Meister der Ninja-Kampfkunst hin: Als Meister hat man den Test nur bestanden, wenn man beide Lösungen findet. Eine Lösung reicht allerdings zum Überleben... (So ähnlich steht es wenigstens auf der Seite des Designers [1].)

Es gibt demzufolge zwei verschiedene Lösungen. Können Sie beide finden?

Schwierigkeit: Verblüffend schwierig. 

 

Design:  Greg Gelf (Puzzle Wanderer)
Hersteller:  NothingYet Designs

Shopping: Lieferbar, Preis ca. 5€

Mehr Infos:

Amoeba / Amöbe

Dieses Symmetrie-Puzzle besteht aus drei Hexominos.

Aus diesen drei Hexominos soll eine flache symmetrische Figur gelegt werden, ohne dass die Steine sich irgendwie überlappen.

Foto von nothingyetdesigns.com mit freundlicher Genehmigung

Die Steine sind aus lasergeschnittenem Acryl.

Es gibt zwei verschiedene Lösungen. Können Sie beide finden?

Schwierigkeit: Verblüffend schwierig. Der Name deutet schon darauf hin, dass die Lösungen etwas unförmig sind.

 

Design:  Alexander Magyarics
Hersteller:  NothingYet Designs

Shopping: Lieferbar, Preis ca. 5€

Horton's Wire Puzzles No. 70: Ein Seilpuzzle

Perry Horton hat in seine Reihe Horton's Wire Puzzles später auch einige Seilpuzzles aufgenommen, hier eines davon:  Wieder ei...