Échange des cavaliers

Pour résoudre ce casse-tête vous devez échanger les positions des deux cavaliers rouges avec celles des deux noirs, en respectant évidemment les règles du déplacement du cavalier sur un échiquier et en n'utilisant que les dix cases dessinées.

Cliquez d'abord sur le cavalier à déplacer et ensuite sur la case libre où il doit aller.

Cavaliers

Une méthode simple permet de trouver rapidement la solution. Elle consiste à dessiner autrement le graphe dont les dix sommets représentent les cases de l'échiquier et dont les arêtes correspondent aux sauts des cavaliers.
La première figure fait correspondrent les cases aux nombres entiers de 1 à 10, les sommets du graphe non-orienté représenté sur la figure suivante.
Sur la figure de droite les sommets reliés par une arête sont placés près l'un de l'autre, la figure obtenue est bien plus simple à étudier.
   

Les déplacements d'une solution en 40 coups sont :

       Cavalier Rouge  1 -  4 - 10 -  2 -  8
       Cavalier Noir   7 -  1 -  4 - 10 -  2
       Cavalier Noir   5 -  7 -  1 -  4 - 10
       Cavalier Rouge  6 -  4 -  1 -  7 -  5 
       Cavalier Noir  10 -  4 -  1 -  7
       Cavalier Noir   2 - 10 -  4 -  1
       Cavalier Rouge  8 -  2 - 10 -  4 -  6
       Cavalier Noir   1 -  4 - 10 -  2
       Cavalier Noir   7 -  1 -  4 - 10
       Cavalier Rouge  6 -  4 -  1 -  7
       Cavalier Noir  10 -  4 -  1 
       Cavalier Noir   2 - 10 -  4 -  6

Cette solution n'utilise pas les deux cases 3 et 9 de l'échiquier.

Pour un échiquier de 6 cases de côté, les sommets sont les 64 cases de l'échiquier et plus généralement, pour un échiquier de n cases de côté, le nombre de sommets du graphe est n×n = n². En repérant les cases par leurs deux coordonnées i et j, le sommet (i, j) est relié par une arête aux huit sommets (i-1, j-2), (i+1, j-2), (i-2, j-1), (i+2, j-1), (i-1, j+2), (i+1, j+2), (i-2, j+1), (i+2, j+1), lorsque ceux-ci ne sont pas à l'extérieur de l'échiquier.
Chercher un parcours du cavalier qui passe une fois et une seule par toutes les cases de l'échiquier, correspond à la recherche d'un chemin hamiltonien sur le graphe : un chemin passant une fois et une seule par tous les sommets du graphe. (Si l'on peut revenir à la case de départ en une étape supplémentaire, il s'agit alors d'un cycle hamiltonien).

Pour un échiquier de 6 cases de côté le graphe est le suivant :



Si vous désirez chercher à la main un cycle, considérez le plus tôt possible les quatre coins : les sommets notés c0_0=(0, 0), c0_5=(0, 5), c5_0=(5, 0) et c5_5=(5, 5) sur l'image ci-dessus.

Les graphes des six échiquiers de 3 à 8 cases de côtés se trouvent dans le fichier grnn.pdf.

Des définitions et des explications complémentaires se trouvent dans le cours sur la théorie des graphes. Le parcours du cavalier y est traité à la page 10 et on y trouve aussi un programme cavalier.c de recherche de tous les chemins hamiltoniens possibles du cavalier, les solutions sont obtenues sous la forme :

      0 15  6 25 10 13            Compilation du programme C :
     33 24 11 14  5 26                  cc -o cavalier cavalier.c
     16  1 32  7 12  9            Utilisation du programme :
     31 34 23 20 27  4                  cavalier 6
     22 17  2 29  8 19            (le premier chemin obtenu est la solution ci-contre, à gauche)
     35 30 21 18  3 28

Dans la solution ci-dessus, les positions successives sont notées 0, 1, 2, ..., 35. (Vérifiez qu'il s'agit d'un chemin hamiltonien et non d'un cycle).

Voir la page de liens consacrée à Sir William Rowan Hamilton (Dublin 1805 -1865).
Hamilton découvrit aussi les quaternions, (corps non-commutatif dans lequel i² = j² = k² = ijk = -1). On trouvera des références à la page de liens et un exemple utilisant certains quaternions à la page Loi de composition interne ainsi d'ailleurs que bien d'autres exemples, tels les complexes et les octonions).
On doit aussi à Hamilton l'énoncé du théorème dit de Cayley-Hamilton et sa démonstration dans le cas d'un espace vectoriel de dimension 2. C'est Frobenius qui le démontre pour tous les espaces vectoriels de dimensions finies.
Théorème : étant donnés un espace vectoriel E de dimension finie sur C, u un endomorphisme de E (application linéaire de E dans E) et P le polynôme caractéristique de u. Alors P(u) = 0.
Lorsque l'endomorphisme u est connu par sa matrice M, on a P(M)=0 (matrice nulle), voir la page Calcul matriciel du site pour des exemples

• 1) cliquer sur le 1er bouton [Matrice au hasard] pour obtenir aléatoirement une matrice carrée réelle puis
• 2) cliquer sur [Polynôme caract. P] pour obtenir le polynôme caractéristique P que l'on peut lire dans la fenêtre d'affichage de l'application, sous la matrice, enfin
• 3) cliquer sur le dernier bouton [Cayley-Hamilton] de l'application pour obtenir P(M) qui est bien la matrice nulle.