Problème du tour du cavalier

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)

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).

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

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).

Trajet 6x6 symétrique

(retour au sommaire)

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

Fusion de deux trajets

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)

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.

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, sur un échiquier 6x6.

(retour au sommaire)

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 :

M M
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 :
M M M
M M M

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 :

M M M M

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é :

M M M
M M M

(retour au sommaire)

Trouver des invariants à partir de la liste des mouvements autorisés (plus difficile).

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) (retour au sommaire)

L'algorithme

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<F(a1) alors                          (r4)
        v1 = w                                  (r5)
      sinon
        v2 = w                                  (r6)
      fin si
    fin Si
  fin Pour                                      (r7)
Jusqu'à ce que  N=0                             (r8)

(plan de la section) (retour au sommaire)

Commentaires sur l'algorithme (utiles pour le démontrer):

Posons D=|det(v1,v2)|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 0<F(a1)<1, la valeur de D diminue strictement après la substitution.
D'autre part, si D était non-nul avant la substitution, il le sera aussi après (car F(a1)>0).
(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<F(a2)<1).
(r7) La remarque (r2) montre que, à la fin de cette boucle, N=0 si tous les vecteurs e(i) (i=1..n-1) sont générés par v1 et v2, N=1 sinon.
(r8) l'algorithme prend fin lorsque il n'y a pas eu de substitution (v1 et v2 n'ont pas changé et N=0)

(plan de la section) (retour au sommaire)

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) (retour au sommaire)

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) (retour au sommaire)

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, l'algorithme donne bien D=4.

(plan de la section) (retour au 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)

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

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.

(retour au sommaire)