Problème du cavalier

thumb|Une des solutions du problème ouvert. Le problème du cavalier (ou encore polygraphie ou algorithme du cavalier ou cavalier d'Euler) est un problème mathématico-logique fondé sur les déplacements du cavalier du jeu d'échecs : un cavalier partant d'une case quelconque doit visiter chaque case sans y repasser. Si le but est généralement de parcourir toutes les cases du plateau avec un cavalier, une variante a été étudiée au Moyen-Orient médiéval où la pièce alterne entre un mouvement de cavalier et un mouvement en diagonale . Le problème a initialement porté sur le parcours d'un échiquier carré de 64 cases ou sur un demi-échiquier de 32 cases ; mais il a par la suite été étudié pour d'autres dimensions et également pour des formes non-rectangulaires, dont des croix. Le parcours peut être ouvert ou se refermer sur lui-même, auquel cas on parle de tour du cavalier. On peut aussi chercher des solutions avec des symétries particulières ou encore les plus longues solutions sans croisement. Knight's Tour 24x24.svg|Circuit du cavalier sur un échiquier de taille 24 × 24 obtenu par un [[Réseau de neurones artificiels|réseau de neurones]]. Knight's Tour of 130x130 Square Board.png|Parcours ouvert sur un échiquier de taille 130 x 130 obtenu en utilisant l'heuristique de Warnsdorf. Knights-Tour-Animation.gif|Parcours ouvert sur un échiquier de taille 5 x 5. Little_night's_tour-solution.png|Tour de cavalier sur un plateau en forme de croix. UncrossedKnightsPath7x7.svg|Circuit fermé sans croisement maximal sur un échiquier de taille 49 ; sa longueur est de 24 sauts. UncrossedKnightsPath8x8.svg|Parcours ouvert sans croisement maximal sur un échiquier de taille 64 ; sa longueur est de 35 sauts. On en trouve la première occurrence dans un traité d'ornement poétique indien, le Kavyalankara du poète Rudrata . Une solution au problème du parcours de l'intégralité d'un demi-échiquier de 32 cases a été trouvée dans un manuscrit datant du début du ; cette solution pouvant facilement être adaptée pour obtenir par juxtaposition le parcours complet d'un échiquier de 64 cases.