Das perfekt verschachtelte 3D-Rätsel

Prämiertes Computerdesign und 3D-Druck von hochgradig verzahnten Puzzles.

Dreidimensionale Puzzles sind viel mehr als nur Denkspiele. Sie sind beeindruckende Beispiele für die vielfältigen Möglichkeiten des 3D-Drucks. Technologisch relevant ist das für elektromagnetischen Einheiten, Architektur und Robotermontage. Ein Team internationaler Computerwissenschafter:innen um den ISTA-Vizepräsidenten für Technologietransfer und Oscar-Preisträger Professor Bernd Bickel hat nun eine Toolbox veröffentlicht, mit der sich hochgradig verschachtelte Puzzles entwerfen lassen. Die Arbeit wurde auf der SIGGRAPH-Konferenz mit dem Technical Paper Award ausgezeichnet.

Verzahnte Puzzles sind verblüffende geometrische Spiele. Ihre Teile werden durch ihre geometrische Anordnung zusammengehalten, die auch verhindert, dass man sie auseinandernehmen kann. Eine spezielle Unterklasse dieser „Interlocking Puzzles“ hat dabei einen sehr hohen Schwierigkeitsgrad. Es sind mehrere Schritte nötig, um sie zu zerlegen. Und das ist eine herausfordernde Aufgabe, da man zahlreiche Konfigurationen erkunden muss, bis man einen Punkt erreicht, an dem das erste Stück freiliegt und herausgenommen werden kann. Eine noch größere Herausforderung ist aber das Design solcher Puzzles.

Ein Team von Forscher:innen der Singapore University of Technology and Design, der ETH Zürich und der École polytechnique fédérale de Lausanne (EPFL) in der Schweiz sowie des Institute of Science and Technology Austria (ISTA) stellen nun auf der SIGGRAPH-Konferenz ein Programm vor, um solche Puzzles mit der Rechenleistung von Computern zu erstellen. Der iterative und robuste Algorithmus ist für alle frei zugänglich, die ihr eigenes Puzzle entwerfen möchten. „Wir haben ein Toolkit entwickelt, mit dem sich hochgradig verschachtelte Puzzles nach den Wünschen der Benutzer:innen entwerfen lassen, einschließlich der Form, der Anzahl der Puzzleteile und des Schwierigkeitsgrads“, lädt Computerwissenschafter Rulin Chen die Community ein.

Die Lösung des Rätsels, wie man lösbare Rätsel erstellt

Stellen Sie sich vor, Ihr Lieblingstier wäre eine Eule. Das Computerprogramm würde die Eulenform als 3D-Gitter modellieren, das gleichmäßig in kleine Volumeneinheiten, so genannten Voxel, unterteilt ist (2D-Bildelemente werden bekanntlich Pixel genannt). Der Algorithmus garantiert, dass alle Puzzleteile die gleiche Größe haben und alle Voxel, die ein Puzzleteil bilden, miteinander verbunden sind. Außerdem verhindert er Konstruktionen, bei denen man ein Teil mit dem ersten Zug entfernen kann. Mit diesen Anforderungen im digitalen Hinterkopf beginnt der Algorithmus mit dem Entwerfen von Puzzleteilen innerhalb des „voxelisierten“ Gitters.

Einzelheiten des Algorithmus

