.. title: Problème du tour du cavalier
.. raw:: html
.. _sommaire:
Programme des réjouissances
---------------------------
- `Introduction et énoncé du problème <#introduction>`__
- `Exemples de solutions <#Exemples_solutions>`__
- `Méthodes de recherche <#Methodes_recherche>`__
- `Montrer l'absence de solution par les invariants. <#aucune_solution>`__
- `Nouveaux invariants et variantes du problème <#variantes>`__
- `Le dernier invariant en date <#decouverte>`__
- `Recherche d'invariants à partir des mouvements autorisés <#euclide>`__
- `Liens <#liens>`__
.. _introduction:
Introduction et énoncé du problème
----------------------------------
Dans la longue série des problèmes
"qui-ne-servent-qu'à-se-presssurer-le-cerveau", celui-ci occupe une
place de choix : faire passer un cavalier d'échecs une fois et une seule
par chacune des cases de l'échiquier, pour revenir au point de départ,
en respectant bien sûr les règles du jeu.
Ce problème admet des solutions (nombreuses) dans le cas d'un échiquier
8x8. De plus, on peut très bien ne pas se limiter aux seuls mouvements
qu'autorisent les règles des échecs.
Il existe de nombreuses méthodes de recherche de telles solutions. Cette
page donne quelques méthodes de recherche manuelles, ainsi que deux
programmes informatiques. Le premier procède à une recherche exhaustive
de toutes les solutions; le second recherche uniquement les solutions
symétriques.
Ceci dit, il est inutile de rechercher des solutions si l'on peut
montrer qu'il n'en existe pas. En général, de telles démonstrations
utilisent la notion d'invariant.
`(retour au sommaire) <#sommaire>`__
.. _Exemples_solutions:
Exemples de solutions
---------------------
La première solution concerne les déplacements classiques du cavalier
sur un échiquier 8x8. Elle comporte une symétrie centrale.
+----+----+----+----+----+----+----+----+
| 0 | 25 | 18 | 13 | 20 | 23 | 38 | 41 |
+----+----+----+----+----+----+----+----+
| 17 | 12 | 63 | 24 | 37 | 40 | 35 | 22 |
+----+----+----+----+----+----+----+----+
| 26 | 1 | 14 | 19 | 28 | 21 | 42 | 39 |
+----+----+----+----+----+----+----+----+
| 11 | 16 | 27 | 62 | 47 | 36 | 29 | 34 |
+----+----+----+----+----+----+----+----+
| 2 | 61 | 4 | 15 | 30 | 59 | 48 | 43 |
+----+----+----+----+----+----+----+----+
| 7 | 10 | 53 | 60 | 51 | 46 | 33 | 58 |
+----+----+----+----+----+----+----+----+
| 54 | 3 | 8 | 5 | 56 | 31 | 44 | 49 |
+----+----+----+----+----+----+----+----+
| 9 | 6 | 55 | 52 | 45 | 50 | 57 | 32 |
+----+----+----+----+----+----+----+----+
Pour la seconde solution, on a modifié la liste des déplacements
autorisés : le cavalier peut ou bien sauter une case en diagonale, ou
bien en sauter deux, verticalement ou horizontalement. La solution
ci-dessous comporte trois symétries : par rapport aux deux axes
(horizontal et vertical) du carré, et par rapport au centre du carré (ce
qui découle d'ailleurs des deux premières symétries).
.. raw:: html
+----+----+----+----+----+----+----+----+----+----+
| 56 | 69 | 62 | 55 | 68 | 81 | 94 | 87 | 80 | 93 |
+----+----+----+----+----+----+----+----+----+----+
| 72 | 59 | 51 | 71 | 60 | 89 | 78 | 98 | 90 | 77 |
+----+----+----+----+----+----+----+----+----+----+
| 63 | 54 | 67 | 64 | 53 | 96 | 85 | 82 | 95 | 86 |
+----+----+----+----+----+----+----+----+----+----+
| 57 | 70 | 61 | 58 | 50 | 99 | 91 | 88 | 79 | 92 |
+----+----+----+----+----+----+----+----+----+----+
| 73 | 65 | 52 | 74 | 66 | 83 | 75 | 97 | 84 | 76 |
+----+----+----+----+----+----+----+----+----+----+
| 26 | 34 | 47 | 25 | 33 | 16 | 24 | 2 | 15 | 23 |
+----+----+----+----+----+----+----+----+----+----+
| 42 | 29 | 38 | 41 | 49 | 0 | 8 | 11 | 20 | 7 |
+----+----+----+----+----+----+----+----+----+----+
| 36 | 45 | 32 | 35 | 46 | 3 | 14 | 17 | 4 | 13 |
+----+----+----+----+----+----+----+----+----+----+
| 27 | 40 | 48 | 28 | 39 | 10 | 21 | 1 | 9 | 22 |
+----+----+----+----+----+----+----+----+----+----+
| 43 | 30 | 37 | 44 | 31 | 18 | 5 | 12 | 19 | 6 |
+----+----+----+----+----+----+----+----+----+----+
.. raw:: html
Une solution graphique, c'est peut-être plus gai. Celle qui suit
présente une symétrie d'ordre 4 elle est invariante si on la tourne d'un
quart de tour. Elle est présentée pour un échiquier 6x6, et on verra
plus loin qu'il n'existe pas de telle solution (avec une symétrie
d'ordre 4) sur un échiquier 8x8 (si on se contente des mouvements permis
par les règles des échecs).
.. _s4e6x6:
.. raw:: html
|Trajet 6x6 symétrique|
.. raw:: html
`(retour au sommaire) <#sommaire>`__
.. _Methodes_recherche:
Méthodes de recherche des solutions
-----------------------------------
| Comment rechercher de telles solutions (Pour l'instant, on suppose
qu'il en existe)?
| La méthode la plus simple consiste à construire pas à pas une telle
solution.
| On peut aussi chercher des solutions symétriques , en effectuant, pour
chaque mouvement, le (ou les) mouvement(s) symétrique(s) et en
essayant de les raccorder à la fin.
| Une autre méthode consiste à couvrir tout l'échiquier, par plusieurs
trajets fermés, puis à relier ces trajets entre eux, de façon à ce
qu'il ne reste plus qu'une grande boucle qui couvre l'échiquier.
L'image suivante montre comment fusionner deux trajets
.. raw:: html
|Fusion de deux trajets|
.. raw:: html
Le premier programme informatique (`cliquezici pour avoir sa source en
C `__) proposé construit une solution cyclique pas à
pas (récursivement), en partant d'un coin de l'échiquier. Afin
d'accélérer sa recherche, il actualise, à chaque itération, un tableau
qui indique de combien de cases, n'appartenant pas encore au trajet en
construction, on peut accéder à une case donnée. Cela permet de détecter
assez tôt des impasses et des coups forcés (il est possible, bien que
fastidieux, d'utiliser ce procédé pour une recherche manuelle).
Le second (`cliquez ici pour avoir le fichier source en
C `__) recherche les trajets invariants
(pour la forme comme pour le sens du parcours) par une symétrie
centrale. Pour chaque coup, il construit aussi son symétrique. Pour s'y
retrouver, il maintient un tableau qui indique, pour chaque case, à
quelle section elle appartient (le trajet en cours de construction, son
symétrique, ou aucun des deux). La recherche est accélérée par le même
procédé que pour le premier programme.
`(retour au sommaire) <#sommaire>`__
.. _aucune_solution:
Montrer l'absence de solution par les invariants.
-------------------------------------------------
Il est inutile, bien entendu, de rechercher des solutions s'il n'en
existe pas. Pour prouver l'absence de solutions, on utilise souvent la
notion d'invariant. Un invariant est simplement une propriété qui ne
dépend pas du trajet considéré.
Par exemple, si les cases de l'échiquier forment un damier noir et
blanc, on remarque que la couleur de la case sur laquelle le cavalier se
trouve, après le coup numéro n, ne dépend que de la parité de n (du
moins si l'on se limite aux mouvements autorisés aux échecs), car la
couleur de la case change à chaque coup joué. Donc, s'il existe une
solution cyclique pour l'échiquier 5*5, alors la couleur de la case
atteinte au 25ème coup est différente de celle de la case de départ. Or
la solution est cyclique, donc cette case est celle de départ et a donc
la même couleur. C'est une contradiction flagrante. Cette démonstration
est aussi valable pour tout échiquier de côté impair.
.. raw:: html
M | M | M | M | M |
M | M | M | M | M |
M | M | M | M | M |
M | M | M | M | M |
M | M | M | M | M |
Remarque : il existe néanmoins des parcours non-cycliques, comme celui
donné ici
+----+----+----+----+----+
| 1 | 24 | 13 | 18 | 7 |
+----+----+----+----+----+
| 14 | 19 | 8 | 23 | 12 |
+----+----+----+----+----+
| 9 | 2 | 25 | 6 | 17 |
+----+----+----+----+----+
| 20 | 15 | 4 | 11 | 22 |
+----+----+----+----+----+
| 3 | 10 | 21 | 16 | 5 |
+----+----+----+----+----+
On peut aussi utiliser les invariants pour montrer qu'il n'existe pas de
solution répondant à des critères donnés.
Supposons par exemple qu'il existe, sur un échiquier 8x8, un parcours
cyclique présentant une symétrie d'ordre 4 (et respectant les mouvements
classiques du cavalier). Appelons a,b,c,d les 4 coins du carrés (a étant
opposé à c, et b à d). Supposons qu'il existe un tel parcours S, et
considérons la portion T de S qui va de a à b. Comme S présente un
symétrie d'ordre 4, il suffit de faire subir à T des quarts de tour
successifs par rapport au centre de carré, pour obtenir les portions
T',T'' et T''' de S qui relient respectivement b à c, c à d et d à a. S
est donc constitué de T, T', T'' et T''' mises bout à bout. Par
symétrie, ces portions sont de même longueur, donc la longueur de T est
8²/4 = 16. Comme T relie a à b et comme 16 est pair, les coins a et b
devraient avoir la même couleur, ce qui est absurde.
Cette démonstration (que l'on peut rendre beaucoup plus rigoureuse),
s'applique à toutes les tailles d'échiquier multiples de 4. Par contre,
elle ne s'applique pas aux tailles d'échiquier congrues à 2 modulo 4
(comme 6 par exemple). D'ailleurs, on a vu plus haut un exemple de
`solution symétrique d'ordre 4 <#s4e6x6>`__, sur un échiquier 6x6.
`(retour au sommaire) <#sommaire>`__
.. _variantes:
Nouveaux invariants, variantes du problème.
-------------------------------------------
Colorer l'échiquier en noir et blanc revient à recouvrir le plan d'un
même motif (ici un domino 2x1) qui se répète par translation :
.. raw:: html
| Remarque : ici, il n'est d'aucune importance que le domino dépasse ou
non de l'échiquier.
| L'intérêt de l'invariant est que, à partir d'une case du motif de
couleur donnée, les mouvements autorisés ne permettent d'accéder qu'à
des cases de même couleur (ainsi, à partir d'une case blanche, on
n'accède qu'à des cases noires, et vice-versa). On pourrait recouvrir
l'échiquier avec un motif différent, avec plus de cases et plus de
couleurs, comme le motif en L ci-dessous :
.. raw:: html
.. _pavage_L:
On peut alors choisir, par exemple, de n'autoriser que des mouvements
qui , d'une case jaune, ne donnent accès qu'à une case grise, comme dans
le dessin suivant (la case de départ contient un cercle, les cases
d'arrivée contiennent une croix):
\ |Autre pavage|
Comme le pavage se répète par translation, on en déduit que le cavalier
passera aussi d'une case grise à une bleue, d'une bleue à une blanche,
d'une blanche à une jaune. Finalement, la couleur de la n-ième case
traversée ne dépendra que de la couleur de la case de départ et du reste
de n dans la division par 4 (taille du motif).
On peut évidemment choisir d'autres motifs, plus ou moins grands, du
moment qu'ils peuvent paver le plan par translation. Il est inutile de
choisir un motif trop compliqué, car, pour un pavage donné, toutes les
translations qui permettent de paver l'échiquier sont obtenues en
combinant deux d'entre elles, bien choisies. Ainsi, dans l'image
ci-dessus, les translations de vecteurs respectifs (4,0) et (1,-1)
conviennent. On en déduit (à partir du parallélogramme engendré par les
deux translations) un motif qui convient aussi :
.. raw:: html
Les couples de translations qui conviennent ne sont pas uniques, ainsi,
on aurait aussi pu choisir les translations (2,2) et (1,-1), ce qui
aurait donné :
.. raw:: html
`(retour au sommaire) <#sommaire>`__
.. _euclide:
Trouver des invariants à partir de la liste des mouvements autorisés (plus difficile).
--------------------------------------------------------------------------------------
- `Ce que l'on cherche <#recherche>`__
- `L'algorithme <#algorithme>`__
- `Commentaires sur l'algorithme <#comment_algo>`__
- `Terminaison de l'algorithme <#terminaison>`__
- `Justesse de l'algorithme <#justesse>`__
- `Application <#application>`__
.. _recherche:
Ce que l'on cherche
~~~~~~~~~~~~~~~~~~~
| On a vu, dans la section précédente, que deux translations bien
choisies engendraient toutes celles qui permettaient à un motif donné
de paver le plan.
| En appelant d(0) ... d(n-1) les n vecteurs (à coordonnées entières)
qui représentent les mouvements autorisés, et en appelant e(1) ...
e(n-1) les vecteurs définis par e(i) = d(i)-d(0), il suffit donc de
trouver deux vecteurs v1 et v2 qui engendrent e(1) .. e(n-1) par
combinaisons linéaires à coefficients entiers.
Pour les trouver, on peut utiliser l'algorithme suivant (donné en
français). L'idée consiste à choisir (presque) arbitrairement, au
départ, les vecteurs v1 et v2, puis à les adapter petit à petit pour
qu'ils génèrent tous les vecteurs e(i) (i=1..n-1). La démarche utilisée
est proche de celle de l'algorithme d'Euclide, qui sert à trouver le
plus grand diviseur commun de deux entiers.
`(plan de la section) <#euclide>`__ `(retour au sommaire) <#sommaire>`__
.. _algorithme:
L'algorithme
~~~~~~~~~~~~
.. code:: text
Parmi les e(i) (i=1..n-1), trouver deux vecteurs libres (i.e non-colinéaires).
Soient v1 et v2 ces deux vecteurs. (r0)
Faire
N = 0
Pour i=1..n-1
trouver a1 et a2 tels que e(i)=a1.v1+a2.v2 (r1)
Si a1 ou a2 n'est pas entier alors (r2)
N = 1
w = F(a1).v1+F(a2).v2 (r3)
Si 0`__ `(retour au sommaire) <#sommaire>`__
.. _comment_algo:
Commentaires sur l'algorithme (utiles pour le démontrer):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Posons ``D=|det(v1,v2)|`` où ``det`` désigne le déterminant et ``| |``
désigne la valeur absolue.
(r0) ``v1`` et ``v2`` sont à coordonnées entières puisque les
``e(i) (i=1..n-1)`` le sont.
| De plus, ils sont libres donc ``D>0``. D'autre part, puisque ils sont
pris parmi les ``e(i)``, ils sont évidemment combinaisons linéaires à
coefficients entiers des ``e(i) (i=1..n-1).``
| (r1) ``a1`` et ``a2`` existent puisque ``v1`` et ``v2`` sont libres.
On peut trouver ``a1`` et ``a2`` à l'aide des formules de Cramer :
| ``a1 = det(e(i),v2)/det(v1,v2)`` et ``a2 = det(v1,e(i))/det(v1,v2)``
| (r2) on regarde si ``e(i)`` n'est pas combinaison linéaire à
coefficients entiers de ``v1`` et ``v2``, on le signale en mettant, le
cas échéant, la valeur de ``N`` à 1.
| (r3) ``F`` désigne la partie fractionnaire (en particulier,
``F(a1)<1`` et ``F(a2)<1)``. On montre facilement que, si ``v1`` et
``v2`` sont à coordonnées entières, alors ``w`` est un vecteur à
coordonnées entières. En effet, en notant ``E`` la fonction partie
entière, on a
``w = (a1-E(a1)).v1+(a2-E(a2)).v2 = (a1.v1 + a2.v2) - (E(a1).v1+E(a2).v2) = e(i)-E(a1).v1-E(a2).v2``.
| Ceci prouve même que, si ``v1`` et ``v2`` sont combinaisons linéaires
à coefficients entiers des ``e(i) (i=1 .. n)``, alors ``w`` l'est
aussi.
| (r4) Comme ``a1`` ou ``a2`` n'est pas entier, on a ``F(a1)>0`` ou
``F(a2)>0``
| (r5)
``|det(w,v2)| = |det(F(a1).v1+F(a2).v2,v2)| = |det(F(a1).v1,v2)|= F(a1).|det(v1.v2)| = F(a1).D``
| donc, comme ``00``).
| (r6) de même, ``|det(v1,w)|=F(a2).D`` donc, là encore, la valeur de
``D`` diminue strictement après la substitution et, si ``D`` était
non-nul avant la substitution, il reste non nul après (car
``0`__ `(retour au sommaire) <#sommaire>`__
.. _terminaison:
Terminaison de l'algorithme :
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| -Les remarques (r0) et (r3) montrent que, tout au long de l'exécution,
les vecteurs ``v1`` et ``v2`` restent à coordonnées entières.
| -Les remarques (r0), (r4), (r5) et (r6) montrent que, à chaque
substitution, ``D`` décroît strictement.
| -Or, par définition, ``D=|det(v1,v2)|``. En particulier ``D`` reste >0
tout au long de l'algorithme. Comme ``v1`` et ``v2`` sont toujours
entiers, ``D`` reste entier tout au long de l'algorithme. Or ``D``
décroît à chaque substitution. Donc le nombre total de substitutions
est fini.
| -Il arrive donc un moment où aucune substitution n'a lieu lors de
l'exécution de la boucle ``Pour``. Donc ``N=0`` à la sortie de cette
boucle et l'algorithme s'arrête.
`(plan de la section) <#euclide>`__ `(retour au sommaire) <#sommaire>`__
.. _justesse:
Justesse de l'algorithme:
~~~~~~~~~~~~~~~~~~~~~~~~~
| -A la fin de l'algorithme ``N=0``, donc la remarque (r7) montre que, à
la fin de l'algorithme, tous les vecteurs ``e(i) (i=1..n-1)`` sont
générés par les vecteurs ``v1`` et ``v2``.
| -Les remarques (r0) et (r3) montrent que, tout au long de
l'algorithme, et en particulier à la fin, ``v1`` et ``v2`` sont
combinaisons linéaires à coefficients entiers des ``e(i) (i=1..n)``.
| Soient ``w1`` et ``w2`` deux vecteurs qui, comme ``v1`` et ``v2``,
engendrent les ``e(i) (i=1..n-1)``. ``v1`` et ``v2`` étant
combinaisons linéaires des ``e(i)``, ils sont aussi combinaisons
linéaires de ``w1`` et ``w2``. Donc il existe des entiers
``a1``,\ ``b1``,\ ``a2``,\ ``b2`` tels que ``v1=a1.w1+b1.w2`` et
``v2=a2.w1+b2.w2``.
| Alors
``det(v1,v2)=det(a1.w1+b1.w2, a2.w1+b2.w2) = a1.b2.det(w1,w2)+a2.b1.det(w2,w1)=(a1.b2-a2.b1).det(w1,w2)``.
| Donc ``D`` est multiple du déterminant de n'importe quel couple de
vecteurs qui engendre les ``e(i) (i=1..n-1)``, donc ``D`` est maximal.
| -Si l'on se rappelle que la valeur absolue du déterminant de 2
vecteurs est l'aire du parallélogramme qu'ils engendrent, on se rend
compte que ``D``, qui vaut ``|det(v1,v2)|``, est l'aire du plus grand
motif possible.
-Remarque : ``D`` est indépendant de l'ordre des vecteurs ``e(i)`` au
départ. Ce n'est pas comme ``v1`` et ``v2`` qui, eux, dépendent de cet
ordre.
`(plan de la section) <#euclide>`__ `(retour au sommaire) <#sommaire>`__
.. _application:
Application
~~~~~~~~~~~
| Pour les mouvements classiques du cavalier, on a n=8 et
| ``{d0...d7}={(1,2)(2,1)(2,-1),(1,-2)(-1,-2)(-2,-1)(-2,1)(-1,2)}``
| donc
| ``{e(1)...e(7)}={(1,-1)(1,-3)(0,-4)(-2,-4)(-3,-3)(-3,-1)(-2,0)}``
| L'algorithme donne alors D=2 et (selon l'ordre des vecteurs au
départ):
| v1=(1,-1) et v2=(1,1). Donc l'aire du motif qui se répète est 2 : ceci
montre que, avec les mouvements classiques des échecs, on n'a pas
d'invariant plus grand que le motif noir et blanc de taille 2x1.
De même, pour le pavage de taille 4 donné en exemple `plus
haut <#pavage_L>`__, l'algorithme donne bien D=4.
`(plan de la section) <#euclide>`__ `(retour au sommaire) <#sommaire>`__
-Un autre aspect du problème consiste à numéroter les cases, selon
l'ordre dans lequel la pièce y passe, afin d'obtenir un carré magique.
Euler avait trouvé un tel circuit (qui n'est en fait que semi-magique),
mais, de nos jours, on peut encore utiliser un programme informatique
(et encore des invariants), pour rendre moins longue la recherche de
solutions. Vous pouvez regarder un tel carré (et beaucoup d'autres) sur
http://villemin.gerard.free.fr/Puzzle/EchecCav.htm#magique.
`(retour au sommaire) <#sommaire>`__
.. _decouverte:
Un invariant (beaucoup) plus avancé
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
En considérant le problème comme un graphe dont les sommets sont les
cases de l'échiquier, et dont les arètes sont données par les mouvements
autorisés, on se ramène à la recherche d'un cycle hamiltonien.
En regardant (pour les déplacements classiques du cavalier) ce graphe
comme la projection, sur un plan, d'un certain graphe en dimension 4, un
chercheur a trouvé un invariant topologique qui permet de classer les
différents circuits (à partir de l'indice d'une classe d'homotopie, pour
ceux qui comprennent ce que ça veut dire).
En particulier, on arrive à rassembler les tours équivalents (notamment
par rotation)
Source : La Recherche, numéro 362 (Mars 2003), page 24
(le lien internet vers l’article original du chercheur a expiré)
.. _liens:
Liens
-----
| http://villemin.gerard.free.fr/Puzzle/EchecCav.htm#magique : de
nombreux détails et exemples, dans un site perso qui traite de
beaucoup d'autres jeux mathématiques.
| `Liens de ce site <../pointeurs.html>`__
`(retour au sommaire) <#sommaire>`__
.. |Trajet 6x6 symétrique| image:: Quad6x6.GIF
.. |Fusion de deux trajets| image:: fusion_trajets.GIF
:class: centre
.. |Autre pavage| image:: pavage_L.GIF
:width: 100px
:height: 100px