Pavages aléatoires par touillage de dominos

Piste bleue Le 17 février 2009  - Ecrit par  Elise Janvresse, Thierry de la Rue Voir les commentaires (4)

La physique statistique s’intéresse à l’étude à grande échelle de systèmes formés d’un nombre immense de composantes microscopiques. Une question essentielle est de savoir comment cette multitude d’éléments s’organise en fonction des contraintes qui leur sont imposées : quelle est la place laissée au hasard ? Quel comportement observe-t-on à l’échelle macroscopique ? Expérimenter dans ce domaine nécessite de pouvoir générer des configurations typiques à l’aide d’algorithmes simulant les effets du hasard.

Paver avec des dominos

L’exemple que nous considérons ici est celui des pavages d’une région du plan avec des dominos de taille $2\times 1$.
Les règles du pavage sont les suivantes : les dominos doivent remplir toute la région et ils ne doivent pas se chevaucher.
Parmi toutes les façons de paver une énorme région, y a-t-il une tendance générale ?

Bien sûr, il n’est pas toujours possible de paver une région donnée. Une condition nécessaire est clairement que la région soit la réunion d’un nombre pair de carrés de côté 1.
Et il existe même des régions du plan satisfaisant cette condition qui ne sont pas pavables par des dominos.


Une région impossible à paver

PNG - 4.4 ko
Un pavage impossible
Il est impossible de paver l’échiquier écorné (62 cases) avec 31 dominos.

Voici un exemple de pavage impossible : On veut paver avec des dominos de taille $2\times 1$ l’échiquier de taille $8\times 8$ « écorné » : on lui a ôté les cases de deux coins opposés. La surface à recouvrir est bien la réunion d’un nombre pairs de carrés de côté 1 ($8\times 8 - 2 = 62$), mais cela est pourtant impossible !
En effet, quelle que soit la façon dont un domino est placé, il recouvre une case noire et une case blanche. Or l’échiquier écorné contient plus de cases blanches (32) que de noires (30). Il est donc impossible de le paver avec nos dominos.

PNG - 1.3 ko
Encore une figure non pavable
Et pourtant elle contient autant de cases noires que de cases blanches.

Notez que l’égalité entre le nombre de cases blanches et de cases noires est nécessaire, mais non suffisante, comme le montre le contre-exemple ci-contre. Pour en savoir plus la condition de pavabilité par des dominos, voir
 [1].

Pavage aléatoire

Quand une région du plan est pavable avec des dominos, il existe en général un très grand nombre de façons possibles de les placer.
Pour connaître la manière typique dont s’organisent les dominos, il est souhaitable de pouvoir tirer au sort un pavage.
Mettons tous les pavages possibles dans un chapeau, mélangeons bien et tirons-en un sans regarder.
C’est ce que l’on appelle un tirage équiprobable : tous les pavages ont la même probabilité d’être choisis.
En pratique, une telle énumération de tous les pavages est irréalisable : le nombre de pavages possibles augmente extrêmement vite avec la taille de la région à paver.

Les mathématiciens ont donc mis au point des algorithmes qui permettent de réaliser une telle expérience sans recourir à un chapeau.
Le plus connu utilise le lien avec les « arbres couvrants » [2] et l’algorithme de David Wilson [3] pour générer ces objets.

Nous allons ici présenter une autre méthode, dite de « touillage de dominos » (domino shuffling), pour générer des pavages aléatoires.
Elle a été développée pour une forme très particulière de région, le diamant aztèque, mais peut être généralisée pour réaliser d’autres sortes de pavages.

L’algorithme du touillage de dominos

Voici les diamants aztèques d’ordre 1, 2, 3 et 6 :

PNG - 2.4 ko
Diamants aztèques d’ordre 1, 2, 3 et 6

Il y a bien sûr deux façons de paver le diamant d’ordre 1 :

Pour le diamant d’ordre 2, il est encore possible de recourir au chapeau. On voit qu’il y a une chance sur 8 de tirer l’un des pavages suivants :

