La ronde des cavaliers

Les jeux sont souvent la source de problèmes mathématiques intrigants. Prenez par exemple un plateau de jeu d’échec standard, de taille 8 x 8, et une pièce nommée « cavalier« .

Aux échecs, le cavalier se déplace selon un motif en L : deux cases horizontales puis une verticale, ou deux cases verticales puis une horizontale, indépendamment des pièces qui pourraient se trouver sur son chemin. Ce comportement peu ordinaire a donné lieu à de nombreuses énigmes, dont celle du parcours du cavalier.

Déplacement du cavalier

Déplacement du cavalier. Le cavalier noir peut se déplacer sur les cases marquées d’un point noir. Source de l’image : pousseurdebois.fr

Partant d’une case au hasard de notre échiquier classique, est-il possible de passer une et une seule fois sur toutes les cases du plateau ? Mieux encore, est-il possible de fermer ce parcours, de manière à ce que la première case de ce chemin soit accessible en un mouvement depuis la dernière ?

Une fois la réponse à cette question donnée, l’esprit curieux ne s’arrêtera pas là. S’il existe un parcours fermé, peut-être tentera-t-il de tous les déterminer. S’il n’en existe pas, encore doit-il être capable de le démontrer. Et si cet échiquier classique ne le satisfait pas totalement, alors il recommencera l’expérience sur des plateaux de tailles variées, pas forcément carrés.

Intéressons-nous plutôt à cette dernière question.

Tourne, tourne

Revenons d’abord à notre problème classique : oui, il est possible d’établir un parcours fermé sur un échiquier de 64 cases, et en voici une des possibilités.

Parcours fermé

Un parcours fermé du cavalier.

Le parcours présenté ici et trouvé par Euler, divise le plateau de jeu en deux sous-plateaux, reproduisant un chemin similaire en haut et en bas. Évidemment, puisque ce parcours est fermé, il est possible de partir de n’importe quelle case et de suivre les flèches pour aboutir à un nouveau parcours fermé.

Bien, ceci étant fait, passons aux choses plus amusantes, et concoctez-vous un plateau de 5 lignes et 5 colonnes par exemple. Essayez de faire un parcours fermé du cavalier dans cette configuration, en partant de la case de votre choix.

N’y passez tout de même pas trop de temps : il vous sera impossible de boucler un tel itinéraire dans ce cas !

Des arguments de parité

Il existe sur les plateaux d’échecs classiques une information de taille pour résoudre ce problème : la couleur des cases. En effet, une case sur deux est blanche, l’autre est noire. Finalement, il y a 32 cases blanches et 32 cases noires sur le plateau classique.

Or, un plateau de 5 par 5 cases comportent 25 cases, et donc aura forcément une case blanche ou noire en plus par rapport à l’autre couleur. Et c’est là toute l’astuce !

Lorsqu’il se déplace, notre cavalier parcourt au total 3 cases : ainsi, s’il est au départ sur une case blanche (B), il finit sur une case noire (N) et inversement. Si l’on regarde simplement l’enchaînement des couleurs sur le chemin du cavalier, on aura forcément une suite de B – N ou de N – B : les cases vont ainsi deux par deux.

Or, pour que notre parcours soit fermé, il faut que la dernière case du chemin soit de couleur différente de celle de départ : notre parcours comporte donc un nombre pair de cases, alors que l’échiquier en possède un nombre impair.

Ce résultat vaut donc pour n’importe quel échiquier rectangulaire qui comporte un nombre impair de cases : par cet argument de parité, il ne peut pas y avoir de chemin fermé sur ce type de plateau.

Plus compliqué cette fois, qu’en est-il d’un échiquier de taille 4 x 6 ?

C’est un nouvel argument de parité, avancé par Louis Posa qui va nous donner la réponse ici. En effet, il est possible de colorier les cases de notre plateau de deux manières différentes :

  • D’abord, un coloriage une case sur deux, comme on a l’habitude d’en voir
  • Mais aussi en coloriant d’une couleur la première et la dernière ligne, et d’une autre les deux lignes restantes.

