Échecs et maths : le problème du cavalier

Le problème du cavalier est certainement le sujet qui intéresse le plus mes lecteurs depuis que j’ai lancé ce blog. J’en avais parlé à deux reprises dans des newsletters, mais sans jamais poser les démonstrations.

Et puisque je reçois tous les ans plusieurs sollicitations sur comment aborder ce sujet, il est grand temps que je réponde de façon structurée et méthodique à la question.

La problématique : sur quels échiquiers rectangulaires le problème du cavalier admet-il une solution ? C’est une vraie question mathématique, et la réponse est un théorème publié en 1991.

Le problème

Un cavalier est une pièce d’échecs qui se déplace en L : deux cases dans une direction, puis une case perpendiculaire. Depuis une case au centre de l’échiquier, il dispose de 8 destinations possibles.

Les 8 destinations possibles du cavalier (en vert) depuis la case c3. Chaque déplacement forme un L : deux cases dans une direction, une perpendiculaire.

Le problème du cavalier, c’est la question suivante : peut-on placer un cavalier sur une case de l’échiquier et lui faire visiter toutes les cases, exactement une fois chacune ?

Sur un échiquier standard 8×8, la réponse est oui. On dénombre plus de 26 000 milliards de circuits fermés distincts (26 534 728 821 064 exactement). Ce chiffre donne une idée de la richesse combinatoire du problème.

Mais il faut distinguer deux variantes :

Tour ouvert (ou chemin) : le cavalier part d’une case et termine sur une case différente. Il visite les 64 cases sans jamais repasser par la même.
Tour fermé (ou circuit) : le cavalier termine sur une case depuis laquelle il peut revenir à son point de départ en un seul coup. Il boucle.

La question qui nous intéresse dans cet article, c’est celle des tours fermés. Pas seulement sur le 8×8, mais sur n’importe quel échiquier rectangulaire $m \times n$ .

La théorie des graphes comme outil

Pour étudier le problème du cavalier rigoureusement, on a besoin d’un outil : la théorie des graphes. L’idée est simple. On transforme l’échiquier en un graphe :

Chaque case de l’échiquier devient un sommet.
Deux sommets sont reliés par une arête si un cavalier peut passer de l’un à l’autre en un seul coup.

Le graphe obtenu s’appelle le graphe du cavalier. Sur un échiquier $m \times n$ , il a $mn$ sommets, et chaque sommet a entre 2 et 8 voisins selon sa position sur l’échiquier.

Regardons ce que ça donne sur le plus petit échiquier carré, le 3×3 :

Le graphe du cavalier sur un échiquier 3×3. La case centrale (1,1) en rouge est isolée : aucun coup de cavalier ne peut l'atteindre. Les 8 cases du bord forment un cycle.

Tu vois immédiatement le problème. La case centrale (1,1) est isolée : elle n’est reliée à aucune autre case. Aucun coup de cavalier ne peut y mener, et aucun ne peut en partir. On y reviendra dans la première démonstration.

Ce graphe a une propriété fondamentale : il est biparti. Colorie l’échiquier comme un damier, cases blanches et cases noires en alternance. Chaque coup de cavalier change la couleur de la case : tu es sur du blanc, tu atterris sur du noir, et inversement. Les sommets se répartissent donc en deux ensembles $B$ (blanches) et $N$ (noires), et chaque arête relie un sommet de $B$ à un sommet de $N$ .

Sur un échiquier $m \times n$ , le nombre de cases blanches et noires dépend de la parité de $m$ et $n$ :

\displaystyle |B| = \left\lceil \frac{mn}{2} \right\rceil \qquad |N| = \left\lfloor \frac{mn}{2} \right\rfloor

Si $mn$ est pair, on a $|B| = |N| = \frac{mn}{2}$ . Si $mn$ est impair, on a $|B| = |N| + 1$ : il y a une case blanche de plus que de noires.

Retiens bien cette propriété. Elle va servir tout de suite.

Les petits échiquiers : trois preuves

On entre dans le vif du sujet. Voici trois démonstrations complètes, de la plus simple à la plus ambitieuse. Chacune utilise une technique différente, et chacune couvre un cas du théorème de Schwenk qu’on verra ensuite.

L’échiquier 3×3 n’admet aucun tour

C’est la preuve la plus courte de cet article, et elle repose sur un constat brutal.

