Computational Design of Polyomino Puzzles

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 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.

Results

Sword results

Sword results. Starting from a base tiling with 161 pieceess, we can create polyomino puzzles with fewer pieces.

Heart results

The composition and size of the base tile set can affest the final piece shapes. The size of the base tile represents the weights of the tiles (tiles with higher weights are more likely to be chosen in the tiling process). Tiles with equal weights are used in the two leftmost examples, while higher weights are assigned to the I-type tiles in the remaining three examples. In these three examples, we also fix the orientation of the I-type tiles.

2D pixel art results

Polyomino puzzles from 2D pixel art. From left to right: reference pixel arts, target region, and puzzle piece partitioning result. (a-b) Mario and Piranha plant: ©Nintendo Co., Ltd. (c) Megaman: ©CAPCOM Co., Ltd.

2D pixel art results

Polycube puzzles from voxel models.

Links

Acknowledgements

This work was supported by JSPS KAKENHI Grant numbers 19K24338 and 20K19944.

Bibtex

@article{Kita:CGI2020,
  title = {Computational design of polyomino puzzles},
  author = {Kita, Naoki and Miyata, Kazunori},
  year = {2020},
  journal = {The Visual Computer},
  volume = {36},
  number = {9},
  issn = {1432-2315},
  pages = {XXXX--XXXX},
  url = {https://doi.org/10.1007/s00371-020-01968-5},
  doi = {10.1007/s00371-020-01968-5},
}