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.

Variantes Selon les pièces 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 .

Selon les formes de plateau 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.

Selon les parcours 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 croisementLa longueur maximale d'un parcours ouvert est donné par la , et celle d'un parcours fermé par la ..

Histoire Inde On en trouve la première occurrence dans un traité d'ornement poétique indien, le Kavyalankara du poète Rudrata C. Rajendran, "Caturanga movements described in Rudrata's Kavyalankara", dans Working-Papers "Indian Views", Förderkreis Scach-Geschichtsforschung e.V., novembre 2001..

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. Cette solution n'est pas un circuit car elle ne permet pas de revenir au point de départ.

Une encyclopédie indienne datant du donne un exemple de parcours fermé sur un échiquier de 64 cases. Charles Monneron rapporte d'Inde une autre solution au problème, qui sera imprimée par la suite dans l'Encyclopédie.

Solution du parcours sur un demi échiquier (900 ap. J.-C.). 1 30 9 20 3 24 11 26 16 19 2 29 10 27 4 23 31 8 17 14 21 6 25 12 18 15 32 7 28 13 22 5

Parcours fermé indien du . 2 51 6 15 64 25 28 23 7 14 1 50 5 22 43 26 52 3 8 63 16 27 24 29 9 62 13 4 49 42 21 44 12 53 10 17 36 45 30 41 61 56 59 48 31 40 35 20 58 11 54 37 18 33 46 39 55 60 57 32 47 38 19 34

Parcours ouvert à extrémités accolées rapporté par Monneron. 17 20 39 4 37 22 49 6 40 53 18 21 8 5 36 23 19 16 3 38 61 50 7 48 54 41 52 1 64 9 24 35 15 2 13 60 51 62 47 10 42 55 30 63 12 59 34 25 29 14 57 44 27 32 11 46 56 43 28 31 58 45 26 33

Le rajah s'est intéressé au sujet dans la première moitié du , on lui doit l'un des premiers parcours de cavalier connus dont la numérotation des cases forme un carré magique.

Monde arabe Circuit fermé thumb|Solution de al-Adli ar-Rumi. 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.

Des moyens mnémotechniques permettant de retenir une solution au circuit du cavalier sont attestés dans un manuscrit copié en 1141, lequel reprend des textes datant au plus du ; il s'agit de poèmes de 64 vers dont chacun est associé aux coordonnées d'une case de l'échiquier. Quatre tels poèmes sont connus, ce qui permet de conclure que le problème du circuit du cavalier était populaire dans le monde arabo-musulman, et qu'aucune méthode générale de construction d'un tel parcours n'était connue.

Autres règles de parcours Les savants arabes ont également étudié un problème voisin dans lequel la pièce à déplacer adopte alternativement le déplacement du cavalier et celui d'une autre pièce, conseiller ou éléphant, du chatrang (la version des échecs pratiquée dans le monde arabe médiéval). Le conseiller (ancêtre de la dame) et l'éléphant (ancêtre du fou) se déplaçant respectivement d'une case en diagonale et de deux cases en diagonale. Des poèmes ont également été composés pour en mémoriser des solutions.

Parcours fermé arabe d'un cavalier-éléphant. 49 42 40 51 9 34 36 11 47 52 54 45 39 12 14 33 41 50 48 43 37 10 8 35 55 44 46 53 15 32 38 13 61 22 16 63 5 26 28 7 19 56 58 21 31 64 2 25 17 62 60 23 29 6 4 27 59 20 18 57 3 24 30 1

Parcours fermé arabe d'un cavalier-conseiller. 37 14 16 35 33 18 24 31 15 36 34 17 19 32 30 25 13 38 48 11 21 26 28 23 39 12 10 49 27 20 22 29 9 42 40 47 61 50 52 63 43 8 46 41 51 60 62 53 45 6 4 59 57 2 64 55 7 44 58 5 3 56 54 1

