jouer à raisonner, échec et cavalier

NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 28/03/2023 Orientation générale DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Jeux et problèmes
Débutants Général	ÉCHECS			Glossaire Général
INDEX Jeux Jeux avec lettres et nombres	Introduction & invention	Solutions	Cavalier	Dame / Reine
		Pavage	Tour	Fou
		Sommaire de cette page >>> Rappel du mouvement du cavalier >>> Petit périple du cavalier >>> Périple du cavalier sur l'échiquier >>> Contrôle du cavalier >>> Menace entre cavaliers >>> Liberté de mouvement >>> Inverser les blancs et les noirs

♞ É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

Devinette

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

RAPPEL DU MOUVEMENT DU CAVALIER

Deux pas dans une direction (horizontale ou verticale)
et un pas dans la direction perpendiculaire.

Ici, le cavalier en blanc menace les cases marquées en rouge.

Le cavalier contrôle des positions formant une sorte de cercle.

Le cavalier sur position noire, contrôle des positions blanches.

Menace du cavalier

Voir suite

PETIT PÉRIPLE DU CAVALIER
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.

PÉRIPLE DU CAVALIER sur l'échiquier

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

Carré semi-magique

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

n < 8	N'existe pas.
n = 8	Existe en semi-magique. Existence en magique non connue.
n, multiple de 4	C'est une obligation (démontré).
n = 12	Comme pour 8, non connu.
n = 16, 20, 24, 32, 40, 48	Existent.

Maîtrise de l'échiquier par le cavalier

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

MENACE ENTRE CAVALIERS
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

LIBERTÉ DE MOUVEMENT

É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)

Problème: INVERSER LES BLANCS ET LES NOIRS

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'exitant 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)

(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	Dame Jeux de déplacements Voir haut de page
Voir	Champions et machines Échiquier et lettres Graphes Intelligence artificielle Jeux et énigmes – Index Morpions Pentominos Roméo et Juliette Solitaire
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	http://villemin.gerard.free.fr/Puzzle/EchecCav.htm