Sur un échiquier 3×3, on numérote les cases par leurs coordonnées $(i, j)$ avec $i, j \in \{0, 1, 2\}$ . La case centrale est $(1, 1)$ .

Depuis $(1, 1)$ , les 8 destinations théoriques d’un cavalier sont :

\displaystyle (1 \pm 1,\; 1 \pm 2) \quad \text{et} \quad (1 \pm 2,\; 1 \pm 1)

Calculons-les une par une : $(0, -1)$ , $(0, 3)$ , $(2, -1)$ , $(2, 3)$ , $(-1, 0)$ , $(-1, 2)$ , $(3, 0)$ , $(3, 2)$ . Les huit tombent en dehors de l’échiquier, puisque les coordonnées doivent rester dans $\{0, 1, 2\}$ .

Conséquence : dans le graphe du cavalier 3×3, la case $(1, 1)$ a degré 0. Elle est isolée. Aucun chemin ne peut la visiter, donc aucun chemin hamiltonien n’existe. A fortiori, aucun cycle hamiltonien non plus.

Le 3×3 n’admet ni tour ouvert, ni tour fermé. Point final.

L’échiquier 5×5 n’admet pas de tour fermé

Cette preuve utilise la bipartition du graphe et un argument de parité. C’est probablement la démonstration la plus élégante de cet article.

L’échiquier 5×5 a 25 cases. Avec la coloration standard du damier :

\displaystyle |B| = 13 \quad \text{cases blanches} \qquad |N| = 12 \quad \text{cases noires}

Supposons par l’absurde qu’un tour fermé existe. Ce tour fermé est un cycle hamiltonien : il visite les 25 cases et revient au point de départ.

Or, le graphe du cavalier est biparti. Dans un graphe biparti, tout cycle alterne entre les deux ensembles de sommets. Si le cycle passe par $k$ sommets, il fait $k$ arêtes et alterne $k$ fois entre $B$ et $N$ . Pour que le cycle se referme, il faut que $k$ soit pair : après un nombre pair d’alternances, on revient dans l’ensemble de départ.

Mais notre cycle passe par les 25 sommets, donc $k = 25$ . Et 25 est impair.

Contradiction. Le tour fermé ne peut pas exister sur le 5×5.

Cet argument se généralise immédiatement : sur tout échiquier $m \times n$ avec $m$ et $n$ tous les deux impairs, le produit $mn$ est impair, et un tour fermé est impossible.

Précision importante : le 5×5 admet quand même des tours ouverts. Il en existe 64 géométriquement distincts (1 728 au total en comptant les symétries). Mais aucun ne peut se boucler.

L’échiquier 4×n n’admet pas de tour fermé

Cette preuve est la plus ambitieuse des trois. Elle utilise un argument de double coloration attribué à Pósa. L’idée est de combiner deux colorations indépendantes de l’échiquier pour arriver à une contradiction.

Coloration 1 : le damier standard. On colorie les cases en noir et blanc comme un échiquier classique. Le cavalier alterne entre les deux couleurs à chaque coup. On note cette partition $B \cup N$ .

Coloration 2 : rangées internes et externes. Sur un échiquier 4×n (4 rangées, $n$ colonnes), on distingue :

Les rangées externes : rangées 1 et 4 (les bords).
Les rangées internes : rangées 2 et 3 (le centre).

Il y a $2n$ cases externes et $2n$ cases internes.

Double coloration d'un échiquier 4×6. Le damier classique (cases claires/foncées) alterne à chaque coup de cavalier. Les rangées externes (1 et 4, en rouge) et internes (2 et 3, en bleu) alternent aussi.

Vérifie par toi-même : depuis une case externe (rangée 1 ou 4), le cavalier ne peut atterrir que sur une case interne (rangée 2 ou 3), et vice versa. Le cavalier alterne aussi entre cases internes et externes.

Combinons les deux colorations. Supposons par l’absurde qu’un tour fermé existe sur le 4×n. Ce tour visite les $4n$ cases en alternant :

noir → blanc → noir → blanc (coloration 1)
externe → interne → externe → interne (coloration 2)

Dans un tour fermé de longueur $4n$ , chaque type de case est visité exactement $2n$ fois (puisque le tour alterne). Donc il y a exactement $2n$ cases noires et $2n$ blanches visitées, et exactement $2n$ internes et $2n$ externes visitées.

