Paper:

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

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.10, No.3, pp. 323-331, 2006.

- [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] R. H. J. M. Otten, “Automatic floor plan design,” Proc. 19th D. A. Conf., pp. 261-267, 1982.
- [3] D. F. Wong, and C. L. Liu, “A new algorithm for floor plan design,” Proc. D. A. Conf., pp. 101-107, 1986.
- [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] 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] 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] S. W. Golomb, “Polypminoes,” Princeton University Press, 1994.
- [8] E. A. Feigenbaum, and J. Feldman, “Computers and thought,” McGraw-Hill, 1963.
- [9] R. D. Greenblatt, “The Greenblatt chess program,” FJCC, pp. 801-810, 1963.
- [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).

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