Problème du tour du cavalier
Programme des réjouissances
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.
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).
Méthodes de recherche des solutions
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.
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.
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 |
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):
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 |
Trouver des invariants à partir de la liste des mouvements autorisés (plus difficile).
- Ce que l'on cherche
- L'algorithme
- Commentaires sur l'algorithme
- Terminaison de l'algorithme
- Justesse de l'algorithme
- Application
Ce que l'on cherche
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.
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)
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.
Terminaison de l'algorithme :
Justesse de l'algorithme:
-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.
Application
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.
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é)