  In this paper we propose the first effective genetic algorithm (GA)-based
jigsaw puzzle solver. We introduce a novel crossover procedure that merges two
"parent" solutions to an improved "child" configuration by detecting,
extracting, and combining correctly assembled puzzle segments. The solver
proposed exhibits state-of-the-art performance, as far as handling previously
attempted puzzles more accurately and efficiently, as well puzzle sizes that
have not been attempted before. The extended experimental results provided in
this paper include, among others, a thorough inspection of up to 30,745-piece
puzzles (compared to previous attempts on 22,755-piece puzzles), using a
considerably faster concurrent implementation of the algorithm. Furthermore, we
explore the impact of different phases of the novel crossover operator by
experimenting with several variants of the GA. Finally, we compare different
fitness functions and their effect on the overall results of the GA-based
solver.
