Fast Placement Algorithm for Rectilinear Jigsaw Puzzles

作     者：Murai, Yasuyuki Tsuji, Hiroyuki Tatsumi, Hisayuki Tokumasu, Shinji 

作者机构：Kanagawa Inst Technol Dept Informat & Comp Sci 1030 Shimo Ogino Atsugi Kanagawa 2430292 Japan Tsukuba Univ Technol Dept Comp Sci Tsukuba Ibaraki 3050821 Japan 

出 版 物：《JOURNAL OF ADVANCED COMPUTATIONAL INTELLIGENCE AND INTELLIGENT INFORMATICS》 (J. Adv. Comput. Intell. Intelligent Informatics)

年 卷 期：2006年第10卷第3期

页      面：323-331页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：game theory polyominoes placement algorithm rectilinear jigsaw puzzle 

摘      要：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.