Computational design of polyomino puzzles
- PDF / 3,224,632 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 9 Downloads / 261 Views
ORIGINAL ARTICLE
Computational design of polyomino puzzles Naoki Kita1
· Kazunori Miyata2
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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 capacityconstrained 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. Keywords Computational design · Graph partitioning · Puzzles
1 Introduction Puzzles have fascinated people all over the world for centuries. Solving puzzles requires logical thinking and inspiration, and both children and adults enjoy puzzles. Geometric puzzles, such as polyomino tiling, involve assembling and disassembling a set of geometrically-shaped pieces. Even if the assembled silhouette forms a simple shape, the sequence of steps required to solve a geometric puzzle is not always straightforward, i.e., it is often more intricate than it first appears. The fun of puzzles is not limited to solving; people also enjoy collecting various types of puzzles or inventing new ones. While the solving process is usually enjoyable—although it sometimes demands patience—designing new puzzles is an intricate and difficult task for both novice and sophisticated puzzle designers. However, inventing new puzzles is important because; although users enjoy solving puzzles for the
B
Naoki Kita [email protected]
1
Tokyo University of Agriculture and Technology, Tokyo, Japan
2
Japan Advanced Institute of Science and Technology, Nomi, Ishikawa, Japan
first several attempts to solve a puzzle, they may lose interest once they have discovered the solution. In this paper, we present a computational method for designing polyomino (polycube) puzzles (Fig. 1). Several computational approaches for generating puzzles have been proposed; however, ours differs from previous methods, i.e., we focus on the controllability of each puzzle piece. Since previous approaches generate puzzle pieces automatically, it is difficult for users to design their desired piece shapes. In contras
Data Loading...
