Top > JACIII > Fast Placement Algorithm for Rectilinear Jigsaw Puzzles

single-jc.php

JACIII Vol.10 No.3 pp. 323-331
doi: 10.20965/jaciii.2006.p0323
(2006)

Paper:

Views over last 60 days: 557

Fast Placement Algorithm for Rectilinear Jigsaw Puzzles

Yasuyuki Murai*, Hiroyuki Tsuji*, Hisayuki Tatsumi**,
and Shinji Tokumasu*

*Department of Information and Computer Sciences, Kanagawa Institute of Technology, 1030 Shimo-ogino, Atsugi, Kanagawa 243-0292, Japan

**Department of Computer Science, Tsukuba University of Technology, 4-12-7 Kasuga, Tsukuba, Ibaraki 305-0821, Japan

Received:
February 22, 2005
Accepted:
December 21, 2005
Published:
May 20, 2006
Creative Commons License
Keywords:
game theory, polyominoes, placement algorithm, rectilinear jigsaw puzzle
Abstract
In previous papers, rectilinear jigsaw puzzles have been described as a specialized placement problem such that this has at least one solution to placement, but generally not that many. Instead of adopting the well-known iterative method to solve this problem, a new game-theoretic algorithm is developed by translating the problem to one of checkmate in games analogous to chess or shogi. By extending the game-theoretic algorithm, a much faster algorithm for large puzzles is developed by introducing various heuristics on the placement of pieces. We also proved through numerical experiments that this worked efficiently.
Cite this article as:
Y. Murai, H. Tsuji, H. Tatsumi, and S. Tokumasu, “Fast Placement Algorithm for Rectilinear Jigsaw Puzzles,” J. Adv. Comput. Intell. Intell. Inform., Vol.10 No.3, pp. 323-331, 2006.
Data files:
References
  1. [1] W. R. Heller, G. Sorkin, and K. Maling, “The planar package for system designers,” Proc. 19th D. A. Conf., pp. 253-260, 1982.
  2. [2] R. H. J. M. Otten, “Automatic floor plan design,” Proc. 19th D. A. Conf., pp. 261-267, 1982.
  3. [3] D. F. Wong, and C. L. Liu, “A new algorithm for floor plan design,” Proc. D. A. Conf., pp. 101-107, 1986.
  4. [4] K. Fujiyoshi, and H. Murata, “Arbitrary Convex and Concave Rectilinear Block Packing Using Sequence-Pair,” Trans. IEEE Computer-Aided Design, Vol.19, No.2, pp. 224-233, 2000.
  5. [5] Y. Murai, H. Tatsumi, and S. Tokumasu, “Game-theoretic Approach to Placement Problems of Rectilinear Blocks –Solution of Rectilinear Jigsaw Puzzle–,” IEEE Proceedings of the First Conference on Nanotechnology, IEEE-NANO 2001, pp. 128-133, 2001.
  6. [6] Y. Murai, H. Tatsumi, and S. Tokumasu, “Solution of Planar Polyomino Packing Problem Based on Topological Characteristics,” Journal of IPSJ, Vol.43, No.12, pp. 4009-4022, 2002 (in Japanese).
  7. [7] S. W. Golomb, “Polypminoes,” Princeton University Press, 1994.
  8. [8] E. A. Feigenbaum, and J. Feldman, “Computers and thought,” McGraw-Hill, 1963.
  9. [9] R. D. Greenblatt, “The Greenblatt chess program,” FJCC, pp. 801-810, 1963.
  10. [10] T. Ochi, T. Kamei, G. Uchigasaki, and S. Tokumasu, “Shogi checkmate problems solved by computers,” Mathematics Seminar, pp. 44-48, June, 1969 (in Japanese).

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 19, 2024