Nous avons déjà vu qu’avec le premier coloriage, on a forcément une alternance entre le noir et le blanc sur le chemin de notre cavalier. Pour le second, il est facile de se convaincre qu’un cavalier qui figure sur les cases rouges devra forcément aller sur une case bleue par la suite. Puisqu’il y a autant de cases rouges que de bleues, on en déduit que dans son parcours fermé, le cavalier doit alterner : Rouge, puis bleu, puis rouge, puis bleu…

Nous allons désormais « mélanger » ces deux coloriages. Supposons qu’on parte de la case en haut à gauche : dans le premier échiquier, cette case est noire ; dans le second, elle est rouge. Par conséquent, au déplacement suivant, le cavalier sera sur une case blanche du premier échiquier, bleue sur le second. Au déplacement d’après, le cavalier sera de nouveau sur une case noire et rouge, puis bleue et blanche, puis noire et rouge, et ainsi de suite.

Finalement, en faisant son tour, le cavalier ne passe que sur des cases qui sont noires et rouges, ou qui sont blanches et bleues. Jamais il ne pourrait passer par une case noire sur le premier échiquier et bleue sur le deuxième. Pourtant, un parcours fermé doit passer par toutes les cases ! Cette contradiction indique donc qu’un tel parcours fermé ne peut exister.

Ce raisonnement vaut pour tous les échiquiers ayant 4 lignes ou 4 colonnes : il est impossible de trouver un parcours fermé du cavalier sur ceux-ci.

En passant par les graphes

Nous avons prouvé qu’il n’existait pas de parcours fermé du cavalier dans les cas suivants :

  • il y a un nombre impair de lignes et un nombre impair de colonnes
  • il y a 4 lignes ou 4 colonnes

Pour comprendre la suite, il nous faut passer par la théorie des graphes. Un graphe, c’est simplement un ensemble de points (les sommets) qui sont reliés entre eux par des arêtes.

Dans le cas de l’échiquier, nous allons matérialiser notre plateau par des sommets. S’il est possible de déplacer le cavalier d’une case à l’autre en un seul coup, alors nous placerons une arête entre les deux sommets de ces cases.

Dans un graphe, un chemin est une suite de sommets connectés par une arête. Si je note (1,2) la case de la ligne 1, colonne 2, alors je peux tracer un chemin qui passe par les cases (1,2) – (2, 4) – (4, 3) – (6, 5)…

Trouver un parcours fermé du cavalier, ça revient dans le graphe à trouver un chemin qui passe une et une seule fois par chaque sommet et qui revient à son point de départ : c’est ce que l’on appelle un cycle hamiltonien.

Imaginez un collier de perles : ces perles, ce sont les sommets du graphe, et le fil qui les relie, c’est le cycle hamiltonien que nous cherchons. Si je retire une perle de mon collier, en coupant de part et d’autre de la perle, mon collier n’est encore qu’en un seul morceau. Certes, il n’est plus relié à lui-même, mais il tient toujours. Si je retire deux perles, alors soit j’ai toujours un seul morceau, soit deux, mais pas plus.

Pour les graphes, le même phénomène se produit : si un graphe comporte un cycle hamiltonien et que je lui retire 2 sommets, il n’est pas possible de créer strictement plus de deux morceaux différents.

Prenons alors l’échiquier a 3 lignes et 6 colonnes : voici ce qu’il se passe lorsque l’on supprime les sommets des lignes 1 et 3 sur la troisième colonne.

Supprimer deux sommets sur l’échiquier coupe le graphe en trois morceaux.

En supprimant les sommets matérialisés par des croix, j’isole les sommets rouges et verts des sommets bleus, et crée ainsi trois morceaux : il ne pouvait donc pas y avoir de cycle hamiltonien dans mon graphe de départ, et donc pas de parcours du cavalier dans un graphe 3 x 6.

Un nouveau raisonnement plus complexe sur ces cycles permet de conclure qu’il n’existe pas non plus de parcours du cavalier fermé sur un échiquier de taille 3 x 8.

Le théorème de Schwenk

