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 GraphesIndex

 

 

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)

(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

*           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

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