So you want to know the trick

The founding idea

Impossible ?

Actually, there is an easy solution.
Use square tiles.
Rearranging them is trivial.
Unfortunately...
that's no longer a jigsaw puzzle.

Playground mats solved this problem years ago.

They don't slide.
Great!
...
Except every piece still fits everywhere.
That's not the kind of puzzle I wanted.

The main constraint

A normal puzzle gives each edge of a piece exactly one neighbour.
Here, every edge must satisfy two different neighbours.
That simple sentence creates almost every difficulty.

Give every edge an identifier which should be unique as much as possible. But a piece shares an edge with two neighbours, one in each configuration. So they have the same border identifier. It's the border contagion.

So you have to follow this contagion. And when the id is fully spread, you'll obtain a cycle.

This cycle is then, by construction, the minimal number of pieces which share the same edge. Proceed to the next edge.

The generation

First of all, let me be clear : the software starts with a terrible solution.
Then it improves it. Just a bit
Again.
Again.
Thousands of times.
This is known as stochastic optimization.

The two pictures are selected from separate image sets.
As a starting point, help yourself : you're allowed to reframe the pictures if it makes them match better. Well, of course with some limits, else you'll end with only one pixel.

How do I know if they'll match well ?

We can't be sure until actually trying, but here is an heuristic : if the pictures share colours in some spots, then those spots shall end on the same piece, don't they?
So let's analyze the colour repartition in the pictures.
Wait a minute... The colour distribution... Is there a trick about histogram matching here ? ;-)

So : reframe, recolor, rotate, flip, and split into two configurations. Random configurations.

That doesn't match!

Of course. Now select two pieces, if they can be switched, switch them. Try to deform them a bit to fit better. Don't compare the pictures themselves : you don't want them to be the same. You want the shapes to be the same.
If your goal is matching every shade of blue, feel free.
I prefer matching circles and squares..
Did you improve the solution? Yes ? Great, keep it and move forward.
No ? Well, try again...

The uniqueness

A third solution may exist (and a fourth by configurations' symetry). It happens whenever two pieces accidentally share the exact same sequence of edges. Exchange these pieces and you get another valid configuration.

Can this be generalized?

Yes.
Actually, it is.
The software doesn't know what Petra is.
It doesn't know what a volcano is.
It doesn't even know what a face is.
It doesn't look for one extra piece. It can search for two extra pieces. Or a full row.
It only knows graphs, geometry and optimization.