August 9, 2022
Unlocking Interlocking Riddles
Award-winning computational design and 3D-printing of high-level interlocking puzzles
Three-dimensional puzzles are a lot more than just brain teasers. Such puzzles are showcasing the possibilities of digital fabrication of 3D-printed objects. Technological use cases include electromagnetic units, architecture and robotic assembly. A team of international computer scientists around ISTA’s Vice President for Technological Transfer and Oscar-winning professor Bernd Bickel now released a toolbox to design high-level interlocking puzzles on demand. The paper was honored with the Technical Paper Award at the SIGGRAPH conference.
Interlocking puzzles are mindboggling geometric games. Their pieces are held together by their geometric arrangement, which also prevents you from taking them apart. A special subclass of interlocking puzzles is high-level in regards of difficulty. The objects require multiple moves to become disassembled. And that is a challenging task since one has to explore numerous configurations until reaching a point, where the first piece is free to be taken out. In fact, even more challenging is the design of such puzzles.
A team of researchers from the Singapore University of Technology and Design, ETH Zurich and the École polytechnique fédérale de Lausanne (EPFL) in Switzerland, and the Institute of Science and Technology Austria (ISTA) now present at the SIGGRAPH conference a computational approach to create them. The novel iterative and robust algorithm is free to use for anyone, who is eager to conceive their own puzzle. “We have developed a toolkit for designing high-level interlocking puzzles according to the user’s wishes, including shape, number of puzzle pieces, and the level of difficulty,” invites computer scientist Rulin Chen the community.
Solving the riddle of creating solvable riddles
Imagine your favorite animal was an owl. The computer program would model the owl shape as a 3D grid equally partitioned into small unit volumes called voxels (remember that 2D picture elements are similarly called pixels). The algorithm guarantees that all puzzle pieces are of the same size and all voxels forming one piece of the puzzle are connected. This is ensures the stability of the piece. Additionally, it prohibits designs where you can remove a piece with the first move. Given these requirements, the digital construction starts by consecutively designing puzzle pieces within the voxelized grid.
It would take only six minutes to generate a 4-pieced cow puzzle with a difficulty level 6 – that means minimally six moves are required to remove the first piece. For a level 27 cube, the computer would spend more than 383 minutes to design it.
Testing the designs in real-life
Almost any shape can serve as input as long as it does not possess internal volumes like shells or trees. Also, keeping the number of pieces below eight will maintain a reasonable complexity of the problem, which the program can handle time-efficiently. “Of course, our project does not only work in theory. We 3D-printed various puzzles to find out how difficult it is for users to solve them,” says Professor Bernd Bickel and jokes, “We learned that it truly is very challenging and also, that the owl puzzle was by far considered the cutest.”
Rulin Chen, Ziqi Wang, Peng Song, and 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
The work was funded by the SUTD Start-up Research Grant SRG ISTD 2019 148, the Swiss National Science Foundation (SNSF) NCCR Digital Fabrication Agreement #51NF40-141853, the European Research Council (ERC) Grant MATERIALIZABLE-715767.