Occident Pendant le Moyen Âge et la Renaissance On trouve dans un manuscrit anglo-normand du un parcours ouvert dont le but est d'amener le cavalier d'un coin à un autre. Plusieurs autres manuscrits plus tardifs donnent également des parcours ouverts sur des échiquiers ou des demi-échiquiers. Solution datée du . 23 26 11 4 49 52 45 40 10 3 22 25 46 41 48 51 27 24 5 12 53 50 39 44 2 9 28 21 42 47 54 59 29 20 13 6 61 58 43 38 8 1 16 19 32 35 60 55 17 30 7 14 57 62 37 34 . 15 18 31 36 33 56 63

Au début du Pierre Rémond de Montmort a étudié ce problème, et en donne une solution citée par Martin Grandin. Ce dernier reprend également deux autres solutions obtenues par Abraham de Moivre et par de Mairan.

Solution de Rémond de Montmort 58 23 62 15 64 21 54 13 61 16 59 22 55 14 51 20 24 57 10 63 18 49 12 53 9 60 17 56 11 52 19 50 34 25 36 7 40 27 48 5 37 8 33 26 45 6 41 28 32 35 2 39 30 43 4 47 1 38 31 44 3 46 29 42

Solution de Moivre où le carré central est visité après la bordure. 34 49 22 11 36 39 24 1 21 10 35 50 23 12 37 40 48 33 62 57 38 25 2 13 9 20 51 54 63 60 41 26 32 47 58 61 56 53 14 3 19 8 55 52 59 64 27 42 46 31 6 17 44 29 4 15 7 18 45 30 5 16 43 28

Solution fermée de Mairan. 56 9 26 43 54 7 32 29 25 44 55 8 27 30 53 6 10 57 24 39 42 33 28 31 23 40 45 36 1 52 5 34 46 11 58 41 38 35 64 51 59 22 37 48 19 2 15 4 12 47 20 61 14 17 50 63 21 60 13 18 49 62 3 16

Les travaux d'Euler Le mathématicien Leonhard Euler reprit l'étude scientifique en 1759. La « Solution d'une question curieuse qui ne paraît soumise à aucune analyse »Euler, Solution d'une question curieuse qui ne paraît soumise à aucune analyse, Mémoires de l'Académie Royale des Sciences et Belles Lettres, Année 1759, vol.15, pp.310-337, Berlin 1766 n'est cependant publiée qu'en 1766. Côme Alexandre Collini en publia une dans le Journal encyclopédique en 1773.

Euler y montre la solution de plusieurs problèmes: comment obtenir un trajet complet à partir d'un trajet partiel ; comment transformer un trajet ouvert en trajet fermé ; comment obtenir un trajet symétrique ; l'obtention de parcours sur des échiquiers carrés ou rectangulaires de taille variable ; l'obtention de parcours complets sur des échiquiers en forme de croix ou de croix rhombiques.

Euler a également commis des erreurs, il a ainsi affirmé qu'aucun trajet fermé n'est possible sur un échiquier de largeur 3 ; un contre-exemple a été donné en 1917 sur un échiquier de taille 3×10.Le théorème de Schwenk permet en fait d'affirmer que les seuls échiquiers de largeur 3 pour lesquels il n'existe pas de circuit fermé ont pour longueur 2, 4, 6, 8 ou un nombre impair..

Parcours fermé sur un échiquier de taille 3×10. 1 28 25 6 19 4 21 10 13 16 26 7 30 3 24 9 18 15 22 11 29 2 27 8 5 20 23 12 17 14

Études ultérieures

Au fil des siècles, les mathématiciens étudient ce thème en variant : les dimensions de l'échiquier, le nombre de joueurs, les propriétés du parcours, la façon dont un cavalier se déplace. Il a été proposé d'étudier les parcours du cavalier dans lesquels la somme des numéros de passage d'une case est constante suivant les lignes et les colonnesLa somme obtenue vaut alors un huitième de la somme totale des 64 numéros : .. En 1888, 83 tels parcours (dont 27 fermés) ont été déposés au Conservatoire National des Arts et Métiers ; aucun de ces parcours ne donne un carré magique car la somme n'est pas la même en suivant les diagonales. Un parcours a été découvert dans les années 1970.D'autres sources mentionnent d'autres découvertes entre 1888 et 1970, il semble que ce soit Jeux et Stratégie qui a été mal informée. Une recherche exhaustive a établi en 2003 que sur un échiquier il existe en tout 108 parcours différents formant des carrés magiques dont aucun n'a de diagonales égales.Certains parcours peuvent être numérotés depuis plusieurs cases de départ, en prenant cela en compte il y a 140 parcours au total, aux symétries près..

