|
♞ ÉCHECS & CAVALIER ♞ Problème du cavalier, algorithme du cavalier, cavalier
d'Euler Un problème très répandu consiste
à faire parcourir tout l'échiquier au cheval en passant par toutes les cases
et une seule fois. Il est intéressant de commencer par un échiquier réduit et
de rechercher les cas possibles ou impossibles. Deux
illustres maîtres concernant ce sujet: Martin Gardner, célèbre pour tous ses
développements sur les jeux mathématiques, et Solomon W. Golomb célèbre pour
ses recherches sur les polyominos et autres pentominos. |
Anglais: The move of a
chess knight, knight's tour
En
1512, Guarini invente ce petit problème de déplacement des cavaliers sur
mini-échiquier 3x3. Comment inverser les blancs et les noirs en un minimum de
coups? Attention, pas si simple! Anglais: Guarini's knight-switching problem. |
Voir suite
|
||
Le cavalier effectue un voyage lui faisant visiter
chacune des cases une seule fois. |
||
Échiquier 2 x 2 |
Le
cavalier ne peut pas se déployer. Impossible. |
|
Échiquier 3 x 3 |
Le
cavalier ne peut pas atteindre la case du milieu. Impossible. Voir liberté de mouvement |
|
Échiquier 4 x 4 |
Impossible. Voir liberté de mouvement |
|
Échiquier 5 x 5 |
Possible En
rouge, le début du parcours. Mais
impossible de revenir au point de départ à la fin du périple: parcours non
fermé. |
|
Échiquier 3 x 4 |
Rectangle
le plus petit permettant le périple du cavalier. Mais non-fermé. |
|
Bilan |
|
En rouge, les plus petites surfaces possibles. |
|
|||||||||||
Il s'agit de parcourir toutes les cases de l'échiquier
en faisant progresser le cavalier selon son déplacement classique.
On ne connaît pas le nombre de solutions: c'est
plusieurs millions. En voici deux qui présentent
des symétries: Euler
en 1759 Chaque couple de nombres symétriques par rapport au
centre présente une différence de 32. Voir Graphes
– Index La figure suivante a été éditée en 1848.
La somme sur les lignes et les colonnes donnent 260,
mais malheureusement les diagonales ne donnent pas cette somme. Le carré est
semi-magique et non pas magique.
Les quatre carrés séparés par les traits bleus épais sont également semi-magiques avec 130 pour
somme. En coupant encore en carrés de 4 cellules, la somme des 4 nombres est
aussi 130 (comme: 1 + 30 +48 + 51). Bilan:
sur un échiquier de n côtés
|
|
||
Sur un échiquier 5
x 5, le cavalier (blanc) contrôle huit positions (rouges). Ce sont des
positions appartenant à la deuxième couronne autour du cavalier. |
|
|
Sur un échiquier 9
x 9 (non conventionnel, donc), le cavalier contrôle huit positions (rouges)
au premier coup et 32 au second coup. 11 indique que cette case est atteinte par le cavalier en position 1; 12 indique que cette case est atteinte par le cavalier en position 1
ou 2.
Il faut quatre coups pour que le cavalier en position
centrale atteigne toutes les cases de l'échiquier 9 x 9.
44 veut dire que cette case est atteinte deux fois au
quatrième coup de jeu du cavalier.
333 veut dire que cette
case est atteinte trois fois au troisième coup. |
Cases atteintes au deuxième coup du cavalier: objet d'une jolie
figure. |
Cas du vrai échiquier 8x 8 |
|
||
Question Combien peut-on poser de cavaliers au maximum sur
l'échiquier sans que l'un menace les autres? Réponses |
||
Solution classique avec 24 cavaliers |
Solution, optimale avec 32 cavaliers En effet un cavalier sur une couleur ne menace
jamais sa propre couleur |
|
|
|
Échiquier 3 x 3: Parcours possible du cavalier sur un plateau de 3 x 3 Le graphe montre que, hors la case centrale, le
cavalier maîtrise toujours deux positions et qu'il peut parcourir toutes les
cases de la couronne. Le schéma équivalent établi sous forme d'un graphe
permet de résoudre plus facilement certains problèmes. Échiquier 4 x 4: Le nombre en rouge dans le tableau indique la quantité
de déplacements du cavalier depuis cette case. Avec ce graphe, on peut imaginer les mouvements du
cavalier dans le cas où on supprime des cases:
Sans les cases d'angle: on supprime les 4 cellules du
centre du graphe; on continue à pouvoir faire le tour en périphérie et au
centre.
Sans, en plus, celles du centre, on continue à pouvoir
faire le tour; ou plutôt deux tours différents selon la position de départ.
C'était les cases centrales qui permettaient de commuter d'un tour sur
l'autre. Avec ce genre de graphe, on peut facilement imaginer
des casse-tête. On peut notamment montrer que le périple du cavalier est impossible (passer partout, une
seule fois) |
|
|
Voici un casse-tête classique, difficile à résoudre
sans l'aide du schéma équivalent.
Avec cette partie de l'échiquier seulement, inverser
les cavaliers bleus et les cavaliers verts.
Mise à plat du graphe et résolution |
Voir Jeux et énigmes
Résolution avec le
graphe équivalent, puis le graphe simplifié Le graphe représente
les possibilités de mouvements de chacun des cavaliers. La solution est
évidente à partir du graphe simplifié. Il suffit de faire tourner d'un cran
l'ensemble des cavaliers de quatre pas. Une rotation d'un cran nécessite
quatre mouvements (Ex: 1-2, 3-4, 5-6 et 7-8). La solution minimale exige
seize mouvements. |
Bonus:
même problème, inverser les noirs et les blancs en un minimum de mouvements. Graphe
équivalent Solution:
mettre les deux blancs en voie de garage en 5 et 9: 5 mouvements. Amener les Blancs en
position finale: 6 mouvements. Amener les noirs en
position finale: 5 mouvements Total: 16 mouvements.
Les cases (2, 3, 6, 8, 11 et 12) ne sont pas utilisées. (b) 13 -- 7 -- 1
(cavalier blanc rangé sans être passé par le garage) (c) 5 -- 7 -- 13
(cavalier noir garé maintenant rangé) (d) 4 -- 6 -- 12
(l'autre cavalier noir débute sa route) (e) 10 -- 8 -- 2
(l'autre cavalier blanc aussi) (f) 12 -- 3 -- 10
(l'autre noir la finit) (g) 2 -- 11 -- 4 (et
l'autre blanc aussi). On gagne ainsi deux
mouvements parce que dans cette solution, le cavalier blanc ne passe pas
forcément par une voie de garage. |
Merci à Denis Vekemans pour cette solution plus
optimisée et sans doute minimale
Suite |
|
Voir |
Jeux et énigmes – Index
|
Site |
Problème du
cavalier – Wikipédia
Le problème du
cavalier – JP Zanotti – 2018
Knight's Tour Challenge – Jouer au parcours du cavalier sur un
échiquier
The
Knight’s tour problem | Backtracking-1 – Geeksfor Geeks – Programmation Python, C++, Java |
Cette page |