Computational design of polyomino puzzles
Computational design of polyomino puzzles
复制标题
DOI：
10.1007/s00371-020-01968-5
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Naoki Kita;K. Miyata
中科院分区：
文献类型：
--
作者：
Naoki Kita;K. Miyata
所有年龄段的人都喜欢解决几何难题。然而，找到合适的谜题，例如中等难度的谜题或具有智力刺激形状的谜题可能很困难。此外，设计创新且有吸引力的谜题需要付出艰巨的努力，并且通常涉及许多试错过程。在本文中，我们介绍了一种设计几何谜题的计算方法。现有的方法采用自下而上的构造性算法来生成拼图。因此，干预件生成过程是很困难的。与自动或半自动生成拼图的现有方法不同，我们提出了一种自上而下、基于分区的方法，使我们能够控制和编辑拼图形状。通过细微的修改，所提出的算法可以轻松扩展到 3D 多维立方体和 2D 多骨牌拼图设计。为了生成各种块形状，所提出的方法涉及容量受限的图分区算法与多骨牌平铺相结合。我们通过各种示例设计（包括使用所提出的方法创建的制作谜题）展示了所提出方法的多功能性。
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.