Un algorithme de pavage de polyominos vieux de huit ans : recherche par retour arrière avec heuristiques

Cet article détaille un algorithme pour résoudre le problème du pavage de polyominos. L’idée principale consiste à transformer le problème géométrique en un problème de théorie des graphes et à utiliser un algorithme de recherche par retour arrière avec plusieurs heuristiques. Tout d’abord, l’algorithme prétraite pour calculer tous les placements possibles, construisant un graphe bipartite représentant toutes les possibilités. Ensuite, un algorithme de recherche par retour arrière trouve un sous-ensemble de placements satisfaisant les conditions, optimisé par des heuristiques telles que la priorisation des points de grille restreints et la division de la grille. L’algorithme démontre une bonne généralité et robustesse dans la gestion des formes de grille arbitraires et des ensembles de polyominos. L’auteur discute également des limitations et des améliorations futures, telles que la transformation du problème en un problème SAT pour sa résolution.