Maintenant, la clé. Les cases qui sont à la fois externes et blanches sont visitées en alternance avec les cases internes et noires. Quand le cavalier est sur une case externe blanche, son prochain coup l’amène sur une case interne noire, et vice versa.

Or sur un échiquier 4×n, les cases externes de la rangée 1 contiennent les deux couleurs : la case (1,1) est d’une couleur, la case (1,2) est de l’autre. Cela impose que le nombre de cases externes blanches soit égal au nombre de cases externes noires, soit $n$ de chaque. La même chose vaut pour les cases internes.

Mais si l’on suit la double alternance dans le cycle, on aboutit à la contrainte que toutes les cases externes devraient être de la même couleur pour maintenir la double alternance dans un cycle. Or la rangée 1 contient des cases des deux couleurs.

Contradiction. Aucun tour fermé n’existe sur un échiquier 4×n, quel que soit $n$ .

Le théorème de Schwenk

On a maintenant trois preuves d’impossibilité. Chacune couvre des cas différents. En 1991, le mathématicien Allen Schwenk a publié un théorème qui caractérise complètement les échiquiers rectangulaires admettant un tour fermé.

Théorème de Schwenk (1991). Un tour fermé du cavalier existe sur un échiquier m × n (en vert) sauf si m et n sont impairs, si min(m,n) vaut 1, 2 ou 4, ou si min(m,n) = 3 et max vaut 4, 6 ou 8.

Voici l’énoncé, en version rigoureuse.

Théorème (Schwenk, 1991). Soit un échiquier $m \times n$ avec $1 \leq m \leq n$ . Un tour fermé du cavalier existe si et seulement si aucune des trois conditions suivantes n’est vérifiée :

(a) $m$ et $n$ sont tous les deux impairs ;

(b) $m \in \{1, 2, 4\}$ ;

(c) $m = 3$ et $n \in \{4, 6, 8\}$ .

Relis chaque condition et relie-la à ce qu’on a démontré :

Condition (a) : c’est exactement notre preuve de parité sur le 5×5. Si $m$ et $n$ sont impairs, $mn$ est impair, et un cycle hamiltonien dans un graphe biparti de taille impaire ne peut pas exister.
Condition (b) : le cas $m = 4$ est couvert par l’argument de Pósa (double coloration). Les cas $m = 1$ et $m = 2$ sont triviaux : sur une seule rangée ou deux rangées, le cavalier n’a pas assez de place pour manœuvrer.
Condition (c) : ces trois cas particuliers ( $3 \times 4$ , $3 \times 6$ , $3 \times 8$ ) se démontrent par un argument de connexité : on montre que retirer certains sommets du graphe le déconnecte en trop de composantes pour qu’un cycle hamiltonien puisse exister. On admet ce résultat.

La partie la plus difficile du théorème, c’est la réciproque : prouver que dans tous les autres cas, un tour fermé existe. Schwenk construit des tours fermés sur 9 échiquiers de base ( $5 \times 6$ , $5 \times 8$ , $6 \times 6$ , $7 \times 6$ , $3 \times 10$ , $6 \times 8$ , $7 \times 8$ , $3 \times 12$ , $8 \times 8$ ), puis démontre un lemme d’extension.

Lemme d’extension. Si un tour fermé du cavalier existe sur un échiquier $m \times n$ , alors il existe aussi sur l’échiquier $m \times (n + 4)$ .

Par récurrence, il couvre tous les cas restants. On admet cette construction. C’est un résultat de recherche, pas un exercice de lycée.

Un problème millénaire

Le problème du cavalier ne date pas d’hier. Sa première trace écrite connue remonte au IXe siècle, dans un manuscrit d’al-Adli ar-Rumi, joueur d’échecs à la cour de Bagdad vers 840. Il y décrit un tour du cavalier sur l’échiquier 8×8.

Mais c’est Leonhard Euler qui, en 1759, donne au problème sa première formulation mathématique rigoureuse. Dans un mémoire intitulé Solution d’une question curieuse qui ne paroît soumise à aucune analyse, il développe une méthode systématique de construction et produit des dizaines de tours sur le 8×8. Il introduit la distinction entre tours “rentrants” (fermés) et non rentrants (ouverts).

En 1823, H.C. Warnsdorff propose une heuristique élégante pour trouver un tour sans calcul exhaustif.

Parcours de Warnsdorff sur un échiquier 5×5. Le cavalier part de la case 1 (en vert) et choisit toujours la case ayant le moins de voisins libres. Il visite les 25 cases et termine en case 25 (en rouge).