1. Für das erste Stück wählt das Programm zufällig eine Bewegungsrichtung aus. Von allen möglichen Voxel, die sich bewegen lassen, aber durch den Rest der Struktur blockiert werden, wählt es zufällig eines aus, das so genannte Keimvoxel.
2. Wenn sich das Keimvoxel auch in eine andere Richtung bewegen kann, fügt das Programm dem Puzzlestück einen Blockiervoxel hinzu, so dass es sich nur in die gewünschte Richtung bewegen kann: Es verbindet das Startvoxel mit einem Voxel, das die unerwünschte Bewegung blockiert. Dafür inkludiert es alle Voxel auf dem kürzesten Weg zwischen Start- und Blockiervoxel.
3. Um eine praktische Stückgröße zu erreichen, wird der Voxelblock erweitert, jedoch so, dass die ersten beiden Schritte respektiert werden. Schließlich wird das Stück in die gewählte Richtung bewegt, und die Konstruktion eines neuen Stücks beginnt auf die gleiche Weise (Schritt 1-3).
4. Sobald die Form und die Größe der Teile festgelegt sind und der Schwierigkeitsgrad erreicht ist, werden die nicht verwendeten Voxel entfernt. Das Puzzle ist fertig, aber sein Aussehen kann noch verbessert werden.
5. Dieser optionale Schritt verbessert sowohl das Aussehen als auch „schwache“ Puzzlestücke. Ein schwaches Teil ist gekennzeichnet durch Voxel, die viel kleiner als die anderen sind. Ein solches Teil kann bei der Herstellung oder beim Spielen leicht brechen. Durch eine leichte Anpassung der Gesamtform können schwache Teile vermieden werden.

Der Algorithmus braucht nur sechs Minuten, um ein vierteiliges Kuhpuzzle mit dem Schwierigkeitsgrad 6 zu erstellen – das bedeutet, dass mindestens sechs Züge erforderlich sind, um das erste Teil zu entfernen. Für einen Würfel mit dem Schwierigkeitsgrad 27 braucht der Computer mehr als sechs Stunden.

Testlauf mit gedruckten Puzzles

Fast jede Form kann zum Puzzle werden, solange sie keine eingeschlossenen Volumina aufweist, so wie etwa Muscheln oder Bäume. Wenn das Puzzle weniger als acht Teile hat, bleibt die Komplexität des Problems und die Dauer der Erstellung überschaubar. „Natürlich funktioniert unser Projekt nicht nur in der Theorie. Wir haben verschiedene Puzzles in 3D gedruckt, um herauszufinden, wie schwierig es für Leute ist, sie zu lösen“, sagt Professor Bernd Bickel und scherzt: „Schnell war klar: die Puzzles sind echt knifflig. Und auch, dass das Eulenpuzzle mit Abstand als das niedlichste empfunden wird.“

Verschiedene Varianten von 3D-gedruckten, hochgradig ineinandergreifenden Puzzles. Die Form des Puzzles, die Anzahl der Teile und der Schwierigkeitsgrad können nach Belieben gewählt werden. © Rulin Chen et al.

Publikation

Rulin Chen, Ziqi Wang, Peng Song, und Bernd Bickel. 2022. Computational Design of High-Level Interlocking Puzzles. ACM Transactions on Graphics, Vol. 41, No. 4, Art. 150 (Proceedings of SIGGRAPH). DOI: 10.1145/3528223.3530071

Förderungen

Die Arbeit wurde durch den SUTD Start-up Research Grant SRG ISTD 2019 148, den Schweizerischen Nationalfonds (SNF) NCCR Digital Fabrication Agreement #51NF40-141853 und den European Research Council (ERC) Grant MATERIALIZABLE-715767 finanziert.

Medienkontakt:

Markus Feigl
markus.feigl@ista.ac.at
+43 664 8832 6393

Über das ISTA

Das Institute of Science and Technology Austria (ISTA) ist ein Forschungsinstitut mit eigenem Promotionsrecht. Das Institut beschäftigt Professor:innen nach einem Tenure-Track-Modell und Post-Doktorand:innen sowie PhD-Student:innen in einer internationalen Graduate School. Neben dem Bekenntnis zum Prinzip der Grundlagenforschung, die rein durch wissenschaftliche Neugier getrieben wird, hält das Institut die Rechte an allen resultierenden Entdeckungen und fördert deren Verwertung. Der erste Präsident ist Thomas Henzinger, ein renommierter Computerwissenschafter und vormals Professor an der University of California in Berkeley, USA, sowie der EPFL in Lausanne. Ihm folgt ab dem Jahr 2023 Martin Hetzer. www.ista.ac.at