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