Polyomino

Exemples de pavages de pentaminos

Un polyomino est une réunion connexe de carrés unitaires. Bien que connu depuis au moins un siècle, Solomon W. Golomb est le premier à en avoir fait une étude systématique dans un ouvrage intitulé Polyominoes.

Description

Il est construit en plaçant un nombre identique de carrés à des endroits séparés dans le plan, les carrés se touchant au complet par un côté.

Selon le contexte, sa définition est plus souple ou plus stricte. Les carrés peuvent seulement se toucher (par exemple, sur une demi-longueur de côté) et les figures ainsi construites s'appellent des polyplets, alors que dans d'autres cas, il y a des trous (en d'autres mots, des régions qui ne sont pas pavées avec des carrés et qui ne touchent pas l'extérieur). Il y a aussi des polyominos en 3D (agrégats de cubes appelés polycubes), en 4D (agrégats d'hypercubes), etc.

Les polyominos font partie de la famille des polyformes, qui contient aussi les polyiamondes (faits de triangles équilatéraux) et les polyhex (formés d'hexagones), entre autres.

Historique

Les polyominos apparaissent régulièrement dans les puzzles depuis la fin du XIX^e siècle, mais Solomon W. Golomb est le premier à en avoir fait une étude systématique dans un ouvrage intitulé Polyominoes. Il utilisa le terme pour la première fois lors d'une conférence au Harvard Math Club en 1952. Martin Gardner, dans sa rubrique Mathematical Games, les a vulgarisés en décembre 1954.

Aujourd'hui, ils font l'objet d'études mathématiques, tout comme ils ont donné naissance à différents jeux : Tetris et pentamino, entre autres.

Mathématiques

Ils sont à la source de multiples problèmes faisant appel à la combinatoire, le premier étant évidemment l'énumération des constructions de différentes tailles. Aucune formule exacte n'est connue, sauf pour quelques cas particuliers. Cependant, plusieurs valeurs estimées sont connues et il existe des algorithmes de décompte.

Formes fixée, à un seul côté et libre

Dans la suite du texte, nous abrégeons « polyomino à forme libre » par PFL et « polyomino à forme fixée » par PFF.

De façon informelle, on peut classer les polyominos en au moins deux groupes. Un polyomino à forme libre peut être retourné. Si l'une de ses images est pareille à un autre polyomino, ils sont dits pareils. À l'opposé, un polyomino à forme fixée ne peut pas être retourné. Si sa chiralité ou son orientation est différente de tous les autres polyominos, il est dit différent.

Il existe trois méthodes courantes pour définir les polyominos selon leur forme :

• fixée : polyominos qui sont nécessairement différents par
  1. la translation.
• à un seul côté : polyominos qui sont nécessairement différents par
  1. la translation
  2. la rotation dans le plan
• libre : polyominos qui sont nécessairement différents par
  1. la translation
  2. la rotation dans le plan
  3. la réflexion.

Le groupe diédral D₄ est le groupe de symétrie d'un carré. Il contient quatre rotations et quatre réflexions. il est généré en alternant la réflexion selon l'abscisse et une diagonale. Un PFL correspond à au plus 8 PFF, lequel sont ses images selon les symétriques D₄. Cependant, ces images ne sont pas nécessairement distinctes : le plus de symétrie un PFL possède, le moins il y a de versions de PFF. En conséquence, un polyomino qui est invariant sous toutes ou certaines symétries non-triviales D₄ peut seulement correspondre à 4, 2 ou 1 PFF. De façon mathématique, les PFL sont des classes d'équivalence des PFF du groupe D₄.

La liste des symétriques possibles (avec le nombre minimum de carrés pour construire un polyomino) est :

• 8 PFF pour chacun des PFL :
  • sans symétrie (4)
• 4 PFF pour chacun des PFL :
  • symétrie selon l'une des directions sur une grille cartésienne (4)
  • symétrie selon l'une des diagonales (3)
  • symétrie de rotation double (4)
• 2 PFF pour chacun des PFL :
  • symétrie selon le deux directions sur une grille cartésienne et, par conséquent, symétrie de rotation double (2)
  • symétrie la direction des deux diagonales et, par conséquent, symétrie de rotation double (7)
  • symétrie de rotation quadruple (8)
• 1 PFF pour chacun des PFL :
  • toutes les symétries du carré (1)

Décompte

Appelons n le nombre de carrés et A_n le nombre de PFF de n carrés (pouvant également posséder des trous). Leurs noms, en utilisant une racine grecque, sont créés à partir du nombre de carrés qu'ils comportent :

n	nom	nombre de PFL voir A000105	nombre de PFF avec trous voir A001419	nombre de PFF (An) voir A001168
1	monomino	1	0	1
2	domino	1	0	2
3	triomino	2	0	6
4	tétromino	5	0	19
5	pentamino	12	0	63
6	hexamino	35	0	216
7	heptamino	108	1	760
8	octamino	369	6	2725
9	ennéamino	1285	37	9910
10	décamino	4655	195	36446
11	undécamino	17073	979	135268
12	dodécamino	63600	4663	505861

Le nombre de polyominos sans trou est donné par la suite A000104 de l’OEIS, alors que le nombre de polyominos à un seul côté est donné par la suite A000988 de l’OEIS.

En 2004, Iwan Jensen a énuméré les PFF jusqu'à n = 56 : A₅₆ vaut environ 6,915×10³¹. Les PFL ont été énumérés jusqu'à n = 28 (voir Liens externes pour des tableaux d'énumération).

Algorithmes d'énumération pour les polyominos à forme fixée

Épuisement par recherche inductive

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.

Méthode par croissance

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.

Méthode de Jensen et méthode de Conway

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.

Croissance asymptotique du nombre de polyominos

Polyominos à forme fixée

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

$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

$\lim_{n\rightarrow \infty} (A_n)^{1/n} = \lambda$

existe. 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 $A_nA_m \leq A_{n+m}$. Connaissant ce résultat, on démontre que $\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.

Usages

Il existe un jeu de table qui consiste à paver une surface imaginaire avec des pentaminos en plastique. Le perdant est celui qui ne peut plus placer l'un de ses pentaminos sans créer un trou. Pour le film 2001, l'odyssée de l'espace, il semblerait que le cinéaste Stanley Kubrick ait envisagé de montrer les astronautes en train de jouer avec des pentaminos, mais a finalement préféré le jeu d'échecs.

Quelques variantes du Sudoku pavent les régions avec des polyominos. Le jeu vidéo Tetris et ses dérivés font également appel aux polyominos.

Les pièces du jeu de domino ne sont pas, au sens strict, des polyominos, puisqu'ils sont identifiés par des symboles.

Voir aussi

Articles connexes

• Pavage
• Percolation

Liens externes

• (en) Site de Solomon W. Golomb
• (en) Pavages de Karl Dahlke
• (en) Énumeration des polyominos
• (en) Énumeration 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