Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 05/04/2024

M'écrire

Brèves de Maths

 

INDEX

 

Jeux

Jeux avec lettres et nombres

Défis mathématiques

Échecs – Cavalier

Échecs – Introduction

Cavalier – Général

Cavalier – Distances

Cavalier – Maîtrise

Cavalier – Menace

Cavalier – Mouvements

Cavalier – Périple

Périple – Magique

Périple – Exemples

Périple – Historique, Théorie et programmation

 

Faites un double-clic pour un retour en haut de page

 

 

Cavalier – Mouvements

 

Problème classique: inverser la position des blancs et des noirs en un minimum de mouvements.
Les graphes sont appelés à le rescousse.

   

 

Sommaire de cette page

>>> Rappel du mouvement du cavalier

>>> Liberté de mouvement

>>> Inverser les blancs et les noirs

 

Débutants

Nombres

 

Glossaire

Nombres

 Anglais: The move of a chess knight, knight's tour

  

 

Devinettes

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.

Solution

 

 

MOUVEMENT DU CAVALIER

haut

 

Cavalier

Le cavalier (ou cheval) est une des pièces du jeu d'échec, représenté par une tête de cheval.

Il y en a deux blancs et deux noirs sur un échiquier.

 

Mouvement en L du cavalier

Deux pas dans une direction (horizontale ou verticale)
et un pas
dans une des directions perpendiculaires.

 

Autre vision: le cavalier avance d'une case puisse saute en oblique sur une case voisine.

 

 

Exemple de mouvement du cavalier

Notez qu'à chaque mouvement du cavalier, la couleur de la case change.

   

 

 

Les 24 (= 4!) trajets possibles du cavalier pour rejoindre la position six cases plus bas

C'est la représentation de l'hypercube

Voir Brève 58-1156

 

 

LIBERTÉ DE MOUVEMENT

haut

 

Échiquier 3 x 3

Parcours possible du cavalier sur un plateau de 3 x 3.

 

 

Le graphe traduit que depuis la position A1, le cavalier ne peu aller qu'en positions C2 ou B3. Etc.

 

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.

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

 

 

 

 

INVERSER les blancs et les noirs

haut

 

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.
Le graphe équivalent est celui établi ci-dessus en éliminant les cases n'existant plus
.

 

 

Mise à plat du graphe et résolution
 

Voir Jeux et énigmes

 

 

Devinette – Solution

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.
Solution de Denis en 14 mouvements:
(a) 1 -- 7 -- 5 (cavalier noir au garage)

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

 

Retour

Merci à Denis Vekemans pour cette solution plus optimisée et sans doute minimale

 

 

 

Suite

*      Cavalier – Distance

*      Dame

*      Jeux de déplacements

*      Voir haut de page

Voir

*      Champions et machines

*      Échiquier et lettres

*      Graphes

*      Intelligence artificielle

*      Jeux et énigmesIndex

*      Morpions

*      Pentominos

*      Roméo et Juliette

*      Solitaire

Sites

*      Problème du cavalier – Wikipédia

*      Le problème du cavalier – JP Zanotti – 2018

*      Knight's tour – Wikipedia

*      Knight's Tour Notes Compiled by George Jelliss © 2000 – 2023

*      There Are No Magic Knight's Tours on the Chessboard

*      By Eric W. Weisstein

*      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

*      OEIS A001230 – Number of undirected closed knight's tours on a 2n X 2n chessboard

Cette page

http://villemin.gerard.free.fr/Puzzle/EchecCa5.htm