and thanks for taking your time considering this question.
My problem is the solving of a non boolean puzzle that has no perfect solution. In a regular puzzle, two pieces either match and can be placed next to each other, or don't match. In a non boolean puzzle, any piece can be put next to any other one, but a matching score can be established for every junction between two pieces, between 0 and 1. Here, let's say the best "solution" is the one that maximises the average score of all the junctions in the solved puzzle. As with big puzzles it becomes impossible to test all solutions, I want an algorithm that gives a solution that is "relatively good".
In reality, I'm not dealing with a puzzle, but with a tiled image where the tiles are shuffled. We get the matching score of a tile junction by comparing their edge pixels. An image with shuffeled tiles looks like this:
In my cases, the additional rules apply:
- No two pieces are the same. Two pieces might have the same edges however.
- The tiles doesn't have to get in a specific shape when solved. I want it to be roughly square/rectangle shaped however.
- It is possible to leave blank tiles with no pieces inside.
What I want is an algorithm idea that could give a decent solution is reasonable time (few minutes is totally ok). If you think the definition of a good solution (currently: get the highest junction score in average in the final image) is wrong, feel free to change it to match your algorithm. A problem I have with that solution is that currently, you can just place two tiles together to get a score of 1, and separate every single other tile with blank space to prevent them from getting a lower score. That technicly gives a perfect average score of 1, but the final image will contain moslty blank spaces, that's not what I want.
For comprehension sake, here is an answer I would find very good for the problem above:
Obviously I would be surprised to have that good of an output, but I would like at least that similar tiles get close to each other in the final image.
Thanks for your time, and remember any idea is welcome, even weird ones.