Reproduce “A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Dror Sholomon, Eli David, Nathan S. Netanyahu
A Genetic Algorithm (GA) framework from Bar-Ilan University automatically solves very large jigsaw puzzles by introducing a novel kernel-growing crossover operator. The system successfully reconstructs puzzles up to 22,834 pieces, exceeding prior capabilities by more than twofold, while achieving higher accuracy on existing benchmarks compared to greedy methods.
Key insights
- The proposed "kernel-growing" crossover operator effectively combines correct relative segments from parent solutions, guaranteeing valid puzzle arrangements by iteratively adding pieces.
- Focusing on position-independent relative piece compatibility allows the Genetic Algorithm to combine and shift correctly assembled segments from different parents.
- Genetic Algorithms can effectively navigate complex search spaces and avoid local optima that often trap greedy approaches in combinatorial problems like jigsaw puzzle solving.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.