Polyomino

L'approche la plus évidente, et la plus lente, pour énumérer tous les polyominos est l'épuisement par recherche inductive. Connaissant une liste de polyominos d'aire n, prendre chaque polyomino un à la fois, insérer dans un carré de n×n, entourer ce carré avec un collier de cellules de façon à créer un carré de (n+2)×(n+2). Pour chacune des cellules de ce carré qui est adjacent à une cellule occupée, remplir la cellule et biffer une rangée de cellules inoccupées et une rangée de colonnes inoccupées. Le carré de (n+1)×(n+1) obtenu est un polyomino candidat d'aire n+1. Si cette construction est nouvelle, elle s'ajoute à la liste des polyominos d'aire n+1. Cette comparaison doit se faire en considérant la position et la symétrie, tout en tenant compte des PFF et des PFL. La position est prise en compte en effectuant une translation du candidat au coin gauche supérieur du carré (n+1)×(n+1). Pour calculer le nombre de PFF, les rotations et les réflexions doivent aussi être prises en compte.

Cette méthode se répète, en commençant par le monomino, jusqu'à ce que les polyominos de taille requise sont énumérés. Cependant, cette méthode est gourmande pour les grandes surfaces. Par exemple, pour trouver tous les dodécominos, elle prend environ 90 secondes avec un ordinateur équipé d'un Pentium tournant à 1 GHz.

Cette méthode est utilisée par plusieurs auteurs pour démontrer les limites supérieures sur les nombres fournis.

Commencer par un carré et y ajouter récursivement des carrés. Cette méthode permet de compter tous les n-ominos n fois.

La variante la plus simple consiste à ajouter un carré à la fois. Imaginer un quadrillage de cellules vides. Parmi celles-ci, identifier une cellule avec 0. Étant la seule cellule disponible, insérer un carré à cette position. Identifier dans le sens horaire les cellules vides adjacentes à la cellule nouvellement remplie : 1, 2, 3 et 4. Choisir un nombre entre 1 et 4, et ajouter un carré à cette position. Identifier les cellules vides adjacentes à toute la construction qui ne sont pas encore identifiées : 5, 6 et 7. Choisir un nouveau nombre plus grand que celui déjà choisi, ajouter un carré à cette position. Répéter ce processus autant que voulu: identifier, choisir et ajouter. Quand n carrés sont créés, un n-omino est créé.

Cette méthode garantit que chaque polyomino fixé est compté exactement n fois, Une fois pour chaque construction de départ. S'il faut compter les PFL à la place, il faut vérifier les symétries après la création de chaque n-omino. Cet algorithme énumère les dodécominos en environ 20 secondes avec un ordinateur cadencé à 1 GHz. Le temps est proportionnel au nombre de polyominos.

Il est possible d'améliorer la vitesse de cette méthode de façon à compter chaque polyomino une fois seulement, plutôt que n fois. Dans une grille de cellules vides, mettre le carré dans le coin inférieur gauche. Par la suite, ne pas identifier les cellules qui se trouvent à une position inférieure ou à sa gauche. Cette amélioration divise le temps de recherche par n.

Cet algorithme, le plus efficace pour énumérer les PFF, est le fruit du travail d'Iwan Jensen. Il améliore l'algorithme d'Andrew Conway, le rendant exponentiellement plus rapide que les algorithmes précédents, même si son temps de recherche est exponentiel en n.

Les deux méthodes comptent le nombre de polyominos qui ont une certaine largeur. Le décompte pour toutes les largeurs est égal au nombre total de polyominos. Elles s'appuient sur l'idée de considérer les rangées de départ valides, puis de compter le nombre minimum de carrés pour compléter un polyomino d'une largeur donnée. Associé aux fonctions génératrices, cette technique compte plusieurs polyominos à la fois, ce qui raccourcit d'autant la durée de l'algorithme lorsque comparé aux autres qui comptent un polyomino à la fois.

En contrepartie de ce gain de vitesse, la quantité de mémoire nécessaire pour qu'il s'exécute croît de façon exponentielle. Par exemple, il faut plusieurs Gigaoctets de mémoire pour n plus grand que 50. Cet algorithme est nettement plus difficile à implanter et est incapable de compter les PFL.

Différents arguments théoriques, supportés par des calculs numériques, donnent le nombre de polyominos en fonction de n :

${\displaystyle A_{n}\sim {\frac {c\lambda ^{n}}{n}}}$

où λ = 4,0626 et c = 0,3024. Ce résultat n'est cependant pas rigoureusement démontré et les valeurs de λ et c ne sont que des estimations.

Les résultats théoriques publiés sont moins précis. On sait seulement que

${\displaystyle \lim _{n\rightarrow \infty }(A_{n})^{1/n}=\lambda <\infty }$

En d'autres termes, A_n croît exponentiellement selon n. La borne inférieure pourλ est 3,72, alors que la borne supérieure est 4,65.

Pour établir la borne inférieure, il suffit d'utiliser une simple et efficace méthode qui concatène les polyominos. Définir le coin droit haut comme étant le dernier carré droit de la plus haute rangée du polyomino, mutatis mutandis, de même pour le coin inférieur gauche. Construire un (n+m)-omino unique en attachant le coin droit haut de n'importel quel polyomino de taille n au coin inférieur gauche du polyomino de taille m. Le nouveau poyomino est unique et ${\displaystyle A_{n}A_{m}\leq A_{n+m}}$. Connaissant ce résultat, on démontre que ${\displaystyle \lambda \geq (A_{n})^{1/n}}$ pour tout n. En raffinant cette procédure, tout comme en utilisant différentes données pour A_n, on obtient la borne inférieure.

La borne supérieure s'obtient en généralisant l'énumération de la méthode par croissance. Plutôt que d'additionner un carré à la fois, ajouter un amas de carrés (opération souvent décrite comme une addition de twigs en anglais). En démontrant que tous les n-ominos sont une séquence de twigs, ainsi que les limites sur les combinaisons de twigs possibles, on obtient la borne supérieure du nombre de n-ominos. Par exemple, pour la méthode par croissance, à chaque répétition, il faut choisir un nombre plus large, et après le deuxième répétition, seulement trois nouveaux identificateurs s'ajoutent. Cela suffit pour obtenir la borne supérieure de 6.75. Avec 2,8 millions de twigs, Klarner et Rivest ont calculé une borne supérieure de 4.65. Ce résultat date des années 1970, il est donc possible de l'améliorer avec les ordinateurs d'aujourd'hui, mais aucun résultat n'a été publié jusqu'à maintenant.

• Pavage
• Percolation

• (en) Site de Solomon W. Golomb
• (en) Pavages de Karl Dahlke
• (en) Énumération des polyominos
• (en) Énumération des polyominos à forme fixée, jusqu'à n = 56
• (en) Une explication et une implantation logicielle de l'algorithme de Jensen
• (en) Article de Klarner et Rivest (PDF)
• (en) Un article décrivant les estimés modernes (PS)
• (en) Polyiamond de MathWorld
• (en) Un jeu vidéo qui remplit des images avec des polyominos
• (en) Notes sur l'énumération des polyominos