# Solving Jigsaw Puzzles with Linear Programming

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2015.

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

- [DiffAssemble: A Unified Graph-Diffusion Model for 2D and 3D Reassembly](https://mlsanity.com/paper/2402.19302/) (2024)
- [Re-assembling the past: The RePAIR dataset and benchmark for real world 2D and 3D puzzle solving](https://mlsanity.com/paper/2410.24010/) (2024)
- [JigsawGAN: Auxiliary Learning for Solving Jigsaw Puzzles with Generative Adversarial Networks](https://mlsanity.com/paper/2101.07555/) (2021)
- [A Survey on Computational Solutions for Reconstructing Complete Objects by Reassembling Their Fractured Parts](https://mlsanity.com/paper/2410.14770/) (2024)
- [TEN: Twin Embedding Networks for the Jigsaw Puzzle Problem with Eroded Boundaries](https://mlsanity.com/paper/2203.06488/) (2022)
- [The Missing GAP: From Solving Square Jigsaw Puzzles to Handling Real World Archaeological Fragments](https://mlsanity.com/paper/2605.12077/) (2026)
- [Solving Convex Partition Visual Jigsaw Puzzles](https://mlsanity.com/paper/2511.04450/) (2025)
- [Benchmarking Content-Based Puzzle Solvers on Corrupted Jigsaw Puzzles](https://mlsanity.com/paper/2507.07828/) (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 propose a novel Linear Program (LP) based formula- tion for solving jigsaw puzzles. We formulate jigsaw solving as a set of successive global convex relaxations of the stan- dard NP-hard formulation, that can describe both jigsaws with pieces of unknown position and puzzles of unknown po- sition and orientation. The main contribution and strength of our approach comes from the LP assembly strategy. In contrast to existing greedy methods, our LP solver exploits all the pairwise matches simultaneously, and computes the position of each piece/component globally. The main ad- vantages of our LP approach include: (i) a reduced sensi- tivity to local minima compared to greedy approaches, since our successive approximations are global and convex and (ii) an increased robustness to the presence of mismatches in the pairwise matches due to the use of a weighted L1 penalty. To demonstrate the effectiveness of our approach, we test our algorithm on public jigsaw datasets and show that it outperforms state-of-the-art methods.