Voir la source de Polyomino

[[Image:BlokusTiles.svg|vignette|21 Polyominos de taille de 1 à 5.]]
En [[mathématiques]], un '''polyomino''' est une réunion [[Connexité (mathématiques)|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<ref>
{{Ouvrage |langue=en |auteur1=[[Solomon W. Golomb]] |titre=Polyominoes |sous-titre=Puzzles, Patterns, Problems, and Packings |lieu=Princeton, New Jersey |éditeur=[[Princeton University Press]] |année=1994 |numéro d'édition=2 |pages totales=xii+184 |isbn=978-0-691-02444-8 |lire en ligne=https://books.google.com/books?id=k-I9DwAAQBAJ&printsec=frontcover}}.</ref>.

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

== Description ==
Un '''polyomino''' est construit en plaçant des [[carré]]s identiques à des endroits séparés dans le [[Plan (mathématiques)|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 [[polyplet]]s, 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 [[cube]]s appelés [[polycube]]s), en 4D (agrégats d'[[hypercube]]s), etc.

Les polyominos font partie de la famille des [[polyforme]]s, qui contient aussi les [[polyiamonde]]s (faits de [[triangle équilatéral|triangles équilatéraux]]) et les [[polyhex]] (formés d'[[hexagone]]s), entre autres.

== Historique ==
Les polyominos apparaissent régulièrement dans les [[puzzle]]s depuis la fin du {{s-|XIX}} 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 {{date-|novembre 1960}}<ref>
{{article|langue=en|auteur=Martin Gardner| titre=More about the shapes that can be made with complex dominoes (Mathematical Games) |journal=Scientific American |date=novembre 1960 |volume=203 |numéro=5 |pages=186–201 |jstor=24940703 |présentation en ligne=https://www.nature.com/scientificamerican/journal/v203/n5/pdf/scientificamerican1160-186.pdf|doi=10.1038/scientificamerican1160-186 }}.</ref>.

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 ==
[[Fichier:Variations.png|vignette|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 (mathématiques)|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
*# la translation.
* ''unilatérale'' : polyominos qui sont nécessairement différents par
*# la translation
*# la rotation dans le plan
* ''libre'' : polyominos qui sont nécessairement différents par
*# la [[Translation (géométrie)|translation]]
*# la [[Translation (géométrie)|rotation]] dans le plan
*# la [[Réflexion (mathématiques)|réflexion]].

Le [[groupe diédral]] ''D''{{ind|4}} est le [[groupe (mathématique)|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 {{abbr|PFL|polyomino à forme libre}} correspond à au plus 8 {{abbr|PFF|polyominos à forme fixée}}, lequel sont ses images selon les symétriques ''D''{{ind|4}}. Cependant, ces images ne sont pas nécessairement distinctes : le plus de symétrie un {{abbr|PFL|polyomino à forme libre}} possède, le moins il y a de versions de {{abbr|PFF|polyominos à forme fixée}}. En conséquence, un polyomino qui est [[invariant]] sous toutes ou certaines symétries non-triviales ''D''{{ind|4}} peut seulement correspondre à 4, 2 ou 1 {{abbr|PFF|polyominos à forme fixée}}. De façon mathématique, les {{abbr|PFL|polyominos à forme libre}} sont des [[Relation d'équivalence|classes d'équivalence]] des {{abbr|PFF|polyominos à forme fixée}} du groupe ''D''{{ind|4}}.

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

* 8 {{abbr|PFF|polyominos à forme fixée}} pour chacun des {{abbr|PFL|polyominos à forme libre}} :
** sans symétrie (4)
* 4 {{abbr|PFF|polyominos à forme fixée}} pour chacun des {{abbr|PFL|polyominos à forme libre}} :
** 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 {{abbr|PFF|polyominos à forme fixée}} pour chacun des {{abbr|PFL|polyominos à forme libre}} :
** 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 {{abbr|PFF|polyomino à forme fixée}} pour chacun des {{abbr|PFL|polyominos à forme libre}} :
** toutes les symétries du carré (1)

== Dénombrement ==
[[Fichier:Trominoes 001.svg|vignette|upright=0.5|Les deux formes libres possibles de triomino.]]
[[Fichier:Free tetrominoes.svg|vignette|Les cinq formes libres possibles de tétromino.]]
[[Fichier:All 18 Pentominoes.svg|vignette|upright=1.5|Les dix-huit formes unilaterales possibles de pentomino.]]
Appelons ''n'' le nombre de carrés et {{mvar|A{{ind|n}}}} le nombre de {{abbr|PFF|polyominos à forme fixée}} 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 :


{|class=wikitable
!rowspan=3|''n''
!rowspan=3|nom
!colspan=5|forme
|-
!colspan=3|libre 
!rowspan=2|unilatérale 
!rowspan=2|fixe ({{mvar|A{{ind|n}}}})
|-
!total
!avec trous
!sans trous
|- align=right
|1 ||align=left |monomino ||1 ||0 ||1 ||1 ||1
|- align=right
|2 ||align=left |[[domino (mathematics)|domino]] ||1 ||0 ||1 ||1 ||2
|- align=right
|3 ||align=left |[[triomino]] ||2 ||0 ||2 ||2 ||6
|- align=right
|4 ||align=left |[[tétramino]] ||5 ||0 ||5 ||7 ||19
|- align=right
|5 ||align=left |[[pentamino]] ||12 ||0 ||12 ||18 ||63
|- align=right
|6 ||align=left |[[hexamino]] ||35 ||0 ||35 ||60 ||216
|- align=right
|7 ||align=left |[[heptamino]] ||108 ||1 ||107 ||196 ||760
|- align=right
|8 ||align=left |[[octamino]] ||369 ||6 ||363 ||704 ||2,725
|- align=right
|9 ||align=left |[[ennéamino]] ||1 285 ||37 ||1 248 ||2 500 ||9 910
|- align=right
|10 ||align=left |[[décamino]] ||4 655 ||195 ||4 460 ||9 189 ||36 446
|- align=right
|11 ||align=left |undécamino ||17 073 ||979 ||16 094 ||33 896 ||135 268
|- align=right
|12 ||align=left |dodécamino ||63 600 ||4 663 ||58 937 ||126 759 ||505 861
|- align=center
|colspan=2|suite [[OEIS]]
|{{OEIS2C|id=A000105}}
|{{OEIS2C|id=A001419}}
|{{OEIS2C|id=A000104}}
|{{OEIS2C|id=A000988}}
|{{OEIS2C|id=A001168}}
|}

En [[2004]], Iwan Jensen a énuméré les {{abbr|PFF|polyominos à forme fixée}} jusqu'à ''n''&nbsp;=&nbsp;56 : ''A''{{ind|56}} vaut environ 6,915×10{{exp|31}}. Les {{abbr|PFL|polyominos à forme libre}} ont été énumérés jusqu'à ''n''&nbsp;=&nbsp;28 (voir [[#Liens externes|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 [[Algorithmique|algorithmes]] de décompte.

=== 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 {{abbr|PFF|polyominos à forme fixée}} et des {{abbr|PFL|polyominos à forme libre}}. 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 {{abbr|PFF|polyominos à forme fixée}}, 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 [[Intel P5|Pentium]] tournant à {{Unité|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 {{abbr|PFL|polyominos à forme libre}} à 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é à {{Unité|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 [[Algorithmique|algorithme]], le plus efficace pour énumérer les {{abbr|PFF|polyominos à forme fixée}}, 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 [[fonction génératrice|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 [[Gigaoctet]]s de mémoire pour ''n'' plus grand que 50. Cet algorithme est nettement plus difficile à implanter et est incapable de compter les {{abbr|PFL|polyominos à forme libre}}.

=== 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'' :

:<math>A_n \sim \frac{c\lambda^n}{n}</math>

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

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

:<math> \lim_{n\rightarrow \infty} (A_n)^{1/n} = \lambda < \infty</math>

En d'autres termes, {{mvar|A{{ind|n}}}} croît [[croissance exponentielle|exponentiellement]] selon ''n''. La borne inférieure pour{{math|λ}} est 3,72, alors que la [[Borne supérieure et borne inférieure|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 <math>A_nA_m \leq A_{n+m}</math>. Connaissant ce résultat, on démontre que <math>\lambda \geq (A_n)^{1/n}</math> pour tout ''n''. En raffinant cette procédure, tout comme en utilisant différentes données pour {{mvar|A{{ind|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|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 [[Combinaison (mathématiques)|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 ==
[[Fichier:Pentomino Puzzle Solutions.svg|vignette|Exemples de pavages rectangulaires utilisant les 12 pentaminos.]]
{{...}}

== Jeux et puzzles ==
Il existe un jeu de table qui consiste à paver une surface imaginaire avec des [[pentamino]]s 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 [[astronaute]]s en train de jouer avec des pentaminos, mais a finalement préféré le [[jeu d'échecs]].

[[Sudoku#Variantes|Quelques variantes]] du [[Sudoku#Variantes|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 [[domino (jeu)|jeu de domino]] ne sont pas, au sens strict, des polyominos, puisqu'ils sont identifiés par des symboles.

<gallery>
Tetris basic game.gif|Exemple de partie de [[Tetris]].
Blokus.jpg|Plateau du jeu [[Blokus]].
Ubongo-tiles.jpg|Tuiles du jeu Ubongo.
</gallery>
== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Pavage]]
* [[Percolation]]

=== Liens externes ===
* {{en}} [http://commsci.usc.edu/faculty/golomb.html Site de Solomon W. Golomb]
* {{en}} [http://www.eklhad.net/polyomino/ Pavages de Karl Dahlke]
* {{en}} [http://www.ieeta.pt/%7Etos/animals/a44.html Énumération des polyominos]
* {{en}} [http://www.ms.unimelb.edu.au/~iwan/animals/series/square.site.ser Énumération des polyominos à forme fixée, jusqu'à n&nbsp;=&nbsp;56]
* {{en}} [http://www-cs-faculty.stanford.edu/~knuth/programs.html#polyominos Une explication et une implantation logicielle de l'algorithme de Jensen]
* {{en}} [http://historical.ncstrl.org/litesite-data/stan/CS-TR-72-263.pdf Article de Klarner et Rivest (PDF)]
* {{en}} [http://www.statslab.cam.ac.uk/~grg/books/hammfest/19-sgw.ps Un article décrivant les estimés modernes (PS)]
* {{en}} [http://mathworld.wolfram.com/Polyiamond.html ''Polyiamond'' de MathWorld]
* {{en}} [http://www.yoogi.com/interactive/pixfit.htm Un jeu vidéo qui remplit des images avec des polyominos]
* {{en}} [http://www.mathpages.com/home/kmath039.htm Notes sur l'énumération des polyominos]

{{Palette|Polyformes}}
{{Portail|jeux|géométrie}}

[[Catégorie:Polyforme]]
[[Catégorie:Jeu de société]]
[[Catégorie:Casse-tête]]