Unknown orientation of puzzle pieces

[superhero1]

@guansanghai I want to enhance your code to automatically rotate pieces for each iteration if their orientation is unknown, how can I do that?

[guansanghai]

For the linear programming based solver, the puzzles with unknown orientation is introduced in Section 3.5.1 of [1]. The authors update the algorithm just by adding a pre-process step. Specifically, they make 4 copies for each piece corresponding to 4 orientations. Then they select one piece, and fix the (x,y) coordinates of its 4 copies as an extra constraint of the LP problem. Hence the solution is 4 pictures with different orientations. For my implementation, I think the post-processing step also requires some upgrades.

For the quadratic programming based solver, the authors of [2] listed this case as their future work. So, I think it is still a challenge for this solver.

[1] R. Yu, C. Russell, L. Agapito, "Solving Jigsaw puzzles with linear programming"

[2] F. A. Andalo, G. Taubin, S. Goldenstein, "PSQP: Puzzle solving by quadratic programming," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 2, pp. 385-396, 2017.