problème du cavalier

cavalier polygraphe
polygraphie du cavalier
cavalier d’Euler

COMBINATOIRE

Le problème ou algorithme du cavalier est un problème de logique basé sur les déplacements du cavalier du jeu d’échecs. Un cavalier est placé sur une case quelconque d’un échiquier, il doit passer par toutes les cases (sans passer deux fois par la même).

Ce problème est connu depuis longtemps en Orient. Il a été étudié en Occident par Montfort, puis Euler .
Il a aussi été étudié en modifiant certains paramètres (taille de l’échiquier).

Dans le cadre de la théorie des graphes, c’est un exemple de graphe hamiltonien.