PNG - 3.1 ko
Le diamant aztèque d’ordre 2
Les 8 pavages possibles.

Pourquoi nos dominos sont-ils de 4 couleurs différentes ?


Nous utilisons pour représenter les pavages une convention de couleurs qui permet de distinguer 4 types possibles de placement d’un domino. Il y a bien sûr une distinction entre les dominos horizontaux et les verticaux, et dans chacune de ces orientations, on compte deux façons de placer le domino : ayant colorié les cases du diamant en échiquier, on différencie les dominos horizontaux recouvrant une case blanche à gauche de ceux recouvrant une case blanche à droite (et de même pour les verticaux, suivant que la case blanche est en haut ou en bas). Cette utilisation des couleurs devient nécessaire pour apprécier à l’échelle macroscopique les tendances d’organisation du pavage (voir le phénomène du cercle arctique décrit plus bas).


On pourrait aussi énumérer tous les pavages du diamant d’ordre 3, bien que cela commence à être difficile.
Mais pour le diamant d’ordre 4, ce n’est déjà plus raisonnable de construire à la main tous les pavages possibles : il en existe 1024 différents.
En général, on peut montrer qu’il y a exactement $2^{n(n+1)/2}$ manières de paver un diamant d’ordre $n$.
Pour le diamant d’ordre 100, il y a donc $2^{5050}$ pavages possibles, un nombre qui s’écrit avec plus de 1 500 chiffres !

On peut facilement passer du diamant aztèque d’ordre $n-1$ à celui d’ordre $n$ : Il suffit d’ajouter autour une couche supplémentaire.
C’est cette propriété géométrique qui permet de construire un pavage aléatoire d’un gros diamant, en construisant successivement des pavages des diamants plus petits : on commence par le diamant d’ordre 1 en tirant à pile ou face l’orientation des deux dominos (tous les deux horizontaux ou tous les deux verticaux). Puis on construit successivement des pavages des diamants d’ordre 2, 3, 4,... jusqu’à l’ordre souhaité. Le passage d’un pavage d’ordre $n-1$ à celui d’ordre $n$ s’effectue en déplaçant localement les dominos (d’où le nom de l’algorithme). Il arrive régulièrement qu’un choix d’orientation des dominos se présente : à chaque fois que c’est le cas, on tire à pile ou face pour décider. En procédant ainsi, on obtient à chaque étape un pavage choisi de manière équiprobable parmi tous les pavages de la même taille.


Détail de l’algorithme

Comment passer d’un pavage du diamant d’ordre $n-1$ à un pavage du diamant d’ordre $n$ ?
Pour cela, nous avons besoin de la notion de cellule active.
Une cellule est un carré $2\times 2$ contenu dans le diamant.
Ayant colorié les cases du diamant comme sur un échiquier, on peut distinguer deux sortes de cellules : celles dont la case en haut à gauche est noire et celle pour lesquelles elle est blanche.
Toutes les cellules qui touchent le bord sont de même type.
Par exemple, dans le diamant d’ordre 2, la case en haut à gauche est blanche (et c’est le cas pour tous les diamants d’ordre pair).
Nous dirons qu’une cellule est active si elle est du même type que celles du bord.

PNG - 2 ko
Cellules actives
À gauche : l’une des 4 cellules actives du diamant d’ordre 2. À droite, 3 des 9 cellules actives du diamant d’ordre 3.

On part d’un pavage du diamant d’ordre $n-1$ et on ajoute une couche de cases pour l’insérer dans un diamant d’ordre $n$.
Considérons une des cellules actives du gros diamant et les dominos complètement contenus dans cette dernière :
Si elle est recouverte par deux dominos entiers, on enlève les deux dominos.
Si elle contient exactement un domino entier, on le décale de l’autre côté de la cellule.
Si elle ne contenait aucun domino entier, on la recouvre avec deux dominos en tirant à pile ou face leur orientation.

