Voir la source de Problème du cavalier

[[Fichier:Knight's tour anim 2.gif|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 [[Règles du jeu d'échecs#Déplacements|déplacements du cavalier]] du [[Échecs|jeu d'échecs]] : un [[cavalier (échecs)|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 {{infra|Monde arabe}}.

=== 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 croisement<ref>La longueur maximale d'un parcours ouvert est donné par la {{OEIS|A003192}}, et celle d'un parcours fermé par la {{OEIS|A157416}}.</ref>.

<gallery>
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.
</gallery>

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

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 {{Xe siècle}} ; cette solution pouvant facilement être adaptée pour obtenir par juxtaposition le parcours complet d'un échiquier de 64 cases<ref name="Sesiano p163"> {{Harvsp|Sesiano|2015|id=sesiano|p=163}}</ref>. 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 {{XVIIe siècle}} donne un exemple de parcours fermé sur un échiquier de 64 cases<ref> {{Harvsp|Sesiano|2015|id=sesiano|p=162}}</ref>. [[Charles Claude Ange Monneron|Charles Monneron]] rapporte d'Inde une autre solution au problème, qui sera imprimée par la suite dans l'[[Encyclopédie ou Dictionnaire raisonné des sciences, des arts et des métiers|Encyclopédie]]<ref name="Sesiano p161"> {{Harvsp|Sesiano|2015|id=sesiano|p=161}}</ref>.
{{Col-début|width=50%}}
{{Col-3}}
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |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
|}
{{Col-3}}
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |Parcours fermé indien du {{s-|XVII|e}}.
|-
|  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
|}
{{Col-3}}
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |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
|}
{{Col-fin}}

Le rajah {{Lien|trad =  Krishnaraja Wadiyar III}} s'est intéressé au sujet dans la première moitié du {{XIXe siècle}}, on lui doit l'un des premiers parcours de cavalier connus dont la numérotation des cases forme un carré magique<ref name="mayhematics">{{Lien web|url = http://www.mayhematics.com/t/1d.htm|site=mayhematics|titre = History of Magic Knight's Tour|langue = anglais|année =2004}}</ref>.

=== Monde arabe ===
==== Circuit fermé ====
[[Image:Marche_du_cavalier_selon_al-Adli_ar-Rumi.png|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|al-Adli ar-Rumi]] en donne déjà une solution.

Des moyens [[mnémotechnique]]s 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 {{Xe siècle}} ; il s'agit de poèmes de 64 [[vers]] dont chacun est associé aux coordonnées d'une case de l'échiquier<ref> {{Harvsp|Sesiano|2015|id=sesiano|p=157}}</ref>. 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<ref> {{Harvsp|Sesiano|2015|id=sesiano|p=159}}</ref>.

==== 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 (échecs)|dame]]) et l'éléphant (ancêtre du [[Fou (échecs)|fou]]) se déplaçant respectivement d'une case en diagonale et de deux cases en diagonale<ref> {{Harvsp|Sesiano|2015|id=sesiano|p=160}}</ref>. Des poèmes ont également été composés pour en mémoriser des solutions<ref name="Sesiano p161" />.
{{Col-début|width=50%}}
{{Col-2}}
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |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'''
|}
{{Col-2}}
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |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'''
|}
{{Col-fin}}

=== Occident ===
==== Pendant le Moyen Âge et la Renaissance ====
On trouve dans un manuscrit [[anglo-normand (langue)|anglo-normand]] du {{XIVe siècle}} un parcours ouvert dont le but est d'amener le cavalier d'un coin à un autre<ref name="Sesiano p163" />. Plusieurs autres manuscrits plus tardifs donnent également des parcours ouverts sur des échiquiers ou des demi-échiquiers<ref> {{Harvsp|Sesiano|2015|id=sesiano|pages=165-167}}</ref>.
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |Solution datée du {{s-|XIV|e}}.
|-
| 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 {{s-|XVIII|e}} ====
[[Pierre Rémond de Montmort]] a étudié ce problème, et en donne une solution citée par [[Martin Grandin]]<ref> {{Harvsp|Sesiano|2015|id=sesiano|pages=168}}</ref>. Ce dernier reprend également deux autres solutions obtenues par [[Abraham de Moivre]] et par [[Jean-Jacques Dortous de Mairan|de Mairan]]<ref>{{Harvsp|Sesiano|2015|id=sesiano|pages=169}}</ref>.
{{Col-début|width=50%}}
{{Col-3}}
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |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
|}
{{Col-3}}
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |Solution de 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
|}
{{Col-3}}
{| class="wikitable" border="1"
|-
!colspan="8" style="text-align: center;" |Solution fermée de 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
|}
{{Col-fin}}

