A Generalized Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles of Complex Types

Dror Sholomon, Omid E. David, Nathan S. NetanyahuAAAI 2014 · DOI

Abstract

Researchers have developed a generalized genetic algorithm (GA) capable of solving massive jigsaw puzzles—up to 22,755 pieces—where the orientation and even the "face" (front or back) of the pieces are unknown. This solver sets a new state-of-the-art by handling "Type 4" (two-sided) puzzles for the first time and doubling the size of previously solvable "Type 2" (rotated) puzzles with significantly higher accuracy.

Introduction

While jigsaw puzzles are a common pastime, they represent a computationally NP-hard problem. Most automated solvers focus on "Type 1" puzzles, where only the piece's location is unknown. This research addresses significantly more complex variants:

  • Type 2: Pieces have unknown locations and orientations (rotated 0, 90, 180, or 270 degrees).
  • Type 4: "Two-sided" puzzles where pieces have unknown locations, orientations, and faces (flipped).

Solving these complex puzzles has critical real-world applications in archaeology (reconstructing frescoes), biology (DNA sequencing), and forensics (recovering shredded documents). As the number of pieces $n$ increases, the search space explodes; Type 4 puzzles increase the number of possible solutions by a factor of $8^n$ compared to the standard version.

Methodology

The core of the solver is a Genetic Algorithm (GA), a search heuristic inspired by natural selection, utilizing a specific fitness function and a novel crossover technique.

Fitness Function and Dissimilarity

To determine if two pieces belong together, the solver uses a "dissimilarity measure." It calculates the sum of squared color differences across the abutting edges of two pieces in the Lab* color space. The GA's objective is to minimize this total dissimilarity across the entire puzzle assembly.

The Kernel Growth Crossover

The primary innovation is the Kernel Growth crossover. Unlike traditional GA crossovers that swap random data chunks, this procedure is inspired by Prim’s Algorithm for Minimum Spanning Trees. It starts with a single seed piece and "grows" the solution by adding pieces one by one, prioritizing edges that appear in both parent solutions or exhibit "best-buddy" characteristics (mutual best matches).

The Kernel Growth crossover process, showing the evolution from parent solutions to a completed child puzzle.

This crossover is designed to be invariant to absolute position and orientation. It builds the puzzle relative to the pieces themselves, allowing the final image to emerge in any orientation without a pre-defined frame.

Experimental Results

The solver was evaluated on established benchmarks and massive new datasets, ranging from 432 to 22,755 pieces.

  • Type 2 Performance: On the 432-piece benchmark, the solver achieved 94.58% direct accuracy, a 4% improvement over the previous state-of-the-art.
  • Unprecedented Scale: The solver successfully reconstructed a 22,755-piece puzzle with 91.07% neighbor accuracy in roughly 3.5 hours. The previous record for Type 2 puzzles was approximately 9,600 pieces.
  • Type 4 Success: The solver achieved 100% accuracy on several 10,375-piece two-sided puzzles. In a practical test, it reconstructed a shredded document by utilizing the image on the reverse side, reaching 99.86% accuracy.

Key Insights

  • Concurrent Solving: For two-sided puzzles, the GA assembles both images simultaneously. The solver often uses the "easier" side of a piece to help place it correctly, which automatically positions the "harder" side (e.g., a blank page) on the reverse.
  • Best-Buddy Heuristic: Integrating the "best-buddy" concept into the crossover phase makes the solver resilient to local optima that often trap greedy algorithms.
  • Frame Independence: By not fixing the $N \times M$ dimensions at the start, the GA can explore solutions rotated 90 degrees from the original, preventing the premature discarding of valid partial assemblies.

Conclusion and Future Work

This generalized GA solver demonstrates remarkable scalability and accuracy across complex puzzle types. While computationally intensive—taking several hours for 22k pieces—it represents a significant leap in automated reconstruction. Future work may extend this framework to "wild" puzzles involving missing, overlapping, or non-square pieces common in archaeological contexts.

Summary updated

BibTeX
@inproceedings{sholomon2014generalized,
  author = {Dror Sholomon and Omid E. David and Nathan S. Netanyahu},
  title = {{A Generalized Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles of Complex Types}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9148},
}
Figure