Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème du cavalier
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.