Parcours fermé qui est aussi un carré magique.(Sauf en ce qui concerne les diagonales) 42 59 2 17 40 15 22 63 3 18 41 60 21 64 39 14 58 43 20 1 16 23 62 37 19 4 57 44 61 38 13 24 56 45 6 29 12 25 36 51 5 30 55 48 33 52 11 26 46 7 32 53 28 9 50 35 31 54 47 8 49 34 27 10

Parcours fermé sur 12 × 12 cases qui est aussi un carré magique.(Y compris en ce qui concerne les diagonales) 12 by 12 Magic Knight's Tours. 1 70 107112 5 66 103116 9 64 99118108 111 2 69 104115 6 65 100 11710 63 71 106 109 4 113 102 67 8 61 9811912 110 3 72 105 68 7 114101 120 11 62 97 73 142 35 40 77 140 17 60 93 122 1358 36 39 74 141 32 41 92 121 16 59 96123143 34 37 76 139 78 55 18 125 94 57 14 38 75 144 33 42 31 126 91 56 15 12495 81 136 29 44 79 138 19 54 89 128 21 52 28 45 80 137 30 43 90 127 20 53 88 129135 82 47 26 133 84 49 24 131 86 5122 46 27 134 83 48 25 132 85 50 23 13087

En revanche un tel parcours existe pour n'importe quel échiquier carré dont la taille est un multiple de 4 autre que 4 ou 8..

Il est à noter que quelques travaux sont menés sur le thème du parcours de cavalier au .

Analyse mathématique right|thumb|270px|Graphe du cavalier montrant tous les mouvements possibles sur un échiquier 8x8 ; le nombre inscrit dans chaque case indique le nombre de cases accessibles depuis celle-ci.

Lien avec la théorie des graphes La recherche d'un tour du cavalier est un cas particulier des graphes hamiltoniens dans la théorie des graphes. De plus comme un cavalier passe toujours d'une case noire à une case blanche et vice-versa, il s'ensuit que le graphe des mouvements du cavalier est un graphe biparti.

Existence d'un parcours ouvert sur un échiquier rectangulaire Dans le cas d'une recherche d'un parcours ne bouclant pas nécessairement sur lui-même, il a été prouvé qu'il existe une solution pour tout échiquier rectangulaire dont la longueur et la largeur sont supérieures ou égales à 5.

Existence d'un circuit fermé sur un échiquier rectangulaire Les tours de cavaliers peuvent se faire sur des damiers de différente taille et sur des formes différentes (rectangle, cube, pavé, spirale infinie, etc.), mais il est nécessaire que le nombre de cases soit pair. Dans le cas d'un échiquier rectangulaire on a le résultat d'existence suivant:

Condition 1

La condition 1 empêche l'existence d'un tour fermé, pour de simples raisons de parité et de coloriage. Sur un échiquier noir et blanc standard, un cavalier se déplace du blanc vers le noir ou inversement. Donc un tour fermé doit visiter le même nombre de cases noires et blanches, et le nombre des cases visitées doit être pair. Or si m et n sont impairs, le nombre de cases est impair donc aucun tour fermé n'existe. Par contre il peut exister des tours ouverts.

Condition 2

Selon cette condition, il n'existe pas de tour fermé si le plus petit côté est 1, 2, ou 4.

Si m = 1 ou 2, le cavalier ne peut pas atteindre toutes les cases (sauf dans le cas trivial ). On peut aussi montrer l'absence de tour fermé dans le cas par un argument de coloriage.

thumb|Le cavalier doit alterner vert et rouge.