Le Cavalier d'Euler
(The Knight's
Tour)
Le problème
Le jeu d'échecs se joue sur un échiquier qui est une grille de 8 cases par 8 cases.
Le Cavalier est une pièce de ce jeu.
Il se déplace par sauts.
Le problème d'Euler consiste à placer le Cavalier sur une case quelconque de l'échiquier et à le faire parcourir les 63 autres cases en exactement 63 sauts consécutifs.
C'est ce que l'on appelle un tour du Cavalier.
Si le Cavalier peut sauter de la case finale à la case initiale d'un tour alors c'est un tour fermé.
En fait on connaît bon nombre de tours. En tenant compte des règles énoncées dans cet article j'obtiens un programme qui en calcule environ 200 000 par seconde.
Le but ultime, que personne n'a encore réussi à atteindre, consiste aujourd'hui à trouver des lois qui permettent de dénombrer toutes les solutions en un temps "acceptable" ou de trouver une formule qui permette de calculer le nombre de solutions.
Pour simplifier le problème et aussi pour tester un algorithme on réduit souvent l'échiquier à des
dimensions inférieures.
Les règles me permettent de trouver rapidement les 1.728 tours d'un échiquier 5x5, les 6.637.920 tours d'un échiquier 6x6 et les 165 575 218 320
tours d'un échiquier 7x7.
Mais il faut encore une nette amélioration pour résoudre complètement l'échiquier 8x8 en un temps acceptable.
Retour à la page principale.