# Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving

arXiv: https://arxiv.org/abs/2303.14793 · HTML: https://mlsanity.com/paper/2303.14793/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 26 Mar 2023.

## Builds on (most cited first, 6 of 6)

- [Deepzzle: Solving Visual Jigsaw Puzzles with Deep Learning andShortest Path Optimization](https://mlsanity.com/paper/2005.12548/) (2020)
- [JigsawGAN: Auxiliary Learning for Solving Jigsaw Puzzles with Generative Adversarial Networks](https://mlsanity.com/paper/2101.07555/) (2021)
- [A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles](https://mlsanity.com/paper/1711.06769/) (2017)
- [GANzzle: Reframing jigsaw puzzle solving as a retrieval task using a generative mental image](https://mlsanity.com/paper/2207.05634/) (2022)
- [Solving Jigsaw Puzzles By the Graph Connection Laplacian](https://mlsanity.com/paper/1811.03188/) (2018)
- [A Generalized Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles of Complex Types](https://mlsanity.com/paper/1711.06768/) (2017)

## Built on by (most cited first, 7 of 7)

- [Pairwise Alignment & Compatibility for Arbitrarily Irregular Image Fragments](https://mlsanity.com/paper/2507.09767/) (2025)
- [PuzLM: Solving Jigsaw Puzzles with Sequence-to-Sequence Language Models](https://mlsanity.com/paper/2511.06315/) (2025)
- [The Missing GAP: From Solving Square Jigsaw Puzzles to Handling Real World Archaeological Fragments](https://mlsanity.com/paper/2605.12077/) (2026)
- [Nash Meets Wertheimer: Using Good Continuation in Jigsaw Puzzles](https://mlsanity.com/paper/2410.16857/) (2024)
- [Solving Convex Partition Visual Jigsaw Puzzles](https://mlsanity.com/paper/2511.04450/) (2025)
- [JigSync: Gauge-Resolved Synchronization for Jigsaw Reassembly under Unknown Piece Orientation](https://mlsanity.com/paper/2609.18379/) (2026)
- [Fix the Match, Not the Solver: STITCH -- a Self-Supervised Compatibility Measure for Eroded Visual Puzzles](https://mlsanity.com/paper/2610.13176/) (2026)

## Abstract (arXiv)

We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation. At the core of the optimization process is nonlinear relaxation labeling, a well-founded approach for deducing global solutions from local constraints, but unlike the classical scheme here we propose a multi-phase approach that guarantees convergence to feasible puzzle solutions. Next to the algorithmic novelty, we also present a new compatibility function for the quantification of the affinity between adjacent puzzle pieces. Competitive results and the advantage of the multi-phase approach are demonstrated on standard datasets.