Solving Convex Partition Visual Jigsaw Puzzles
This work expands computational puzzle-solving to convex partitions, addressing a limitation in practical applications beyond square puzzles.
The paper tackled the problem of solving convex partition visual jigsaw puzzles, which are a subset of polygonal puzzles with convex pieces, by developing a greedy solver that uses geometrical and pictorial compatibilities, and it reported performance measures alongside the first benchmark dataset for such puzzles.
Jigsaw puzzle solving requires the rearrangement of unordered pieces into their original pose in order to reconstruct a coherent whole, often an image, and is known to be an intractable problem. While the possible impact of automatic puzzle solvers can be disruptive in various application domains, most of the literature has focused on developing solvers for square jigsaw puzzles, severely limiting their practical use. In this work, we significantly expand the types of puzzles handled computationally, focusing on what is known as Convex Partitions, a major subset of polygonal puzzles whose pieces are convex. We utilize both geometrical and pictorial compatibilities, introduce a greedy solver, and report several performance measures next to the first benchmark dataset of such puzzles.