Nothing Special   »   [go: up one dir, main page]

Aller au contenu

Polyomino

Un article de Wikipédia, l'encyclopédie libre.
21 Polyominos de taille de 1 à 5.

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 | modifier le code]

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.

Les polyominos apparaissent régulièrement dans les puzzles depuis la fin du XIXe 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 [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 | modifier le code]
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 D4 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 D4. 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 D4 peut seulement correspondre à 4, 2 ou 1 PFF. De façon mathématique, les PFL sont des classes d'équivalence des PFF du groupe D4.

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 | modifier le code]
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 An 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 (An)
total avec trous sans trous
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 OEISA000105 OEISA001419 OEISA000104 OEISA000988 OEISA001168

En 2004, Iwan Jensen a énuméré les PFF jusqu'à n = 56 : A56 vaut environ 6,915×1031. 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 | modifier le code]

Épuisement par recherche inductive

[modifier | modifier le code]

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 | modifier le code]

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 | modifier le code]

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 | modifier le code]

Polyominos à forme fixée

[modifier | modifier le code]

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

λ = 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

En d'autres termes, An 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 . Connaissant ce résultat, on démontre que pour tout n. En raffinant cette procédure, tout comme en utilisant différentes données pour An, 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.

Exemples de pavages rectangulaires utilisant les 12 pentaminos.

Jeux et puzzles

[modifier | modifier le code]

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.

Notes et références

[modifier | modifier le code]
  1. (en) Solomon W. Golomb, Polyominoes : Puzzles, Patterns, Problems, and Packings, Princeton, New Jersey, Princeton University Press, , 2e é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, no 5,‎ , p. 186–201 (DOI 10.1038/scientificamerican1160-186, JSTOR 24940703, présentation en ligne).

Articles connexes

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]