  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.
