What is a good algorithm for solving a non-logic puzzle?

and thanks for taking the time to review this issue.

My problem is in solving a non-boolean puzzle that doesn't have a perfect solution. In a normal puzzle, the two pieces either match, or can be placed next to each other, or do not match. In a non-logic puzzle, any piece can be placed next to any other, but an appropriate score can be set for each connection between the two pieces, between 0 and 1. Here, say, the best "solution" is the one that maximizes the average score of all nodes in solved puzzle. As with large puzzles, it is impossible to test all solutions, I need an algorithm that gives a "relatively good solution".

I'm not really dealing with a puzzle, but a tiled image where tiles are shuffled. We get a matching score with tiling by comparing their edge pixels. The kebab image looks like this:

In my cases, additional rules apply:
- No two items are alike. However, the two parts can have the same edges.
- When resolving, tiles must not fit into a specific shape. I want it to be roughly square / rectangular.
- You can leave empty tiles without pieces inside.

What I want is an idea of ​​an algorithm that can give a decent solution - reasonable time (a few minutes is completely ok). If you think the definition of a good solution (currently: get the highest compound score on average over the final image) is wrong, feel free to modify it to fit your algorithm. The problem with this solution is that currently, you can just place two tiles together to get a score of 1, and separate each individual tile with white space so that they can't get a lower score. This technically gives a perfect GPA of 1, but the final image will contain moslty spaces, this is not what I want.

For understanding, here is the answer that I would find very good for the problem above:

Obviously, I would be surprised if there was a good result, but I would like at least similar fragments to approach each other in the final image.

Thank you for your time and remember that any idea is welcome, even weird ones.