Un polymino est une généralisation du domino, un polymino de taille
p est un ensemble connexe de p carrés. Cette connexité s'entend
dans le sens que, entre deux carrés d'un polymino, il existe
toujours un chemin formé de carrés qui se touchent par un coté.
Voici quelques polyminos de taille 4.
Le but du projet est d'énumérer les polyminos pour une
taille donné, On peut compter les polyminos d'une taille donné d'au
moins deux manières. On peut tout d'abord considérer que deux
polyminos sont différents lorsqu'ils ne se recouvrent pas par
translation.
On parle alors de polyminos fixés.
Selon
cette définition il y a 6 polyminos fixés de taille 3 :
Si, en revanche on décide d'identifier les polyminos
qui se recouvrent après symétrie (retourner le polymino) ou rotations
d'un quart de tour, alors on ne compte plus que 2 polyminos de
taille 3. De tels polyminos sont dits libres.
Les polyminos fixés seront comptés par énumération. En effet, étant
donné un polymino P(k) de taille k, on obtient un polymino de
taille k+1 en ajoutant un carré qui a un coté en commun avec
un des carrés
de P(k). Réciproquement, tout polymino de taille k+1 peut être
construit en augmentant un polymino de taille k de cette façon.
Il est possible d'écrire un bon énumérateur qui ne génère jamais deux
fois le même polymino fixé. C'est un peu moins simple qu'il n'y
paraît. Le principe de l'énumérateur est, tout d'abord, de considérer
un damier de cases. On crée un polymino en énumérant tous les
remplissages possibles de ces cases.
On souhaite éviter d'énumérer deux polyminos identiques à une
translation près. Ceci fixe une case commune à tous les polymino, qui
se situe à une position conventionnelle dans les polyminos générés, par
exemple, en bas et le plus à gauche possible.
Ensuite on a un algorithme récursif dans le principe. À chaque étape un
polymino P(k), d'une certaine taille k est déjà construit, on
souhaite générer tous les polyminos de taille inférieure
à p qui
contiennent ce polymino courant P(k).
On occupe donc une case voisine de P(k), créant ainsi un nouveau
polymino P(k+1). On énumère ensuite récursivement tous les polyminos qui
contiennent P(k+1). Une fois cette énumération terminée, on efface
la case voisine de P(k) et on recommence avec un autre voisin de
P(k), tant qu'il en reste.
L'algorithme simple décrit ci-dessus énumère encore plusieurs fois le
même polymino. En effet, il y a, en partant du coin en bas à gauche
deux suites distinctes de polyminos croissants qui atteignent
le polymino carré de taille 4 (la dernière case occupée à chaque
étape est grisée) :
et,
Un algorithme astucieux évite ce piège en limitant le choix des cases
voisines à examiner. Par exemple, considérons la case initiale et ses
deux voisines (en haut et à droite). Supposons en outre que la case
de droite est choisie en premier, l'exploration démarrera par le
domino couché et aboutira (entre autres) au tetramino carré, ce qui
est normal puisque ce dernier contient le domino couché.
Une fois explorés tous les polyminos qui contiennent le domino
couché, on génère le domino debout et on poursuit l'exploration,
recherchant maintenant les polyminos qui contiennent le domino debout.
Cependant, la génération du tetramino carré n'aura cette fois pas
lieu, si l'on s'interdit d'occuper la voisine de gauche de la case
initiale. Et c'est bien logique, puisqu' on construirait alors
forcément un polymino qui contient le domino couché et que l'on a donc
déjà vu.
La différence entre le compte des polyminos libres et fixés repose
sur les symétries des polyminos, un polymino libre peut compter pour
un, deux, quatre ou huit polyminos fixés, selon les isométries qui
le laissent invariant.
On appelle indice d'un polymino le nombre de polyminos
fixés qui lui sont isomorphes.
Par exemple, dans le cas p = 4, le polymino suivant,
qui possède toutes les symétries possibles, compte à la fois pour un
polymino libre et un polymino fixé, il est donc d'indice un.
En revanche, un polymino d'indice huit ne se recouvre jamais
lui-même si on le retourne ou le tourne.
Entre les deux, ce polymino invariant par une rotation
d'un demi tour, compte pour un polymino libre et quatre
polyminos fixés.
Plus précisément, on considère le groupe des isométries du carré.
L'ensemble des isométries qui laissent invariant un polymino donné est
un sous-groupe. L'indice d'un polymino est directement fonction du
cardinal de ce sous-groupe.
Revenons au cas p=3, et classons les polyminos fixés selon
les isométries qui les laissent invariants.
Nous avons tout d'abord deux polyminos invariants par
rotation d'un demi tour et symétrie selon les deux axes vertical et horizontal.
Vu comme libre, chacun de ces polymino compte pour deux polyminos
fixes (l'un est l'image de l'autre par
la rotation d'un quart de tour, qui justement ne les laisse pas invariants).
Ensuite, deux polyminos invariants par symétrie selon la diagonale
ascendante. Chacun d'entre eux compte pour quatre dans le compte des
polyminos fixés.
Enfin deux polyminos invariants par symétrie selon la diagonale
descendante, qui eux aussi comptent pour quatre chacun.
Soit finalement, deux polyminos d'indice deux et quatre d'indice
quatre. Le nombre de polyminos libres de taille trois est bien 2 =
2/2 + 4/4.
La méthode de comptage des polyminos libres, s'articule comme suit :
Compter les polyminos fixés de taille p. On obtient un
entier Nf(p).
Compter les polyminos fixés de taille p invariants par
certaines isométries. On en déduit, N1(p), N2(p), N4(p), les
nombres de polyminos fixés,
d'indices respectifs un, deux et quatre. Le nombre de polyminos fixés
d'indice huit (ceux qui ne sont invariants par aucune isométrie) est
N8(p) = N(p) − (N1(p)+ N2(p) +N4(p)).
Le nombre de polyminos libres Nl(p) est N1(p) + N2(p)/2 +
N4(p)/4 + N8(p)/8
La méthode ne coûte guère plus cher que l'énumération des polyminos
fixés pour les raisons suivantes :
La somme N1(p)+ N2(p) +N4(p) des polyminos invariants par
au moins une isométrie non-triviale est petite devant Nf(p),
dès que p est un peu grand.
Sauf dans le cas particulier des polyminos de taille paire
invariants par rotation, il est facile de compter les polyminos fixés
invariants par un sous-groupe d'isométries donné
en modifiant légèrement l'énumérateur de polyminos fixes.
Il suffit, lorsque l'on ajoute une case à un polymino,
d'ajouter aussi sa ou ses transformés par les isométries en question.
On s'inspirera d'un article scientifique en anglais fourni (si vous
choisissez ce sujet, contactez moi : Luc.Maranget@inria.fr).
L'article décrit les énumérateurs dans un langage parfois un peu abstrait :
Écrire l'énumérateur de polyminos fixés. Il faut savoir que
l'auteur de l'article a mis neuf mois pour calculer le nombre de
polyminos fixés de taille 24.
L'article ayant été écrit en 1974, il devrait être possible de faire
un peu mieux aujourd'hui en programmant en Pascal, C ou Caml.
Voici les comptes des polyminos de 1 à 26.
Pour ce faire, la programmation devra être efficace et l'énumérateur
redémarrable.
En effet, Votre programme devra certainement s'exécuter pendant un temps
assez long sur une machine donnée. Cette machine peut
s'arrêter inopinément. Par conséquent, votre programme devra, de
temps en temps,
sauver suffisamment d'information sur disque pour pouvoir ensuite
reprendre le compte des polyminos sans recommencer au début.
Identifier et écrire les énumérateurs contraints, dans le cas
des polyminos de taille impaire. En déduire le compte des polyminos
libres pour p aussi grand que possible.
Le polyminos sont parfois utilisés comme pièces de puzzle. Par
exemple, on peut paver un rectangle 3 × 20 à l'aide des 12
pentaminos libres.
Les polyminos qui comportent des trous ne font pas de bonnes pièces de
puzzle. C'est par exemple le cas des trois polyminos suivants.
On demande de définir clairement les polyminos à trous et d'énumérer
les polyminos sans trous d'une taille donnée p. Tentez de
réaliser un énumérateur qui ne construit que des polyminos sans trous
et construit chaque polymino sans trou une et une seule fois.
