Le cavalier d’Euler à un problème

cavalier Euler

Connaissez-vous le problème du cavalier (ou encore la polygraphie ou l’algorithme du cavalier) ? C’est un problème mathématico-logique fondé sur les déplacements du cavalier. Un cavalier posé sur une case quelconque de l’échiquier doit en visiter toutes les cases sans passer deux fois sur la même. Le cavalier d’Euler est connu depuis fort longtemps. Vers 840, le joueur et théoricien d’Échecs arabe al-Adli ar-Rumi en donne déjà une solution. On en trouve la première occurrence dans un traité d’ornement poétique indien, le Kavyalankara du poète Rudrata.

cavalier Euler
Une des milliers de milliards de solutions. Et pourtant, ce n’est pas si facile !

Depuis lors, de nombreux mathématiciens s’y sont intéressés, en particulier Leonhard Euler (1707-1783). Car plus qu’un jeu de patience, il est relié à un champ extrêmement important et fécond des mathématiques appelé théorie de graphes qui peut avoir une application très concrète dans notre vie quotidienne. Les graphes modélisent des objets en interaction : connexions routières, ferroviaires ou aériennes, plan d’une ville et de ses rues en sens unique, liens entre les composants d’un circuit électronique.

Les mathématiciens prirent rapidement conscience du très grand nombre de solutions possibles. En 1823,  H.C. Warnsdorff énonce une règle pragmatique et efficace, conseillant de choisir la case qui laisse le moins de possibilités de fuite, c’est-à-dire, la case la plus enclavée. En 1997, un chercheur australien, Brendan McKay conclut à l’existence de treize mille milliards de possibilités. Pour se donner une idée de ce chiffre astronomique, il faudrait 25 ans à un super ordinateur, découvrant un million de solutions par minute, pour en venir à bout ! Le mathématicien uruguayen Ernesto Mordecki en donne aujourd’hui une estimation plus précise : 1,22 million de milliards de parcours possibles ! La pile de chaque solution, dessinée sur une feuille de papier et empilée les unes sur les autres, s’élèverait jusqu’au soleil !

Et pourtant, malgré tant de solutions, la tâche n’est pas si aisée d’en découvrir une seule. Tentez votre chance sur l’excellent blog Procrastin :

cavalier Euler

Si ce cavalier polygraphe éveilla la curiosité des mathématiciens, il n’en stimula pas moins l’imaginaire des poètes et des romanciers. Georges Perec, dans son roman La vie mode d’emploi, retrace la vie d’un immeuble parisien, entre 1875 et 1975, évoquant ses habitants, les objets qui y reposent et les histoires qui directement ou indirectement l’ont animé. Chaque chapitre traite d’une pièce ou d’un endroit précis de l’immeuble et le décrit de façon méthodique, presque clinique, avec une jubilation de cruciverbiste, « quelque chose comme un souvenir pétrifié, comme un de ces tableaux de Magritte où l’on ne sait pas très bien si c’est la pierre qui est devenue vivante ou si c’est la vie qui s’est momifiée, quelque chose comme une image fixée une fois pour toutes, indélébile ». Le passage d’une pièce/chapitre à l’autre obéit en  fait à la règle précise de notre cavalier polygraphe.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *