Journal
VISUAL COMPUTER
Volume 37, Issue 4, Pages 777-787Publisher
SPRINGER
DOI: 10.1007/s00371-020-01968-5
Keywords
Computational design; Graph partitioning; Puzzles
Categories
Funding
- JSPS KAKENHI [19K24338, 20K19944]
- Grants-in-Aid for Scientific Research [20K19944, 19K24338] Funding Source: KAKEN
Ask authors/readers for more resources
This paper introduces a computational approach for designing geometric puzzles that differs from existing methods by using a top-down partitioning approach, allowing control and editing of piece shapes instead of automatic generation. The proposed algorithm can be easily extended to both 3D polycube and 2D polyomino puzzle design, demonstrating versatility and innovation in puzzle design.
People of all ages enjoy solving geometric puzzles. However, finding suitable puzzles, e.g., puzzles with a moderate level of difficulty or puzzles with intellectually stimulating shapes can be difficult. In addition, designing innovative and appealing puzzles requires demanding effort and, typically, involves many trial and error processes. In this paper, we introduce a computational approach for designing geometric puzzles. Existing approaches employ bottom-up, constructive algorithms to generate puzzle pieces; therefore, intervening in the piece generation procedure is difficult. Differing from existing approaches that generate puzzles automatically or semi-automatically, we propose a top-down, partitioning-based approach, that enables us to control and edit piece shapes. With a subtle modification, the proposed algorithm can be easily extended to both 3D polycube and 2D polyomino puzzle design. To generate a variety of piece shapes, the proposed approach involves a capacity-constrained graph partitioning algorithm combined with polyomino tiling. We demonstrate the versatility of the proposed approach through various example designs, including fabricated puzzles, created using the proposed method.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available