--- res: bibo_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.\r\n\r\nIn 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.@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Rulin foaf_name: Chen, Rulin foaf_surname: Chen - foaf_Person: foaf_givenName: Ziqi foaf_name: Wang, Ziqi foaf_surname: Wang - foaf_Person: foaf_givenName: Peng foaf_name: Song, Peng foaf_surname: Song - foaf_Person: foaf_givenName: Bernd foaf_name: Bickel, Bernd foaf_surname: Bickel foaf_workInfoHomepage: http://www.librecat.org/personId=49876194-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0001-6511-9385 bibo_doi: 10.1145/3528223.3530071 bibo_issue: '4' bibo_volume: 41 dct_date: 2022^xs_gYear dct_identifier: - UT:000830989200018 dct_isPartOf: - http://id.crossref.org/issn/0730-0301 - http://id.crossref.org/issn/1557-7368 dct_language: eng dct_publisher: Association for Computing Machinery@ dct_title: Computational design of high-level interlocking puzzles@ ...