PNG - 2.7 ko
Effet local du touillage
Exemples de cellule active contenant 2, 1 ou 0 dominos entiers.

Il n’est pas a priori évident que l’on puisse appliquer cette procédure simultanément sur chacune des $n^2$ cellules actives du diamant d’ordre $n$, puisque celles-ci se chevauchent. C’est pourtant toujours possible, et cela donne un pavage du diamant d’ordre $n$.

PNG - 3 ko
Passage d’un pavage du diamant d’ordre 2 à un pavage du diamant d’ordre 3.
À droite, on a tiré au sort les orientations des dominos dans les cellules actives entourées en pointillés.

Les animations suivantes présentent les étapes successives de l’exécution de l’algorithme du touillage pour des diamants aztèques d’ordre 10 puis 100.

GIF - 76.2 ko
Algorithme du touillage de dominos
Étapes successives de l’algorithme pour la génération d’un pavage du diamant d’ordre 10. Chaque pavage est tiré de manière équiprobable parmi tous les pavages possibles.
GIF - 1.8 Mo
Le même algorithme, poussé jusqu’à un diamant d’ordre 100

Le phénomène du cercle arctique

Si l’on tire au hasard un des pavages possibles d’un diamant d’ordre assez grand, on verra, comme sur l’animation ci-dessus, apparaître avec une probabilité proche de 1 le fameux cercle arctique [4] : à l’extérieur du cercle inscrit dans le diamant les dominos sont tous « gelés » dans le même sens, alors qu’à l’intérieur le désordre règne.

Le phénomène du cercle arctique dans le pavage aléatoire du diamant aztèque présente un intérêt très particulier : dans ce modèle, les effets de bord se propagent à une grande distance de la frontière du domaine et sont donc visibles à l’échelle macroscopique. Ce n’est pas le cas pour le carré par exemple.

PNG - 251.4 ko
Effets de bords
À gauche : un pavage typique du diamant aztèque d’ordre 100, sur lequel on observe le phénomène du cercle arctique. À droite : un pavage typique du carré de côté 60.

Pavage aléatoire d’autres régions du plan : l’algorithme du touillage avec poids

Lors de l’application de l’algorithme du touillage, il est nécessaire de tirer à pile ou face pour passer d’un pavage du diamant d’ordre $n-1$ au pavage du diamant d’ordre $n$.
On utilise une pièce équilibrée pour décider entre les deux façons possibles d’orienter certains dominos car on ne souhaite pas privilégier un sens plutôt que l’autre.
Il existe une version [5] plus sophistiquée de l’algorithme qui permet de favoriser ou défavoriser certains placements des dominos.
On associe un poids à chaque position possible d’un domino : la position sera d’autant plus favorisée que le poids est important.
Les tirages au sort se font alors avec des pièces biaisées (qui favorisent ou défavorisent les piles).

En fait, il est même possible d’interdire de placer des dominos à certains endroits en leur attribuant des poids nuls [6].
C’est ce que l’on a fait pour obtenir un pavage aléatoire du carré de côté 60 présenté plus haut.
Celui-ci a été « inséré » dans un diamant aztèque, et on a interdit certains placements de dominos.

PNG - 3.9 ko
Un carré inséré dans un diamant aztèque.
On interdit que les dominos chevauchent le carré, en attribuant un poids nul aux positions spécifiées en rouge.

À l’extérieur du carré, les dominos se rangent obligatoirement tous de la même façon (horizontalement en bas et en haut et verticalement à droite et à gauche).
On obtient, à l’aide de l’algorithme du touillage, un pavage aléatoire équiprobable du carré.

Bien sûr, on peut faire la même chose pour paver un rectangle (dont la largeur ou la longueur est paire) ou une autre région de forme plus compliquée.
On peut même s’amuser en attribuant des poids en fonction de l’intensité de pixels d’une photographie. Voilà ce que cela donne :

GIF - 475.6 ko
Pavage avec poids
Pavage aléatoire d’un carré lorsque les orientations sont pondérées en fonction de l’intensité des pixels d’une photo.