Il faudra attendre 1991 et Allen Schwenk pour obtenir la caractérisation complète qu’on a vue plus haut.

Chronologie du problème du cavalier

graph LR
  A["al-Adli ar-Rumi
~840"] --> B["Leonhard Euler
1759"]
  B --> C["H.C. Warnsdorff
1823"]
  C --> D["Allen Schwenk
1991"]

Ton plan grand oral, minute par minute

Voici un plan détaillé pour un passage de 5 minutes. Chaque étape est calibrée. Ne dépasse pas les temps indiqués : le grand oral punit les candidats qui s’éternisent sur l’introduction.

Plan chronométré

0:00 – 0:30 · Accroche

Pose le problème concrètement. Un cavalier, un échiquier, visiter toutes les cases. Le chiffre 26 534 milliards de circuits sur le 8×8. Question : sur quels échiquiers est-ce possible ?

0:30 – 1:30 · Modélisation

Transforme l'échiquier en graphe. Définis sommet, arête, chemin hamiltonien, cycle hamiltonien. Montre que le graphe est biparti (coloration damier). Premier exemple : le 3×3 est impossible (case centrale isolée, degré 0).

1:30 – 2:30 · Preuve de parité

Démontre que le 5×5 n'admet pas de tour fermé. Argument : graphe biparti, 25 sommets, un cycle de longueur impaire est impossible dans un graphe biparti. Généralise : tout m×n avec m et n impairs est exclu.

2:30 – 3:30 · Double coloration

Esquisse l'argument de Pósa pour le 4×n. Double alternance (damier + interne/externe). Pas besoin de tout détailler : donne l'idée et la conclusion. Dis honnêtement ce que tu admets.

3:30 – 4:30 · Théorème de Schwenk

Énonce le théorème avec ses trois conditions. Montre au jury comment chaque condition correspond à une preuve (parité, Pósa, connexité). Mentionne la construction par récurrence (admise).

4:30 – 5:00 · Ouverture

Mentionne la règle de Warnsdorff (algorithme glouton, lien avec la NSI). Le problème hamiltonien est NP-complet dans le cas général : aucun algorithme efficace connu pour tous les graphes.

Avant ton passage, vérifie que...

Tu sais définir un graphe, un chemin hamiltonien, un cycle hamiltonien
Tu sais expliquer pourquoi le graphe du cavalier est biparti
Tu sais démontrer l'impossibilité sur le 3×3 (centre isolé, degré 0)
Tu sais démontrer l'impossibilité d'un tour fermé sur le 5×5 (parité)
Tu connais l'idée de l'argument de Pósa pour le 4×n (double coloration)
Tu sais énoncer le théorème de Schwenk avec ses trois conditions
Tu sais relier chaque condition à la preuve correspondante
Tu as préparé un support visuel (échiquier dessiné ou graphe)
Tu sais expliquer la règle de Warnsdorff en une phrase
Tu sais ce que tu admets et tu l'assumes

Pour conclure

Le problème du cavalier n’est pas un sujet de grand oral facile : c’est un sujet qui tient la route mathématiquement, avec de vraies démonstrations, un vrai théorème, et de vrais outils.

Si tu maîtrises les trois preuves de cet article (centre isolé sur le 3×3, parité sur le 5×5, double coloration sur le 4×n), que tu sais énoncer Schwenk proprement, et que tu es honnête sur ce que tu admets, tu as un grand oral solide. Pas brillant par sa forme, mais solide par son fond. C’est exactement ce qu’un jury attend.

Sources

Schwenk, A.J. (1991). “Which Rectangular Chessboards Have a Knight’s Tour?” Mathematics Magazine, 64(5), pp. 325-332.
Euler, L. (1759). “Solution d’une question curieuse qui ne paroît soumise à aucune analyse”. Mémoires de l’Académie royale des sciences et belles-lettres de Berlin, 15, pp. 310-337.
Warnsdorff, H.C. (1823). Des Rösselsprunges einfachste und allgemeinste Lösung. Schmalkalden.
Conrad, A. et al. (1994). “Hamilton cycles in the graph of the knight on the chessboard”. Journal of Computational and Applied Mathematics, 54(3), pp. 367-375.
Numberphile : “Knight’s Tour” (YouTube). Accessible et bien vulgarisé.