Résumé : de nombreux casse-tête sont difficiles à résoudre car le nombre de possibilités est énorme. Le jeu d’Engel est composé de deux cercles inscrits dans des hexagones ; lorsqu’on mélange les pièces, il est particulièrement difficile de le reconstituer.
Mots-clés : combinatoire, hexagone, permutation.
L’exercice s’inspire de l’article Des casse-tête fascinants à une, deux et trois dimensions extrait du livre Récréations informatiques de A. Dewdney, Pour La Science, 1984.
A. Dewdney débute son article en précisant : « Ecrire un programme d’aide à la conception d’un casse-tête est sans doute tout aussi passionnant que d’écrire un programme qui résout les casse-tête. »
Il décrit ensuite plusieurs casse-tête et termine son article par une description du jeu de D. Engel : « Le troisième puzzle, celui de D. Engel, m’a procuré de bonnes heures de distraction, mais je dois avouer que son casse-tête m’a aussi prodigieusement énervé : je n’ai pas encore réussi à trouver une méthode de résolution. Selon D. Engel, son puzzle a même tenu en échec plusieurs spécialistes du cube de Rubik.
L’objet se compose de deux disques sécants, encastrés dans un support de matière plastique ; la partie extérieure de chaque disque est recouverte par 12 pièces : six « pierres » (qui ressemblent à des triangles obèses) alternent avec six « os » (dont la forme évoque des rectangles sous-alimentés). L’intersection des deux disques comprend un os encadré de deux pierres. La couronne d’os et de pierres contenue dans chaque disque peut tourner : lorsque, par exemple, le disque supérieur tourne de 60 degrés, l’os et une des pierres qui étaient communs aux deux disques sont remplacés par deux autres pièces du même type. En faisant tourner alternativement les deux disques d’un angle multiple de 60 degrés, on mélange complètement les pièces.
Dans sa configuration initiale, le puzzle, formé de deux disques et des bords du support, est divisé en dix zones colorées : sur les huit zones extérieures on trouve quatre couleurs et deux dans les zones internes.
Chaque « pierre » figure dans trois zones différentes et possède donc trois couleurs ; en revanche, les « os » ne se trouvent simultanément que dans deux zones et n’ont donc que deux couleurs.
Lorsqu’on mélange les pièces en faisant alternativement tourner les disques, on obtient une mosaïque de couleurs. Pourquoi ce puzzle est-il aussi difficile que le cube Rubik, malgré le nombre restreint de mouvements possibles ? »
L’intérêt d’un tel jeu réside dans la recherche d’algorithmes performants pour résoudre le puzzle.
La représentation du jeu d’Engel est relativement complexe : on commence en représentant les deux hexagones du centre. Puis on représente une pierre : elle est formée d’arcs de cercles (d’angle 2π∕9) et du barycentre (en fait un des sommets de l’hexagone). On remplit les trois parties avec les couleurs adéquates.
Pour les os, on travaille de façon similaire : on prend deux arcs de cercle ; le trait du milieu relie également deux sommets de l’hexagone.
Les autres os et les autres pierres sont obtenues par des rotations d’angle π∕3.
Pour gérer le déplacement des pierres et des os, il suffit de les numéroter. Ensuite, une rotation dans le sens contraire des aiguilles d’une montre consiste à placer le dernier numéro en première position et de décaler les autres pierres dans les positions suivantes.
Une difficulté provient du passage dans les positions centrales : il faut permuter les couleurs lorsqu’on tourne la roue de droite (dans le sens contraire des aiguilles d’une montre et inversement).
La solution actuellement proposée est donnée par les fichiers MatLab : engel.m, clicengel.m et demoengel.m.