Partie 7 : PENTAMINOS

le jeu

Le jeu de pentaminos est un puzzle constitué de pièces en deux dimensions réalisées à partir d’un carré de base ; chaque pièce est colorée de façon identique sur ses deux faces. Une pièce est constituée de 5 carrés juxtaposés, en connexion par les côtés. On considère donc que deux pièces sont différentes si on ne peut les superposer exactement même en en retournant une. La copie d’écran qui suit est tirée d’un logiciel fait par le club sur les pentaminos :

question 7.1.

Prouvez qu’avec les conventions énoncés, il n’y a pas d’autres pentaminos que ceux représentées ci-dessus.

les symétries.

Les pentaminos sont supposés posés sur une grille rectangulaire à maille carrée de même dimension de base. On pourra ainsi parler de la grille 6x10, différente de la grille 10x6, ou de la grille 8x8... Le but du jeu est de poser tous les pentaminos sur la grille ; dans le cas où la grille a plus de 60 carreaux, un certain nombre de carrés sont neutralisés (on y pose autant de carrés «blancs» qu'il le faut) avant d’entamer le puzzle.


Il y a alors 8 manières de poser le pentamino 10 comme le montre l’illustration ci-dessus, la position initiale donnée par la première illustration, les trois positions obtenues par rotation, et les quatre symétriques. On appelle «instance» chacune des dispositions. Les pentaminos qui possèdent une symétrie interne ont un nombre d’instances réduit.

On propose d’appeler I l’instance de la première illustration, R1, R2, R3 les instances obtenues à partir de I par rotation de 1/4, 1/2 et 3/4 de tours, SI, SR1, SR2, SR3 les quatre instances obtenues en prenant un symétrique de I et en la composant aux trois rotations.

question 7.2.

On demande de réaliser un tableau qui donne pour chaque pentamino quelles sont ses instances distinctes.

le jeu effectif.

Afin d’éviter les doublés par rotation ou retournement, on décide en général de ne retenir qu’une instance de l’une des pièces non symétriques. Ici, ce sera l’instance du pentamino 0 présenté dans l’illustration : ce pentamino ne sera ni tourné, ni retourné (on rappelle que la grille est orientée, et que la grille 6x10 est un rectangle en portrait, et 10x6, un rectangle en paysage). Quelques réalisations possibles :

question 7.3.

On demande de réaliser un logiciel de recherche de recouvrement de grilles par les 12 pentaminos. En entrée, il faut pouvoir choisir entre les grilles suivantes :

- grilles complètes : 3x20, 20x3, 4x15, 15x4, 5x12, 12x5, 6x10, 10x6
- avec des cases neutres : 3x21, 21x3, 4x16, 16x4, 5x13, 13x5, 8x8, 7x9, 9x7. Pour ces grilles, il faut préciser quelles sont les cases neutres avant la recherche.

Le logiciel doit alors rechercher systématiquement toutes les solutions possibles, les dénombrer, et donner un moyen d’en prendre connaissance. Si un affichage texte peut suffire, une solution graphique constituera un bonus.