Recherche efficace pour résoudre un puzzle?

Question

Je crois que la résolution d'un puzzle de puzzle est en général NP-Complete basé sur les deux questions liées ci-dessous. Cependant, j'aimerais mettre en œuvre un algorithme heuristique qui fonctionne bien dans la pratique.

Supposons que les pièces du puzzle sont codées sous forme de 4 vecteurs d'entiers représentant les quatre côtés. Un entier négatif indique une indentation qui doit être appariée avec un entier positif correspondant représentant une extrusion. Zéro représente un bord lisse (c'est-à-dire une pièce de bordure) Les rotations correspondent alors au décalage cyclique (en supposant que les indentations / extrusions sont symétriques en rotation.)

Mon heuristique pour une solution efficace est d'essayer de carreler le puzzle dans une spirale intérieure à partir des frontières. Quelle est la meilleure stratégie pour construire une chaîne de pièces d'ajustement qui évitent d'essayer de manière exhaustive toutes les combinaisons / rotations?

J'ai trouvé des questions SE connexes qui sont pertinentes:

1. https://cs.stackexchange.com/questions/13849/are-zero-one-jigsaw-puzzles-np-complete
2. https://stackoverflow.com/questions/15121903/algorithm-for-solving-teling-jigsaw-puzzle
3. Puzzle de puzzle partiellement rempli avec six types de tuiles