research-article

Computational design of high-level interlocking puzzles

Authors:

Rulin Chen,

Ziqi Wang,

Peng Song,

Bernd BickelAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 41, Issue 4

Article No.: 150, Pages 1 - 15

https://doi.org/10.1145/3528223.3530071

Published: 22 July 2022 Publication History

Get Access

Abstract

Interlocking puzzles are intriguing geometric games where the puzzle pieces are held together based on their geometric arrangement, preventing the puzzle from falling apart. High-level-of-difficulty, or simply high-level, interlocking puzzles are a subclass of interlocking puzzles that require multiple moves to take out the first subassembly from the puzzle. Solving a high-level interlocking puzzle is a challenging task since one has to explore many different configurations of the puzzle pieces until reaching a configuration where the first subassembly can be taken out. Designing a high-level interlocking puzzle with a user-specified level of difficulty is even harder since the puzzle pieces have to be interlocking in all the configurations before the first subassembly is taken out.

In this paper, we present a computational approach to design high-level interlocking puzzles. The core idea is to represent all possible configurations of an interlocking puzzle as well as transitions among these configurations using a rooted, undirected graph called a disassembly graph and leverage this graph to find a disassembly plan that requires a minimal number of moves to take out the first subassembly from the puzzle. At the design stage, our algorithm iteratively constructs the geometry of each puzzle piece to expand the disassembly graph incrementally, aiming to achieve a user-specified level of difficulty. We show that our approach allows efficient generation of high-level interlocking puzzles of various shape complexities, including new solutions not attainable by state-of-the-art approaches.

Supplemental Material

MP4 File

supplemental material

Download
92.57 MB

MP4 File

presentation

Download
179.21 MB

ZIP File - Repository for "Computational Design of High-level Interlocking Puzzles" (SIGGRAPH 2022 Journal Track Paper)

This repo presents a computational approach to design high-level interlocking puzzles. We have implemented our computational design tool in C++ and libigl [Jacobson et al. 2018] on a desktop computer with 3.6 GHz 8-Core Intel processor and 16 GB RAM. More information available on GitHub at https://github.com/Linsanity81/High-LevelPuzzle

Download
175.88 MB

SRT File

presentation

Download
13.44 KB

ZIP File

supplemental material

Download
41.79 MB

References

[1]

Maneesh Agrawala, Doantam Phan, Julie Heiser, John Haymaker, Jeff Klingner, Pat Hanrahan, and Barbara Tversky. 2003. Designing Effective Step-By-Step Assembly Instructions. ACM Trans. on Graph. (SIGGRAPH) 22, 3 (2003), 828--837.

Abstract

Supplemental Material

References

Cited By

Index Terms

Recommendations

Recursive interlocking puzzles

Computational design of polyomino puzzles

Computational design of generalized centrifugal puzzles

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations