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.

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 :

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 :

Le diamant aztèque d’ordre 2

Les 8 pavages possibles.

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.

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.

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.

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.

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.

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 :

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).

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.

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.