A Generalized Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles of Complex Types
This work addresses computational challenges in jigsaw puzzle assembly, which has applications in real-world problems, but it is incremental as it builds on existing genetic algorithm methods.
The authors tackled the problem of solving complex jigsaw puzzles with unknown piece location, orientation, and flipping, introducing a generalized genetic algorithm-based solver that achieves new state-of-the-art results, solving puzzles faster and more accurately, handling larger sizes, and assembling two-sided puzzles effectively.
In this paper we introduce new types of square-piece jigsaw puzzles, where in addition to the unknown location and orientation of each piece, a piece might also need to be flipped. These puzzles, which are associated with a number of real world problems, are considerably harder, from a computational standpoint. Specifically, we present a novel generalized genetic algorithm (GA)-based solver that can handle puzzle pieces of unknown location and orientation (Type 2 puzzles) and (two-sided) puzzle pieces of unknown location, orientation, and face (Type 4 puzzles). To the best of our knowledge, our solver provides a new state-of-the-art, solving previously attempted puzzles faster and far more accurately, handling puzzle sizes that have never been attempted before, and assembling the newly introduced two-sided puzzles automatically and effectively. This paper also presents, among other results, the most extensive set of experimental results, compiled as of yet, on Type 2 puzzles.