==== 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 »<ref name=Euler>Euler, ''[http://eulerarchive.maa.org/docs/originals/E309.pdf 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</ref> n'est cependant publiée qu'en [[1766]]. [[Cosimo Alessandro Collini|Côme Alexandre Collini]] en publia une dans le ''[[Journal encyclopédique]]'' en 1773.

Euler y montre la solution de plusieurs problèmes<ref>{{Harvsp|Sesiano|2015|id=sesiano|pages=}}</ref>:
* 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 [[wikt:rhombique|rhombiques]].

<gallery>
Cavalier Euler Tour.svg|Une solution publiée par Euler<ref name=Euler/>.
Cavalier Euler Tour Symetrique.svg|Une solution proposée par Euler<ref name=Euler/>. Celle-ci est symétrique par rapport au centre de l'échiquier, et parcourt d'abord la moitié inférieure de ce dernier, puis la partie supérieure.
Cavalier Euler Tour10x10.svg|Solution du tour sur un échiquier 10x10, proposée par Euler<ref name=Euler/>.
</gallery>

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<ref name = "delahaye">{{Article|langue = français|titre = Du flou et du faux en mathématiques|auteur = [[Jean-Paul Delahaye]]|périodique = [[Pour la Science]]|numéro = 516|mois = octobre|année = 2020}}.</ref>{{,}}<ref group = N>Le théorème de Schwenk {{infra|Existence d'un circuit fermé sur un échiquier rectangulaire}} 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.</ref>.

{| class="wikitable" border="1"
|-
!colspan="10" style="text-align: center;" |Parcours fermé sur un échiquier de taille 3×10<ref name = "delahaye"/>.
|-
| '''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 colonnes<ref group="N">La somme obtenue vaut alors un huitième de la [[Nombre triangulaire|somme totale des 64 numéros]] : <math>\frac{64 \times 65}{2} \times \frac{1}{8}= 260</math>.</ref>. 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<ref name = "jessie18"/>. Un 84{{e}} parcours a été découvert dans les années 1970<ref name = "jessie18">{{Article|langue = français|auteur = [[Pierre Berloquin]]|périodique = [[Jeux et Stratégie]]|numéro = 18|passage = 24-26|titre = Manœuvre de cavalerie|mois = novembre-décembre|année = 1982}}.</ref>{{,}}<ref group=N>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</ref>. 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<ref name="mayhematics"/>{{,}}<ref>{{Lien web|langue = anglais|titre = There Are No Magic Knight's Tours on the Chessboard|site = [[MathWorld]]|auteur = [[Eric W. Weisstein]]|date = 6 août 2003|url =https://mathworld.wolfram.com/news/2003-08-06/magictours/}}.</ref>{{,}}<ref group=N>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.</ref>. 
{{Col-début|width=50%}}
{{Col-3}}
{| class="wikitable"
!colspan="8" style="text-align: center;" |Parcours fermé qui est aussi un carré magique.<br/>(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
|}
{{Col-3}}
{| class="wikitable"
!colspan="12" style="text-align: center;" |Parcours fermé sur 12 × 12 cases qui est aussi un carré magique.<br/>(Y compris en ce qui concerne les diagonales)<ref name = "numberphile"/>{{,}}<ref>{{en}} [https://www.mayhematics.com/t/md.htm 12 by 12 Magic Knight's Tours].</ref>
|-
| '''1'''  || 70 || 107||112 ||  5 || 66 || 103||116|| 9  || 64 || 99||118
|-
|108 ||111 || 2  || 69 || 104||115 || 6  ||65 || 100|| 117||10 ||63
|-
| 71 ||106 || 109|| 4  ||113 || 102|| 67 || 8 || 61 ||  98||119||12
|-
| 110||  3 || 72 ||105 || 68 || 7  || 114||101|| 120|| 11 ||62 ||97
|-
| 73 ||142 || 35 || 40 || 77 ||140 || 17 ||60 || 93 ||122 || 13||58
|-
| 36 || 39 || 74 ||141 || 32 || 41 || 92 ||121|| 16 || 59 || 96||123
|-
|143 || 34 || 37 || 76 || 139|| 78 || 55 ||18 ||125 || 94 ||57 ||14
|-
| 38 || 75 || '''144'''|| 33 || 42 || 31 ||126 ||91 || 56 || 15 ||124||95
|-
| 81 || 136|| 29 || 44 || 79 || 138|| 19 ||54 || 89 ||128 ||21 ||52
|-
| 28 || 45 || 80 ||137 || 30 ||  43|| 90 ||127|| 20 || 53 ||88 ||129
|-
|135 || 82 || 47 || 26 ||133 || 84 || 49 ||24 ||131 || 86 || 51||22
|-
| 46 || 27 ||134 || 83 || 48 || 25 || 132|| 85|| 50 || 23 ||130||87
|}
{{Col-fin}}
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<ref name = "numberphile">{{Youtube|langue = en|titre = Magic Chess Tours (with Knights and Kings)|date = {{1er}} avril 2024|chaîne = [[Numberphile]]|id = RytNZ2btZxE}}.</ref>.

Il est à noter que quelques travaux sont menés sur le thème du parcours de cavalier au {{XXIe siècle}}<ref name = "delahaye"/>.

== Analyse mathématique ==
[[Image:Knight's graph showing number of possible moves.svg|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 [[Graphe hamiltonien|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<ref name=Cull1978>{{Article|langue = anglais | auteur1 =P. Cull|auteur2=J. De Curtins|titre = Knight's Tour Revisited|périodique = Fibonacci Quarterly|volume = 16|année = 1978|pages = 276–285 |lire en ligne=http://www.fq.math.ca/Scanned/16-3/cull.pdf}}</ref>{{,}}<ref name=Conrad1994>{{Article |langue = anglais|auteur1=A. Conrad |auteur2=T. Hindrichs |auteur3=H. Morsy | auteur4=I. Wegener |titre=Solution of the Knight's Hamiltonian Path Problem on Chessboards |journal=Discrete Applied Mathematics |volume=50 |numéro=2 |pages=125–134 |année=1994 |doi=10.1016/0166-218X(92)00170-Q }}</ref>.

=== 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<ref>{{Article
 |langue = anglais
 | auteur=Allen J. Schwenk
 | titre=Which Rectangular Chessboards Have a Knight’s Tour?
 | périodique=Mathematics Magazine
 | année=1991
 | pages=325–332}}</ref>:

{{Théorème|nom = Théorème de Schwenk|
énoncé=Pour tout échiquier {{nobr|''m'' × ''n''}} tel que ''m'' soit inférieur ou égal à ''n'', il existe un tour du cavalier,  '''à moins''' qu'une des conditions suivantes (ou plus) ne soit vraie :
# ''m'' et ''n'' sont impairs; ''n'' est différent de 1.
# ''m'' = 1, 2, ou 4 ; ''n'' est différent de 1.
# ''m'' = 3 et ''n'' = 4, 6 ou 8.
|style=display:table}}

==== 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 {{nobr|1 × 1}}). On peut aussi montrer l'absence de tour fermé dans le cas {{nobr|4 × ''n''}} par un argument de coloriage.

[[Image:Grid4xnColoredSquares.jpg|thumb|Le cavalier doit alterner vert et rouge.]] 
Supposons qu'il existe un tour fermé sur un échiquier 4 × ''n''. Appelons <math>A_1</math> l'ensemble des cases noires et <math>A_2</math> l'ensemble des cases blanches visitées par le tour, sur un échiquier noir et blanc standard. Regardons la figure de droite. Appelons <math> B_1 </math> l'ensemble des cases vertes et <math> B_2 </math> celui des cases rouges. Elles sont en nombre égal. Remarquons que le cavalier passe obligatoirement d'une case de <math> B_1 </math> à une case de <math> B_2 </math>. Comme il doit visiter chaque case, il doit aussi passer d'une case de <math> B_2 </math> à une case de <math> B_1 </math>  (sinon il devrait parcourir deux cases consécutives ou plus de <math> B_1 </math> ensuite, ce qui est impossible).

L'examen de ce tour hypothétique donne une contradiction :
#La première case du tour sera dans <math> A_1 </math> et <math> B_1 </math>. Sinon il suffit d'intervertir les définitions de <math> B_1 </math> et <math> B_2 </math>.
#La seconde case doit être dans <math> A_2 </math> et <math> B_2</math>.
#La troisième case doit être dans <math> A_1 </math> et <math> B_1 </math>.
#La quatrième case doit être dans <math> A_2 </math> et <math> B_2 </math>.
#Et ainsi de suite.

Il en découle que les ensembles <math> A_1 </math> et <math> B_1 </math> sont confondus, tout comme les ensembles <math> A_2 </math> et <math> B_2 </math>. C'est absurde, donc aucun tour n'existe dans le cas {{nobr|4 × ''n''}}, et ce quel que soit ''n''.

==== Condition 3 ====

On peut prouver la condition 3 au cas par cas. Rechercher un tour fermé dans les cas  {{nobr|3 × 4}}, {{nobr|3 × 6}}, {{nobr|3 × 8}} échoue rapidement. Pour les cas {{nobr|3 × ''n''}}, avec ''n'' pair et plus grand que 8, on construit les tours fermés par récurrence, en répétant les mouvements.

==== Autres cas ====

Nous avons prouvé l'inexistence d'un tour fermé dans les trois conditions mentionnées.
Prouver l'existence d'un tel tour dans les autres cas est plus compliqué<ref>{{Ouvrage|langue=en|auteur1=John J. Watkins|titre=Across the Board|sous-titre=the Mathematics of Chessboard Problems|éditeur=[[Princeton University Press]]|année=2004|pages totales=257|isbn=978-0-691-11503-0|lire en ligne=https://books.google.com/books?id=TtkLIE47DCkC&printsec=frontcover}}</ref>.

=== Obtention effective d'un parcours du cavalier ===
{{...}}
Pour réussir un parcours, il suffit de choisir pour chaque nouveau saut une case libre parmi celle offrant le moins de sauts ultérieurs possibles, quitte à annuler les derniers coups en cas d'impasse : c'est un exercice classique de programmation.

Bien que le problème général de recherche d'un circuit hamiltonien dans un graphe soit [[NP-complet]], le cas particulier du tour du cavalier peut être résolu en [[Analyse de la complexité des algorithmes|temps linéaire]]<ref name=Conrad1994/>.

=== Dénombrement des solutions ===
Il y a {{formatnum:26534728821064}} circuits fermés différents sur un échiquier carré de 64 cases<ref>{{Article
 | langue=anglais
 | auteur=Brendan McKay
 | titre=Knight's Tours on an {{nowrap|8 × 8}} Chessboard
 | périodique=Technical Report TR-CS-97-03
 | éditeur=Department of Computer Science, Australian National University
 | année=1997
 | lire en ligne=http://www.combinatorics.org/ojs/index.php/eljc/article/downloadSuppFile/v3i1r5/mckay
}}</ref>, et il y en a {{formatnum:9862}} sur un échiquier carré de 36 cases<ref>{{MathWorld|nom_url=KnightsTour|titre=Knight's Tour}}</ref>.

Le nombre de parcours ouverts pour un échiquier carré est donné par {{OEIS|A165134}} :
{| class="wikitable" border="1"
|-
! Dimension de l'échiquier : || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8
|-
| Nombre de parcours ouverts : || 1 || 0 || 0 || 0 || {{formatnum:1728}} || {{formatnum:6637920}} || {{formatnum:165575218320}} || {{formatnum:19591828170979904}}
|-
|}

== Applications ==
{{…}}
=== Cryptographie ===
{{…}}
* Le problème du cavalier a été proposé pour concevoir des schémas de chiffrement en [[cryptographie visuelle]]<ref>{{Article|langue = anglais|titre = Image Encryption Scheme Based on Knight’s Tour Problem|année = 2015|périodique = Procedia Computer Science|auteur1 = Manpreet Singha|auteur2 = Ajay Kakkarb |auteur3 = Manjinder Singhc|lire en ligne = https://www.sciencedirect.com/science/article/pii/S1877050915032457}}.</ref>;
* Le problème a aussi été proposé pour la génération de [[Générateur de nombres pseudo-aléatoires|nombres pseudo-aléatoires]] de qualité cryptographique<ref>{{Article|langue = anglais|titre = Generating and Expanding of an Encryption Key Based on the Knight's Tour Problem|auteur1 = Ali Shakir Mahmood|auteur2 = Mohd Shafry Mohd Rahim|périodique = Journal of Theoretical and Applied Information Technology|date = 15 avril 2017|lire en ligne = http://www.jatit.org/volumes/Vol95No7/17Vol95No7.pdf|volume = 95|numéro = 7}}.</ref>.

== Littérature ==
* [[Rudrata]], un poète du [[Cachemire]] de la fin du {{s-|IX|e}} (vers 825-850), propose un problème d'Euler rédigé en vers : « Les Ornements de la poésie », écrit en [[sanskrit]], qui comporte un ensemble de versets basés sur des séries de syllabes en relation avec le parcours cavalier.
* [[Mikhaïl W. Ramseier]], dans son roman [[Nigrida]], propose une intrigue qui tourne autour d'un [[cryptogramme]] basé sur un [[chiffre de Vigenère]] dissimulé au sein d'un problème du cavalier d'Euler.
* Au {{s-|XX|e}}, le groupe d'écrivains [[Oulipo]] utilise ce problème. L'exemple le plus remarquable est le tour ''10 × 10'' qui détermine l'ordre des chapitres dans le livre de [[Georges Perec]] : ''[[La Vie mode d'emploi]]''. Le même auteur a également utilisé un ''9 × 9'' dans ''Deux cent quarante-trois cartes postales en couleurs véritables''.

== Notes et références ==
=== Notes ===
{{références|group = N}}

=== Références ===
{{Traduction/Référence|en|Knight's tour|806712977}}
{{références}}


== Bibliographie ==
* {{Ouvrage|langue=fr|auteur1=Jacques Sesiano|titre=Euler et le parcours du cavalier|sous-titre=Avec une annexe sur le théorème des polyèdres|lieu=Lausanne|éditeur=[[Presses polytechniques et universitaires romandes]]|année=2015|pages totales=272|isbn=978-2-88074-857-9|présentation en ligne={{Google Livres|PGLzDAAAQBAJ}}|lire en ligne=https://link-springer-com.bases-doc.univ-lorraine.fr/content/pdf/10.1007%2Fs00283-017-9708-z.pdf|id=sesiano|libellé=Sesiano15|plume=oui}}

== Articles connexes ==
* [[Twixt (jeu)|Twixt]]

== Liens externes ==
{{Autres projets
 | commons = Category:Knight's Tours
}}
* {{Lien web|langue=anglais|auteur1=George Jelliss|titre=Knight's Tour Notes|url=http://www.mayhematics.com/t/t.htm|site=mayhematics.com|date=2000 - 2017|consulté le=3 novembre 2017}} : compilation de parcours de différentes époques, avec différentes règles et différentes formes de plateau.
* [http://classes.bnf.fr/echecs/litt/perec.htm La description du problème et quelques références par Georges Perec]'' extrait de la revue [[l'Arc (revue)|l'Arc]]'', n°78.
* [http://www.procrastin.fr/tool/polygraphe/ Une application en Flash pour jouer au problème du cavalier], sur procrastin.fr
* {{en}} [http://dmitrybrant.com/knights-tour Programme pour résoudre le problème du cavalier], sur le [[blog]] de Dmitry Brant


{{Portail|mathématiques|échecs|informatique théorique}}

{{DEFAULTSORT:Cavalier, Probleme du}}
[[Catégorie:Mathématiques récréatives]]
[[Catégorie:Théorie des graphes]]
[[Catégorie:Problème d'échecs]]
[[Catégorie:Leonhard Euler]]