Trouver les cas où ça ne fonctionne pas, c’est bien beau. Trouver ceux qui fonctionnent c’est encore mieux. Ca tombe bien, puisque le théorème de Schwenk nous donne toutes ces informations

Théorème de Schwenk : Pour tout échiquier de taille m x n, ou m est inférieur ou égal à n, il existe un parcours fermé du cavalier, sauf si :

  1. m et n sont impairs
  2. m vaut 1, 2 ou 4 et n est différent de 1
  3. m = 3 et n = 4, 6 ou 8

Nous avons vu plus haut un bon nombre de ces situations. Le cas où un côté est de longueur 1 ou 2 est évident : il est impossible pour le cavalier de faire demi-tour sur son échiquier. En revanche, nous n’avons nulle part montré qu’il s’agissait des seuls cas où le parcours fermé était impossible.

Pour ce faire, Schwenk raisonne par induction : il va d’abord trouver des cycles hamiltoniens dans un certain nombre de graphes, puis il va montrer que ces cycles peuvent être « fusionnés » pour former tous les cas possibles.

En effet, Schwenk va montrer que s’il existe un parcours fermé du cavalier sur un échiquier de taille m x n, alors ce parcours peut être prolongé dans un sens sur un échiquier de taille (m+4) x n ou dans l’autre sur un plateau de taille m x (n + 4).

En progressant ainsi par prolongement successif, on atteint ainsi toutes les tailles souhaitées.

Extension d'un cycle

Le cycle hamiltonien sur un graphe de taille 5 x 6 est prolongé sur un graphe de taille 5 x 10. Source en fin d’article.

Par exemple, connaissant la solution pour un échiquier 5 x 6, on peut en déduire une solution sur un échiquier 5 x 10, puis 9 x 10, puis 13 x 10, puis 13 x 14, et ainsi de suite. Il ne suffit alors que d’une poignée de graphes de départ (9 dans ce cas) pour obtenir toutes les solutions.

Les neuf cycles hamiltoniens de base trouvés par Schwenk. Source en fin d’article

Pourquoi 9 ? Puisque l’on progresse en ajoutant lignes ou colonnes par paquet de 4, il suffit de s’intéresser à un nombre restreint d’entiers. Les entiers peuvent se répartir en 4 classes, qui sont les suivantes :

  • 1, 5, 9, 13, 17… et tous les entiers de la forme 4k +1, avec k entier
  • 2, 6, 10, 14, 18… 4k + 2
  • 3, 7, 11, 15, 19, 23… 4k + 3
  • 4, 8, 12, 16, 20, 24… 4k

Il suffit donc de prendre un représentant convenable dans chacune de ces classes. Nous savons qu’il nous est impossible de créer des parcours fermés du cavalier si l’un des côtés de l’échiquier est de longueur 1, 2 ou 4. Aussi, nous choisirons pour représentants le nombre 5 pour la première classe, 6 pour la deuxième, 3 pour la troisième et 8 pour la quatrième, puis nous combinons tout ce beau monde pour faire nos échiquiers de base.

5 x 5 – 5 x 6 – 5 x 3 – 5 x 8 – 6 x 6 – 6 x 3 – 6 x 8 – 3 x 33 x 8 – 8 x 8

Parmi ceux-ci, nous devons supprimer les cas où les deux côtés sont de longueur impaire, car il n’est pas possible d’y trouver un cycle hamiltonien. Pour le cas 3 x 6, également impossible, il faut passer aux représentants suivants : on obtient les cas 7 x 6 et 3 x 10. Même chose pour le 3 x 8 qui est remplacé par les échiquiers 7 x 8 et 3 x 12.

Finalement, nos 9 échiquiers de base sont les suivants :

5 x 6, 5 x 8, 6 x 6, 7 x 6, 3 x 10, 6 x 8, 7 x 8, 3 x 12, 8 x 8

Et le tour est joué !

Pour compléter

Cet article a été publié dans Curiosités et récréation. Ajoutez ce permalien à vos favoris.

Un commentaire pour La ronde des cavaliers

  1. Ping : La ronde des cavaliers : Deuxième prise ! | Automaths

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s