期刊
ACM TRANSACTIONS ON GRAPHICS
卷 41, 期 4, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3528223.3530071
关键词
interlocking puzzle; level of difficulty; disassembly planning; computational design
资金
- SUTD Start-up Research Grant [SRG ISTD 2019 148]
- Swiss National Science Foundation (NCCR Digital Fabrication) [51NF40-141853]
- European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme [715767 -MATERIALIZABLE]
This paper presents a computational approach to design high-level interlocking puzzles. The core idea is to use a rooted, undirected graph called a disassembly graph to represent all possible configurations of an interlocking puzzle as well as transitions among these configurations, and leverage this graph to find a disassembly plan. The algorithm iteratively constructs the geometry of each puzzle piece to expand the disassembly graph incrementally, aiming to achieve a user-specified level of difficulty.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据