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
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.
-  W. R. Heller, G. Sorkin, and K. Maling, “The planar package for system designers,” Proc. 19th D. A. Conf., pp. 253-260, 1982.
-  R. H. J. M. Otten, “Automatic floor plan design,” Proc. 19th D. A. Conf., pp. 261-267, 1982.
-  D. F. Wong, and C. L. Liu, “A new algorithm for floor plan design,” Proc. D. A. Conf., pp. 101-107, 1986.
-  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.
-  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.
-  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).
-  S. W. Golomb, “Polypminoes,” Princeton University Press, 1994.
-  E. A. Feigenbaum, and J. Feldman, “Computers and thought,” McGraw-Hill, 1963.
-  R. D. Greenblatt, “The Greenblatt chess program,” FJCC, pp. 801-810, 1963.
-  T. Ochi, T. Kamei, G. Uchigasaki, and S. Tokumasu, “Shogi checkmate problems solved by computers,” Mathematics Seminar, pp. 44-48, June, 1969 (in Japanese).
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.