A Genetic Algorithm-Based Solver for Small-Scale Jigsaw Puzzles

Abstract

In this paper, we present a genetic algorithm-based puzzle solver, which is mainly used to solve small-scale puzzle problems. We introduce a new measurement function that improves its accuracy by normalizing the Mahalanobis distance and the Euclidean distance between two puzzle pieces. By calculating the difference between edges of two puzzle pieces and using the genetic algorithm to assemble pieces correctly, two “parent” solutions are merged into one improved “child” solution. Using the idea of local search, it avoids the problem of local optimum solutions brought by the genetic algorithm, which greatly improves the accuracy of the puzzle.