Polyominos

Les polyominos sont des figures géométriques formées en assemblant des carrés unitaires bord à bord. Ce terme englobe toutes ces figures, quelle que soit leur taille : les monominos (1 carré), les dominos (2), les trominos (3), les tétrominos (4), les pentominos (5), les hexominos (6) et ainsi de suite. Dans un casse-tête de polyominos, le joueur doit placer un ensemble donné de pièces de formes irrégulières à l'intérieur d'une forme cible — un rectangle, un cadre ou tout autre contour — en couvrant chaque case exactement une fois. La nature générique des casse-têtes de polyominos permet une variété infinie d'ensembles de pièces et de formes cibles.

Règles

1. On vous donne une forme cible (contour de la grille) et un ensemble de pièces de polyomino.
2. Placez toutes les pièces dans la forme cible de manière à ce que chaque case soit recouverte.
3. En général, les pièces peuvent être pivotées et retournées librement (les règles varient selon le casse-tête).
4. Les pièces ne doivent pas se chevaucher.
5. Aucune case de la forme cible ne doit rester vide.

Catégories de pièces par taille

| Nom | Carrés | Nombre (gratuit) |

|------|---------|-------------|

| Monomino | 1 | 1 |

| Domino | 2 | 1 |

| Tromino | 3 | 2 |

| Tétromino | 4 | 5 |

| Pentomino | 5 | 12 |

| Hexomino | 6 | 35 |

| Heptomino | 7 | 108 |

| Octomino | 8 | 369 |

Stratégies

• Correspondance des surfaces : Calculez la surface totale de toutes les pièces et vérifiez qu'elle correspond à celle de la forme cible. Si ce n'est pas le cas, le casse-tête est insoluble ou vous n'avez pas le bon jeu de pièces.
• Remplissage des coins : les coins de la forme cible sont les emplacements les plus contraignants. Identifiez les pièces pouvant s'insérer dans les coins et placez-les en premier.
• Coloration par parité : coloriez la grille comme un damier. Chaque pièce couvre un rapport spécifique entre cases noires et blanches. Vérifiez que le nombre total de cases noires et blanches de toutes les pièces correspond à la cible.
• Placer d’abord les pièces contraignantes : les pièces aux formes inhabituelles (croix, formes en U, formes asymétriques) ont moins de placements valides. Placez-les avant les pièces plus flexibles.
• Éviter les zones isolées : au fur et à mesure que vous placez les pièces, veillez à ne pas créer de zone isolée plus petite que votre plus petite pièce restante.
• Suivi des contours : suivez le contour de la forme cible en remplissant vers l’intérieur. Cela restreint naturellement le problème et évite la formation de grands espaces intérieurs ambigus.

L'étude mathématique des polyominos a été lancée par Solomon W. Golomb, qui a introduit ce terme lors d'une conférence donnée en 1953 au Harvard Mathematics Club et a publié un article scientifique sur le sujet l'année suivante. Son ouvrage de 1965, intitulé « Polyominoes : Puzzles, Patterns, Problems, and Packings », est devenu la référence incontournable et a donné lieu à des décennies de recherche mathématique.

Cependant, le concept consistant à emboîter des formes géométriques remonte à plusieurs siècles avant Golomb. Les puzzles de dominos remontent au XVIIIe siècle, et les problèmes de pavage font l’objet d’études mathématiques depuis l’Antiquité. L’étude spécifique des formes à base carrée a pris de l’ampleur au XXe siècle, parallèlement au développement de la combinatoire et des mathématiques récréatives.

Martin Gardner a popularisé les polyominos grâce à sa rubrique « Mathematical Games » publiée dans Scientific American à partir de 1957. Son style d’écriture accessible a fait découvrir ces formes à un large public et a inspiré des générations de mathématiciens, de concepteurs de casse-têtes et de créateurs de jeux. L’influence des polyominos sur la culture populaire s’est confirmée lorsque Alexey Pajitnov a utilisé des tétrominos comme base pour Tetris en 1984.

Les problèmes de pavage par des polyominos sont devenus des objets d'étude fondamentaux en informatique et en mathématiques. Déterminer si un ensemble donné de polyominos peut paver une région donnée est, en général, un problème NP-complet, ce qui en fait l'un des problèmes difficiles classiques de la théorie de la complexité algorithmique. Les recherches se poursuivent dans les domaines de la théorie du pavage, de l’énumération des polyominos, des pavages sans faille et des liens avec la mécanique statistique. Les casse-têtes modernes basés sur les polyominos apparaissent dans les jeux de société (comme Blokus), les jeux vidéo, les outils pédagogiques et les compétitions mathématiques à travers le monde.