Autres pavages aléatoires

Il est possible de réaliser des pavages avec d’autres formes que des dominos à partir de l’algorithme du touillage : par exemple paver un hexagone avec des losanges. L’idée est de remplacer le réseau carré, qui est en quelque sorte le « squelette » du diamant aztèque, par un autre réseau régulier : le réseau hexagonal (en haut à droite), le réseau carrés-octogones (en bas à gauche), ou le réseau composé de carrés, hexagones et octogones (en bas à droite).


Couplages parfaits d’un graphe

Pour comprendre le passage à d’autres types de pavages, nous avons besoin de la notion de couplage parfait d’un graphe.
Nous allons associer un graphe à une région formée de cases : Les sommets sont les centres de chaque case, et deux sommets appartenant à des cases ayant un côté commun sont reliés entre eux par une arête.

Chaque arête du graphe correspond à un placement possible d’un domino.
Partant d’un pavage de la région par des dominos, on considère l’ensemble des arêtes associées : on obtient ainsi un couplage parfait du graphe, c’est-à-dire une collection d’arêtes qui recouvrent une fois et une seule chaque sommet du graphe. Inversement, à tout couplage parfait du graphe correspond un pavage par les dominos.

PNG - 3.7 ko
Lien entre un pavage du diamant d’ordre 3 et un couplage parfait du graphe associé.

Attribuer un poids nul à une position de domino revient à effacer l’arête correspondante dans le graphe.
L’algorithme de touillage avec poids permet alors d’obtenir un couplage parfait de sous-graphes du graphe associé au diamant aztèque.
Cela peut fonctionner même avec des graphes a priori différents.
Par exemple, le graphe associé au réseau hexagonal ci-dessous peut s’identifie à un sous-graphe d’un diamant aztèque assez grand.

PNG - 37.5 ko
Réseau hexagonal
À gauche : un graphe représenté comme un réseau hexagonal. À droite, le même graphe vu comme un sous-graphe du diamant aztèque (les arêtes en pointillés sont effacées par attribution d’un poids nul).

Une fois généré un couplage parfait du sous-graphe correspondant au réseau hexagonal, on lui associe un pavage de l’hexagone. Cette fois les pavés utilisés ne sont plus des dominos rectangulaires, mais des losanges. Il y en a trois sortes, suivant leur orientation.

PNG - 62.9 ko
Couplage et pavage
Couplage parfait d’un réseau hexagonal et pavage par des losanges correspondant.

Un pavage typique de l’hexagone à l’aide de losanges fait apparaître un phénomène semblable au cercle arctique dans le diamant aztèque.

PNG - 23.1 ko
Pavage aléatoire de l’hexagone.

Les autres réseaux présentés ci-dessus donnent lieu à des pavages dans lesquels apparaissent simultanément des pavés de formes différentes (carrés, triangles, etc.). La figure suivante présente deux pavages aléatoires obtenus à partir de ces réseaux (avec détails des pavages à l’intérieur des disques).

On observe à nouveau sur ces pavages un phénomène de gel des bords, mais on ne sait pas encore identifier la forme de la partie gelée.

Article édité par Jacques Istas

Notes

