Echange des cavaliers (1)
La principale difficulté ici est l'espace exigü sur lequel caracolent nos six cavaliers.
Pour faciliter la vision des choses, nous allons considérer tous les mouvements possibles d'un cavalier sur ce terrain.
Représentons ces mouvements sous la forme d'un graphe, deux cases étant reliées par un saut de cavalier.
Et ô miracle ce graphe est planaire !
Il suffit de réarranger un peu pour le redessiner sous la forme :
Considérons le jeu des noirs. Le plus court trajet est immédiatement visible sur ce graphe :
a4-c3-b1, b4-a2-c1, c4-a3-c2-a1, ou des variantes, soit 7 coups, et autant pour les blancs :
a1-c2-b4, b1-a3-c4, c1-a2-c3-a4.
Le nombre minimum de coup est ≥ 14
Et on voit aussi immédiatement où cela coince : les cases a2, a3, c2 et c3.
Si pour les cases d'arrivée on peut aisément s'arranger pour que la case soit libre quand le cavalier y arrive, il n'en est pas de même pour les cases intermédiaires :Une solution en 14 coups est impossible
La solution consiste alors à garer le cavalier qui se trouve par example en c3 après c1-a2-c3
et utilisation par les noirs de la case a2.
Le ramener en a2 pour laisser les noirs utiliser cette case c3, et enfin terminer son trajet par a2-c3-a4.
Et la solution minimum en 16 coups (le nombre de coups est forcément pair) :
c1-a2-c3, b4-a2-c1, c3-a2, a1-c2-b4, c4-a3-c2-a1, b1-a3-c4, a4-c3-b1, a2-c3-a4
ou des variantes par symétries ou interversions de coups.
L'un des deux camps fait forcément deux coups de suite (deux coups de plus pour les blancs que pour les noirs).
Si on veut alterner les coups des blancs et des noirs, il faut 18 coups, par exemple :
1. a1-c2, a4-b2
2. b1-c3, c4-a3
3. c1-a2, b2-c4
4. c3-a4, a3-b1
5. a2-c3, b4-a2
6. c2-b4, a2-c1
7. a4-b2, c4-a3
8. b2-c4, a3-c2
9. c3-a4, c2-a1
Noter l'utilisation de la case a4 comme case intermédiaire, et il n'y a aucun "aller-retour", chaque cavalier ne passe par ses cases qu'une seule fois ! (solution due à Jim Gillogly)
