Each tile ti is assigned to a location j. The result is represented by a permutation π of the N = 9 tiles.
The traditional Jigsaw Puzzle is the problem of assembling several non-overlapping puzzle pieces that can be combined in order to obtain a single image. Despite that fact it is a NP-complete problem, much effort has been devoted to solve the problem and its scientific challenges. In this article, the authors introduce the Puzzle Solving by Quadratic Programming (PSQP) method as a new formulation to solve image puzzles.
The solution corresponds to the biunivocal association of tiles to locations, according to an energy function. Due to the complexity of this hard combinatorial problem, the authors reformulate it as a quadratic programming problem, which we solve using a Constrained Gradient Ascent algorithm. To evaluate it experimental results are shown and compared to the state-of-the-art approaches.
F. Andalo; G. Taubin; S. Goldenstein, “PSQP — Puzzle Solving by Quadratic Programming,” in IEEE Transactions on Pattern Analysis and Machine Intelligence. doi: 10.1109/TPAMI.2016.2547394
RECOD — Reasoning for Complex Data 