Coloriage du pavage d'un plan

[invite8af81491]

Aux curieux que les problèmes inhabituels intéressent...

J'ai une surface sur laquelle je souhaite poser, en damier, des motifs différents.

Je souhaite qu'il n'y ait pas deux motifs identiques à coté.

Je considère comme "à coté", ceux adjacent en diagonale, et ceux qui sont directement voisins sur la même ligne et colonne. Voici un exemple : tous les carrés "jaune" sont à coté du carré "rouge".

To delete1.JPG

J'ai de la chance, car j'ai plus de motifs qu'il n'en faut à disposition: j'en ai 6.

Après essai, pour respecter cette règle, en avoir 4 était suffisant (eh oui c'est le célèbre théorème des 4 couleurs).

Avec 6, c'est donc très facile.

Je corse donc un peu la difficulté: ma surface est limitée et fait 10 colonnes par 14 lignes (ou l'inverse, cela revient au même).
Je souhaite ne pas avoir de répétition sur chaque ligne (c.a.d. un motif ne pourra apparaitre qu'une fois maximum), et une répétition maximale par colonne. Evidemment, je souhaite que cette même répétition varie, c'est à dire que globalement on ait la même proportion de chaque motif, aux arrondis près.

Voici un exemple, mais qui ne respecte pas parfaitement ces conditions:

To delete2.JPG

On est globalement pas mal:
- on respecte la règle d'être différent de ses voisins
- on respecte la règle d'une seule répétition par colonne (verticalement il y a 7 cases donc il y a forcément une répétition), et ce n'est pas la même répétition
- MAIS horizontalement on a des répétitions. Par exemple sur la deuxième ligne on a deux "1", sur la sixième ligne on a deux "6", etc. Ce n'est donc pas parfait.

To delete3.JPG

Ce problème est il résoluble ?
Surtout, à part en procédant au hasard et par ajustement comme j'ai fait, y a t'il une procédure applicable ou une méthode qui permette de colorier cette matrice ? Egalement avec une surface plus grande, permettant de respecter une homogénéité de densité de chaque motif.

Il y a beaucoup de littérature sur le pavage du plan (ou plus) et c'est passionant mais je n'ai pas trouvé grand chose sur le coloriage. Je pense qu'il y a peut être une analogie avec les méthodes de construction des carrés magiques.

La solution à ce problème, c'est bien, mais ce que j'aimerai surtout savoir c'est quelle est la méthode pour y parvenir (s'il en existe une).
-----

Publicité

[invite8af81491]

Après une nuit sans sommeil (pas à cause de ce problème, mais parce que j'ai attrapé froid), j'ai bien avancé sur ce problème.
Ce n'est pas étonnant, car des fois, simplement en se donnant la peine de le formaliser clairement pour d'autres, cela aide à identifier des pistes voire des solutions.

Il ne fallait pas regarder du coté des techniques de pavage, ni tout à fait du coté des carrés magiques, mais du coté des carrés latins (=unicité de chaque caractère sur chaque ligne/colonne).

Premièrement, il faut retirer l'aspect en damier qui est artificiellement perturbant.

Un carré latin n'est pas suffisant, car il faut aussi respecter la condition sur la non-adjacence de caractères identiques en diagonale.
Je ne connais pas le nom de cette propriété.
Par contre un carré latin dit pandiagonal respecte l'unicité de caractère sur les diagonales principales et les diagonales brisées. Donc il n'y aura pas de caractères identiques dans la diagonale immédiatement adjacente. C'est suffisant et même plus qu'il n'en faut (j'y reviens après).

Donc l'idée pour une solution générique, c'est que je remplis ma surface de carrés latins pandiagonaux d'ordre correspondant au nombre de caractères à disposition. Si cela ne tombe pas juste, il suffit de mettre une portion de ce carré latin, puisque cela gérera à la fois la frontière et les conditions de non-répétition au delà du nécessaire.

Voici un exemple:
Exemple.JPG

Coup de chance, on peut générer très facilement des carrés latins pantagoniaux quelque soit l'ordre (pour peu que celui ce ne soit pas divisible par 2 ou 3).

Par exemple, en appliquant la formule valeur = numéro de la ligne + 2 x numéro de la colonne, ceci modulo l'ordre
(trouvé sur math stackexchange)

En faisant celà, on n'a même plus à se préoccuper de la taille de la matrice. On a donc bien ici une solution générique, tel que je la recherchais. Elle est même un peu meilleure, car on garantie de surcroît une densité homogène par zone, et l'unicité dans les portions de diagonales.

Voici un exemple d'une matrice si on a un ordre 5:

Exemple ordre 5.JPG

J'ai mis la formule. J'ai mis, dans cette exemple, une matrice de 11x14 mais on voit bien qu'on aurait pu mettre n'importe quoi.
On reconnait bien les carrés latins pantagoniaux en 5x5, qui se répètent.

Pour la bonne bouche, voici un autre exemple d'ordre 7:

Exemple ordre 7.JPG

Je suis déjà très satisfait car je ne savais pas qu'il serait possible d'avoir une solution aussi élégante, mais pas arrivé au bout, car dans mon problème de départ, j'avais 6 motifs à disposition. Or, il n'existe pas de carrés latins pandiagonaux d'ordre divisible par 2 ou 3, donc pas de carrés latins pandiagonaux d'ordre 6 (Hedayat). Pas de chance !

Heureusement, le fait qu'il soit pandiagonal n'est pas nécessaire. Je dois juste en trouver qui respecte la condition de non répétition immédiatement en diagonal (c'est là que je suis arrivé).

[invite8af81491]

En fait il est possible de générer un carré latin d'ordre 6 qui respecte la condition sur les cases adjacentes en diagonale, simplement en faisant des décalages successifs.

La première ligne on écrit 1 2 3 4 5 6
La seconde on décale de deux cases
La troisième aussi
Les lignes 4 5 6 on décale d'une puis +2 et +2

Voilà ce que cela donne:



Cette méthode simple fonctionnera avec un carré 8 ou 9 ou 10 de la même manière.

Donc on a là aussi une solution générique possible lorsque les motifs sont de nombre multiples de 2 ou 3.

On peut considérer la question de départ comme résolue.

Ceci dit, cela ne me satisfait pas pleinement (ce n'était pas dans l'énoncé de départ) car c'est trop prévisible. A la fois
- la règle x+2y modulo ordre, pour les ordres non multiples de 2 ou 3
- cette dernière par décalage successifs pour les autres ordres

Je vais chercher d'autres carrés latins d'ordre 6 respectant cette condition, qui soient plus "mélangés". Pour l'instant, avec des permutations, c'est difficile.

[invite8af81491]

Non, finalement cela ne fonctionne pas. Pourquoi ? A cause du damier que j'ai sorti un peu trop vite.

Les solutions que j'ai donné fonctionnent parfaitement pour un carré dont toutes les cases sont pavées.

Pour mon souhait, d'avoir davantage de mélanges, j'ai recherché des carrés latins d'ordre 6 qui, sans être pandiagonaux (puisque cela n'existe pas), respectent la condition de ne pas avoir de répétition en diagonale adjacente. Ces animaux sont assez rares: d'après mes essais, je pense que la proportion est d'environ 2 ou 3 pour 10.000 carrés latins d'ordre 6. Comme il y a quand même 812 millions de CLs 6, on arrive quand même à en trouver...

En voici quelques exemples:

CL ordre 6.JPG

Là ou le bât blesse, c'est lors de la mise en damier, pour les sommes en colonnes.

Voilà ce que cela donne, si je souhaite remplir mon espace (en damier) avec le premier exemple:

Espace rempli avec le premier exemple.JPG

Je respecte bien les conditions de non-voisinage de nombre identiques.
J'ai bien (par construction) une unicité de chaque caractère sur chaque ligne.
Par contre, par colonne j'ai deux fois les mêmes caractères et pas l'autre moitié (exemple première colonne, j'ai plusieurs 2,1,3, et pas de 4,5,6). C'est normal puisque l'on recopie un chiffre sur deux, et, étant dans le même ordre, ce sont les mêmes.

On est condamné à avoir cela avec cette méthode de construction (à cause du damier).

Si j'essaie, pour le second carré, de mettre un autre CL respectant les conditions, ou une inversion ou translation du premier, cela ne fonctionne pas non plus car:
- soit il y a des collisions à l'interface
- la condition sur l'unicité en colonne est assez compliquée à respecter => le premier carré impose beaucoup plus fortement les choix sur le deuxième carré

Il pourrait sembler logique de juste faire un décalage, car on voir bien ici que la deuxième colonne avait vocation à être sous la première. Faisant cela c'est très bien, puisqu'on reconstitue le CL d'origine (qu'on a coupé à cause du damier). Mais on se retrouve avec des collisions supplémentaires:

CL Prob damier.JPG

On voit que les 4/5/6 de la deuxième colonne sont passés sous la première, et les 2/1/3 de la première passent sous la deuxième, ainsi de suite.
Par contre on se retrouve avec des collisions que l'on n'avait pas avant.

[A voir en vidéo sur Futura]