Résumé : Le jeu du démineur a été popularisé par Microsoft : on le retrouve dans différentes versions de son système d’exploitation. Le jeu de l’hexagone et de la marguerite est probablement son ancêtre. Pour décoder ou « déminer » automatiquement une grille hexagonale, il faut faire appel à la logique et aux mathématiques. De plus la technique de codage permet de réaliser des mosaïques spectaculaires dont la texture est, une nouvelle fois, fractale.
Mots-clés : hexagone, codage, équation.
L’exercice s’inspire de l’article Du jeu de l’hexagone et de la marguerite à la création de mosaïques de Pierre Tougne, Pour la Science, octobre 1985.
Le jeu de l’hexagone a été imaginé par un auteur belge, Jean-Pierre Labrique ; ce jeu de l’hexagone et de la marguerite soulevait des problèmes mathématiques intéressants à propos des grilles permutables finies ou infinies (les résultats mathématiques donnés dans cet exercice sont dûs à Pierre Billoir). Il se joue sur une grille de cases circulaires ou hexagonales disposées selon un réseau hexagonal régulier. Cette grille peut être de forme quelconque (dans sa forme originelle, il y a 37 cases). Pour remplir cette grille, on noircit arbitrairement un certain nombre de cases puis l’on code cette grille à l’aide d’une marguerite à sept trous dont on applique la case centrale sur chaque case de la grille l’une après l’autre.
Cette marguerite sélectionne les six cases voisines de la cases choisies (ou cinq si la case est sur un bord ou quatre quand c’est une case sommet) et l’on inscrit dans la case centrale en face du trou de la marguerite, le nombre de cases noires situées dans la marguerite. En procédant ainsi sur toutes les cases de la grille de départ, on obtient une grille codée. Sur cette grille, on n’indique évidemment pas quelles cases sont noires. Le but du jeu est de reconstituer le tableau original des cases à partir de la seule grille codée, c’est-à-dire déterminer quelles cases sont noires.
Comment décoder une grille ? Il suffit en général d’exploiter les particularités du codage pour déterminer la coloration de certaines cases puis, à partir ce ces cases, de décoder le contenu des autres cases de proche en proche de façon logique.
Une autre application du codage de la marguerite permet de créer des mosaïques. L’idée est la suivante : on part d’un motif quelconque de cases noires sur une grille hexagonale que l’on code à l’aide de la marguerite en plaçant sa case centrale sur ces cases noires et les plus proches voisines des cases noires. Ce codage étant effectué, on en déduit le motif de la génération suivante en noircissant les cases de code impair et laissant blanche les cases de code pair, puis on recommence.
Ce procédé n’est autre que la transposition au réseau hexagonal de l’automate cellulaire d’Edward Friedkin. Manuellement le procédé devient vite fastidieux mais il se programme facilement sur ordinateur. C’est le but de ce problème.
Il y a évidemment des cas triviaux où une case a pour code 0, auquel cas la case et toutes ses voisines sont blanches ainsi que le code 7 pour une case intérieure, ou le code 5 pour une case de bord et enfin 4 pour une case de sommet, où l’on peut affirmer que la case et toutes ses voisines sont noires.
Hormis les points d’attaques évidents il existe un certain nombre de dispositions des nombres codes de deux cases voisines dits « points faibles de la grille », qui permettent de préciser le noircissement ou le non-noircissement de certaines cases (ces points faibles se situent le plus souvent sur les cases du bord car le nombre de cases prises en compte est plus faible et les possibilités restreintes).
Si la grille ne présente aucun point faible, il suffit de « créer » un ou des points faibles en postulant qu’une case bien choisie est soit noire, soit blanche. Si l’on suppose que la case choisie est blanche on forme une grille dérivée où cette case est supposée noire, c’est-à-dire que l’on ajoute 1 à cette case et à ses voisines, créant ainsi, sur cette nouvelle grille, le ou les points faibles voulus.
Inversement si l’on suppose la case noircie au départ on forme la grille dérivée en soustrayant 1 du contenu de la case et des voisines. Sur cette grille dérivée comportant des points faibles on procède au décodage qui, s’il peut se poursuivre jusqu’au bout, donne le coloriage de la grille de départ (ne pas oublier de rétablir la coloration de la case choisie au départ). Si en revanche on arrive à une contradiction, on peut en déduire seulement que l’hypothèse était fausse et donc la coloration d’une seule case ; il faut alors créer un autre point faible et recommencer.
La solution actuellement proposée est donnée par les fichiers MatLab : pavagehexa.m, defhexa.m, demohexa.m, hexagone.m, marguerite.m et clic.m.