[1J. C. Fournier. Tiling pictures of the plane with dominoes. Discrete Mathematics
165-166, (1997), 313—320
Graphs and Combinatorics

[2R. Kenyon, J. Propp, D. Wilson. Trees and matchings. Electron. J. Combin. 7 (2000), Research Paper 25, 34 pp.

[4W. Jockusch, J. Propp et P. Shor. Random domino tilings and the arctic circle theorem (1998).

[5J. Propp. Generalized domino-shuffling. Theoretical Computer Science 303 (2003), p. 267-301

[6É. Janvresse, T. de la Rue, Y. Velenik. A note on domino shuffling. Electron. J. Combin. 13 (2006), no 1.

Partager cet article

Pour citer cet article :

Thierry de la Rue , Elise Janvresse — «Pavages aléatoires par touillage de dominos» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

  • Pavages aléatoires par touillage de dominos

    le 23 octobre 2009 à 22:58, par FrancoisGueg

    Je me suis personnellement lancé dans l’écriture de l’algorithme tel qu’il est décrit ici...

    Etape 0/ type pavage == int list vect vect (matrice de liste d’entiers )

    Etape 1/ Vidage de toutes les cellules actives « pleines »

    Etape 2/ Permutation unique de chaque cellule active contenant exactement ! un domino

    Etape 3/ Remplissage aléatoire des cellules strictement vides ...

    Etape 4/ On fait bien entendu une procédure récursive sur les pavages auquels on rajoute successivement des « bords »

    Toutefois ! à partir du rang n=7 subsistent des « trous » dans le pavage
    alors que pas précédemment ...

    Auriez vous quelque chose à redir esur ma manière de procéder où bien l’algorithme est il erroné ?

    Répondre à ce message
  • Pavages aléatoires par touillage de dominos

    le 26 octobre 2009 à 11:01, par Thierry de la Rue

    Bonjour,

    Nous ne savons pas d’où vient le problème, peut-être est-ce dû à la définition de cellule active. Avez-vous tenu compte du fait que ces cellules changent à chaque étape ?
    Une cellule est active si elle a la même configuration en terme d’échiquier que les cellules du bord. Une fois sur deux, les cellules actives ont une case blanche en haut à gauche.

    En tout cas soyez assuré que l’algorithme fonctionne !

    Répondre à ce message
  • Pavages aléatoires par touillage de dominos

    le 9 novembre 2009 à 17:01, par FrancoisGueg

    Bon j’ai finalement résolu mon problème je post ici la solution puisque je pense qu’il pourra intéresser de futurs lecteurs :

    Il ne faut pas exactement prendre au pied de la lettre le sujet tel qu’il est posé puisqu’en réalité les cellules actives ne sont pas forcément et cela m^me à partir d’un certain rang comme le laisse suggérer l’énoncé du type : (vide,1 domino) exemple ( 1 case de chaque couleur dans une cellule non active de sorte que les 4 cellules actives autour ne puisse être décaler chacune en bloquant une autre etc ... ( on a en fait un cercle vicieux , faire un dessin pour une meilleure visualisation, encore désolé de ne pas pouvoir insérer d’image dans le message )

    Il faut donc travailler sur les dominos ( ce qui n’était pas évident à première et même deuxième lecture du sujet ) pour les déplacements qui seront faits dans un nouveau pavage et non sur les cellules actives ce qui donnerait trop d’indices et de cas à traiter !

    Cela reste tout de même un très bon sujet quoique un peu confus sur ce point.

    Répondre à ce message
  • Pavages aléatoires par touillage de dominos

    le 3 avril 2015 à 18:29, par myryllion

    Bonjour,

    L’algorithme m’intéresse aussi mais c’est effectivement présenté de façon très peu claire !
    Vous dites que : « Il n’est pas a priori évident que l’on puisse appliquer cette procédure simultanément sur chacune des n² cellules actives du diamant d’ordre n, puisque celles-ci se chevauchent. C’est pourtant toujours possible, et cela donne un pavage du diamant d’ordre n. ». Simultanément, je vois pas comment ?
    En effet, comme dit dans un commentaire précédemment, les cellules actives changent au fur et à mesure qu’on applique « l’effet local du touillage ». Considérez par exemple le diamant d’ordre 1 avec deux dominos horizontaux. Les cellules actives à gauche et à droite ne peuvent pas être traitées. Il faut d’abord « pousser » un domino vers le haut, l’autre vers le bas avant de pouvoir considérer deux cellules actives vides. Par ailleurs, « touillage » est bien mal choisi puisqu’on est amené à remplacer des dominos. Ceux-ci ne sont pas mélanger stricto sensu... Les visuels de l’article sont cependant intéressants et donnent envie de creuser.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM