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.

and Shinji Tokumasu, “Fast Placement Algorithm for Rectilinear Jigsaw Puzzles,”

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