problème des dominos de Wang

Imaginez une boîte de carrés dont chaque bord porte une couleur. Pour poser deux carrés côte à côte, les deux bords qui se touchent doivent avoir la même couleur. Les carrés gardent toujours leur orientation : on peut les déplacer, mais ni les tourner ni les retourner.

Le défi ne consiste pas à compléter un petit rectangle. Il faut savoir si les règles locales permettent de couvrir le plan entier, sans trou ni chevauchement. Certains ensembles y parviennent sans qu'aucun motif global se répète périodiquement.

Une tuile de Wang est un carré dont chacun des quatre côtés reçoit une couleur prise dans un ensemble fini. Un jeu de tuiles est lui aussi fini. On peut utiliser autant de copies que nécessaire de chaque type, mais uniquement par translation : les rotations et les retournements sont interdits. Un pavage valide couvre tout le plan, sans trou ni chevauchement, et deux côtés en contact portent toujours la même couleur.

Le problème des dominos de Wang demande si un jeu fini donné admet au moins un tel pavage du plan. Le mot « domino » désigne ici cette question de raccord entre carrés colorés ; il ne change pas leur forme en rectangles composés de deux cases. La validité d'une région finie isolée ne garantit pas qu'elle puisse être prolongée au plan entier. En revanche, pour un jeu fini, l'existence de pavages de carrés arbitrairement grands garantit, par compacité, l'existence d'un pavage du plan.

Hao Wang introduisit ces tuiles en 1961 et conjectura que tout jeu capable de paver le plan possédait un pavage périodique. Robert Berger réfuta cette conjecture en 1966 avec un jeu de 20 426 tuiles qui pave le plan, mais seulement de manière apériodique. Il établit aussi, par un argument d'encodage distinct, qu'aucun algorithme ne peut décider correctement, pour tous les jeux finis de tuiles de Wang, lesquels pavent le plan. Les tuiles de Wang fournirent ainsi le premier exemple historique de pavage apériodique et inspirèrent notamment des généralisations en dimension trois.

Prenons quatre types de tuiles orientées, notés A, B, C et D. Chaque côté est rouge, jaune ou noir. Le schéma représente un carré de quatre tuiles et rend visibles les quatre raccords à contrôler.

Données.
A : haut jaune, droite noire, bas rouge, gauche rouge.
B : haut rouge, droite jaune, bas jaune, gauche noire.
C : haut rouge, droite jaune, bas noir, gauche jaune.
D : haut jaune, droite noire, bas rouge, gauche jaune.
Les tuiles restent dans cette orientation.

Étape 1. Plaçons A à gauche de B. Le côté droit noir de A rencontre le côté gauche noir de B : ce raccord est autorisé.

Étape 2. Plaçons C sous A et D sous B. Entre A et C, les côtés en contact sont rouges. Entre B et D, ils sont jaunes.

Étape 3. Le dernier raccord intérieur, entre C et D, réunit deux côtés jaunes. Les quatre contraintes locales du carré sont donc satisfaites.

Contrôle. On peut relire successivement les deux raccords verticaux et les deux raccords horizontaux : noir, jaune, rouge, jaune. Ce carré fini est valide, mais il ne prouve pas que ces quatre types peuvent couvrir le plan entier.

Pour contrôler une configuration finie, on examine chaque côté partagé une seule fois. Dès que deux couleurs diffèrent, la configuration est rejetée ; si tous les raccords coïncident, on sait seulement que cette région est valide.

Pour établir qu'un jeu pave le plan, une simple collection d'exemples finis de tailles bornées ne suffit pas. En revanche, pour un jeu fini, des pavages de carrés arbitrairement grands garantissent par compacité l'existence d'un pavage du plan. Si un motif rectangulaire se répète par translations compatibles, cette répétition fournit directement un pavage périodique.

Pour comparer des jeux de tuiles, on sépare trois questions : un pavage existe-t-il, existe-t-il un pavage périodique, et tous les pavages sont-ils apériodiques ? Cette distinction évite de prendre une absence de motif repéré dans une zone finie pour une preuve d'apériodicité.

Tuile de Wang et domino ordinaire. Une tuile de Wang est un carré à quatre côtés colorés, pas un rectangle formé de deux cases. Le critère décisif est l'accord des couleurs sur chaque côté commun.

Pavage non périodique et jeu apériodique. Un pavage particulier peut ne pas être périodique alors que le même jeu en admet un autre qui l'est. Un jeu est apériodique lorsqu'il pave le plan et que tous ses pavages sont non périodiques.

Une grande région finie ne suffit pas. Des raccords corrects sur une zone, même vaste, ne garantissent pas que cette zone puisse être prolongée indéfiniment. Il faut raisonner sur l'existence d'un pavage du plan entier.

L'orientation fait partie des données. Tourner ou retourner une tuile change la position de ses couleurs et sort du problème défini par Wang. Il faut recopier les côtés dans un ordre fixé — haut, droite, bas, gauche — et ne déplacer les copies que par translation.

Indécidable ne signifie pas insoluble dans chaque cas. Certains jeux particuliers peuvent être analysés. Le résultat d'indécidabilité affirme qu'il n'existe pas un algorithme unique qui donne toujours la bonne réponse pour tout jeu fini fourni en entrée.

L'absence de période observée n'est pas une preuve. Une portion finie ne permet ni d'exclure une répétition plus lointaine ni de conclure que tous les pavages possibles sont apériodiques. Ces affirmations exigent un argument global.

Le pavage apériodique développe la notion qui a réfuté la conjecture de Wang : un jeu peut paver le plan sans permettre de pavage périodique.

La fiche décidabilité et indécidabilité replace le problème des dominos dans la question générale de ce qu'un algorithme peut décider pour toutes les entrées.

Les généralisations en dimension trois prolongent le même changement d'échelle : des règles imposées entre voisins doivent produire une structure cohérente dans tout l'espace.