Polyomino

En mathématiques, 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 paru en 1953^[1].

Ils sont le sujet de multiples problèmes mathématiques, notamment autour de dénombrement ou de pavage, et ils inspirent différents jeux, notamment Tetris.

Description modifier

Un polyomino est construit en plaçant des carrés identiques à 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 modifier

Les polyominos apparaissent régulièrement dans les puzzles depuis la fin du XIX^e siècle et 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 novembre 1960^[2].

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

Polyominos identiques modifier

Ces tetrominos peuvent être considérés équivalents car ils se retrouvent mutuellement par transformations simples.

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.
unilatérale : 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 les 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énombrement modifier

Les deux formes libres possibles de triomino.

Les cinq formes libres possibles de tétromino.

Les dix-huit formes unilaterales possibles de pentomino.

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	forme
		libre			unilatérale	fixe ( $A n$ )
		total	avec trous	sans trous	unilatérale	fixe ( $A n$ )
1	monomino	1	0	1	1	1
2	domino	1	0	1	1	2
3	triomino	2	0	2	2	6
4	tétramino	5	0	5	7	19
5	pentamino	12	0	12	18	63
6	hexamino	35	0	35	60	216
7	heptamino	108	1	107	196	760
8	octamino	369	6	363	704	2,725
9	ennéamino	1 285	37	1 248	2 500	9 910
10	décamino	4 655	195	4 460	9 189	36 446
11	undécamino	17 073	979	16 094	33 896	135 268
12	dodécamino	63 600	4 663	58 937	126 759	505 861
suite OEIS		A000105	A001419	A000104	A000988	A001168

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).

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.

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

Épuisement par recherche inductive modifier

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 modifier

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 modifier

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 modifier

Polyominos à forme fixée modifier

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 <\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 $A_{n}A_{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.

Pavage modifier

Exemples de pavages rectangulaires utilisant les 12 pentaminos.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Jeux et puzzles modifier

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.

Exemple de partie de Tetris.
Plateau du jeu Blokus.
Tuiles du jeu Ubongo.

Notes et références modifier

↑ (en) Solomon W. Golomb, Polyominoes : Puzzles, Patterns, Problems, and Packings, Princeton, New Jersey, Princeton University Press, 1994, 2^e éd., xii+184 (ISBN 978-0-691-02444-8, lire en ligne).
↑ (en) Martin Gardner, « More about the shapes that can be made with complex dominoes (Mathematical Games) », Scientific American, vol. 203, n^o 5,‎ novembre 1960, p. 186–201 (DOI 10.1038/scientificamerican1160-186, JSTOR 24940703, présentation en ligne).

Voir aussi modifier

Articles connexes modifier

Liens externes modifier

[1] (en) Solomon W. Golomb, Polyominoes : Puzzles, Patterns, Problems, and Packings, Princeton, New Jersey, Princeton University Press, 1994, 2^e éd., xii+184 (ISBN 978-0-691-02444-8, lire en ligne).

[2] (en) Martin Gardner, « More about the shapes that can be made with complex dominoes (Mathematical Games) », Scientific American, vol. 203, n^o 5,‎ novembre 1960, p. 186–201 (DOI 10.1038/scientificamerican1160-186, JSTOR 24940703, présentation en ligne).

[1]

[2]