Recherche efficace pour résoudre un puzzle?
-
05-11-2019 - |
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:
Pas de solution correcte