Assembly of puzzles using a genetic algorithm

In this paper, we proposed a method for solving the rectangle piece jigsaw puzzle assembly problem. A shape of a piece is a rectangle, and a picture of a puzzle is only painted in black and white, i.e., puzzles are processed as binary images. The assembly of the puzzle is performed only using information of the pixel value on the border line of the pieces. This problem cannot be solved by the simple local piece matching because there are many similar pieces. Global matching is required. The proposed method utilizes a genetic algorithm (GA) to search the optimum piece arrangement because GA has the ability to find the global solution in the large optimization space. The proposed method correctly assembled all pieces in the 8 × 8-piece puzzle.