Alors comme ça, vous voulez savoir le truc

L'idée fondatrice

Impossible ?

En fait, il y a une solution fastoche.
Utiliser des tuiles carrées.
Les réarranger est trivial.
Malheureusement...
Ce n'est plus vraiment un puzzle.

Les tapis de jeu ont résolu ce problème il y a des années.

Il ne glissent pas.
Super !
...
Sauf que chaque pièce va partout.
Ce n'est pas le genre de puzzle que je voulais.

La contrainte principale

Un puzzle normal assigne à chaque bord de'une pièce exactement un voisin.
Ici, chaque bord doit s'emboîter dans deux voisins différents.
Cette simple phrase crée toute la difficulté.

Chaque bord de pièce est un identifiant qui doit être aussi unique que possible. Mais une pièce partage un bord avec deux voisins, un pour chaque configuration. Donc elles ont le même identifiant de bord. C'est la contagion du bord.

Donc il faut suivre cette contagion. Et quand l'identifiant est complètement distribué, alors vous obtenez un cycle.

Ce cycle est alors, par construction, le nombre minimal de pièces qui partagent le même bord. Continuez avec le bord suivant.

La génération

Tout d'abord, une clarification : le logiciel démarre avec une solution complètement naze.
Ensuite il l'améliore. Juste un peu.
Encore.
Encore.
Des milliers de fois.
Ceci est connu sous le nom d'optimisation stochastique.

Les images sont choisies dans deux ensembles d'images.
Comme point de départ, aidons-nous: on s'autorise à redimensionner les images si cela les fait correspondre mieux. Bon, évidemment avec certaines limites, sinon on termine avec un seul pixel.

Oui mais comment je sais qu'elles vont bien correspondre ?

On ne peut pas savoir avant d'essayer véritablement, mais voici une heuristique : si les images partagent le même profil de couleur à cerains endroits, alors ces endroits devraient finir sur la même pièce, non ?
Donc analysons la répartition des couleurs dans les images.
Une minute... La répartition des couleurs... N'y aurait-il pas un truc avec de la correspondance d'histogramme ? ;-)

Donc : redimensionner, recolorier, tourner, retourner, et séparer en deux configurations. Pifométriques, les configurations.

Elles ne correspondent pas !

Bien sûr. Maintenant on sélectionne deux pièces. Si elles peuvent être échangées, échangeons-les. Essayons de les déformer un peu pour qu'elles correspondent mieux. Ne pas comparer les images elles-mêmes : on ne veut pas que ce soient les mêmes. On veut que les formes soient les mêmes.
Si votre but est de faire correspondre toutes les nuances de bleu, allez-y.
Pour ma part, je préfère faire correspondre les cercles et les carrés.
Est-ce que ça améliore le score ? Oui ? Super, on le garde et on passe au suivant.
Non ? Dommage, on réessaie...

L'unicité

Une troisième solution existe ( et même une quatrième par symétrie de configuration ). Ca arrive quand deux pièces se retrouvent avec la même séquence de bords. En échangeant ces pièces ont obtient une autre configuration valide.

Est-ce que ça peut être généralisé ?

Oui.
En fait, ça l'est.
Le logiciel ne sait pas ce que Petra est.
Il ne sait pas ce qu'est un volcan.
Il ne sait même pas ce qu'est un visage.
Il ne cherche pas une pièce en trop. Il peut chercher deux pièces en trop. Ou une ligne complète.
Il ne connaît que les graphes, la géométrie et l'optimisation.