Huit dames, cavalier d'Euler, échiquier amputé : les grands casse-têtes mathématiques de l'échiquier

Ces énigmes se résolvent avec les pièces ou le quadrillage, sans pour autant relever de la pratique d'une partie : il s'agit de véritables questions mathématiques, abordables dès le collège, et que de grands noms de la discipline ont étudiées. Elles conviennent parfaitement à un cercle de mathématiques, à un exposé ou à un sujet d'oral.

Tableau récapitulatif

Le problème des huit dames

Problème des huit dames

Disposer huit dames sur un échiquier de 8 × 8 de telle sorte qu'aucune ne puisse en capturer une autre : pas deux dames sur la même ligne, la même colonne ou la même diagonale.

Max Bezzel a fait paraître ce problème en 1848, lui qui concevait des problèmes d'échecs. Franz Nauck a publié les toutes premières solutions en 1850 et l'a étendu à n dames sur un échiquier de n × n cases. Carl Friedrich Gauss figure parmi les mathématiciens qui ont porté leur attention sur cette question.

Objectif : dégager une disposition, puis l'ensemble des dispositions. On en dénombre 92. Bon nombre d'entre elles se déduisent les unes des autres par rotation ou symétrie de l'échiquier ; en les regroupant, il ne subsiste que 12 solutions fondamentales. En voici une, les dames occupant les cases d8, g7, c6, h5, b4, e3, a2 et f1 :

Il est aisé de constater qu'il y a une dame par ligne et par colonne. Quant aux diagonales, il suffit de vérifier que, pour deux dames quelconques, l'écart entre les colonnes n'est jamais égal à l'écart entre les lignes.

Comment s'y prendre ?

La méthode traditionnelle repose sur le retour sur trace (backtracking en anglais) : on pose une dame dans la première colonne, puis une dame dans la deuxième colonne sur une case non menacée, et ainsi de suite ; si aucune case n'est disponible, on revient en arrière pour déplacer la dame précédente. C'est un exercice très prisé en informatique au lycée. La version à n dames admet des solutions pour toute valeur de n, à l'exception de 2 et 3 : on en compte par exemple 2 pour n = 4, 10 pour n = 5, 4 pour n = 6 et 40 pour n = 7.

Le problème du cavalier d'Euler

Problème du cavalier

Déterminer une succession de sauts de cavalier qui passe une seule fois par chacune des 64 cases. Le parcours est qualifié de fermé lorsque la dernière case se trouve à un saut de cavalier de la première, ce qui autorise à reprendre la boucle.

La question est fort ancienne : un parcours du cavalier sur un demi-échiquier figure déjà dans un traité de poétique sanskrit du IX^e siècle, le Kavyalankara de Rudrata. Leonhard Euler lui a consacré un mémoire intitulé « Solution d'une question curieuse qui ne paroit soumise à aucune analyse », présenté en 1759 et publié en 1766 dans les mémoires de l'Académie des sciences de Berlin. En 1823, H. C. von Warnsdorff a suggéré une règle simple pour construire un parcours : se diriger toujours vers la case qui offrira au cavalier le moins de sorties possibles.

L'échiquier ordinaire admet un nombre colossal de parcours fermés : 26 534 728 821 064 si l'on tient compte du sens de parcours, soit la moitié, 13 267 364 410 532, lorsqu'on considère qu'un trajet et son sens inverse ne font qu'un.

Un parcours à vérifier sur un échiquier de 5 × 5

Pour s'exercer, on peut débuter avec un plateau plus réduit. Voici un trajet ouvert qui traverse les 25 cases d'un échiquier de 5 × 5 : suivez les numéros de 1 à 25, chacun étant situé à un saut de cavalier du précédent.

Ce trajet a été établi au moyen de la règle de Warnsdorff, et chaque saut a fait l'objet d'une vérification. Défi : en découvrir un autre qui prend son départ au centre.

Le problème du cavalier à l'oral du grand oral

Le sujet se prête bien à l'épreuve orale du baccalauréat, qu'il s'agisse de la spécialité mathématiques ou de NSI : modélisation au moyen d'un graphe (les cases sont les sommets, les sauts possibles les arêtes), recherche d'un chemin qui visite tous les sommets, algorithme de retour sur trace, règle de Warnsdorff et son efficacité. On peut également montrer pourquoi aucun parcours fermé n'existe sur un échiquier de 5 × 5 : le cavalier change de couleur à chaque saut, si bien qu'une boucle comporte nécessairement un nombre pair de cases, alors que 25 est impair.

L'échiquier amputé

Le philosophe Max Black a formulé ce problème en 1946 dans son ouvrage Critical Thinking. On ôte deux coins opposés d'un échiquier (par exemple a1 et h8). Est-il possible de recouvrir les 62 cases restantes au moyen de 31 dominos, chacun couvrant deux cases voisines ?

Réponse : non. Chaque domino recouvre nécessairement une case blanche et une case noire. 31 dominos couvriraient donc 31 cases blanches et 31 cases noires. Or les deux coins opposés sont de même couleur : il reste 32 cases d'une couleur et 30 de l'autre. Le pavage est donc impossible, sans qu'il soit nécessaire d'essayer la moindre disposition. Martin Gardner a fait connaître ce problème au grand public en 1957, dans sa rubrique de Scientific American.

Et si l'on retire une case blanche et une case noire ? Ralph Gomory a démontré (résultat publié en 1973) que le pavage est alors toujours réalisable, quelles que soient les deux cases ôtées.

Polyominos et pentominos

Un polyomino est une figure formée de carrés identiques accolés par leurs côtés ; le domino en compte deux, le pentomino cinq. Le mathématicien Solomon Golomb a introduit et étudié ces figures à partir de 1953. Il existe 12 pentominos distincts (en considérant qu'une pièce retournée ou tournée demeure la même), qui recouvrent ensemble 60 cases.

Or un échiquier compte 64 cases, soit 60 + 4 : on peut donc tenter de disposer les 12 pentominos sur l'échiquier en laissant libre un carré de 2 × 2 au centre. En 1958, Dana Scott a confié la résolution de ce problème à un ordinateur, l'un des premiers emplois de la méthode de retour sur trace : il existe 65 solutions. Autre défi fameux : le rectangle de 6 × 10 peut être pavé de 2 339 façons différentes avec les 12 pentominos.

Combien de carrés sur un échiquier ?

La réponse « 64 » est fausse, ou plutôt incomplète : elle ne prend en compte que les petits carrés. Il faut également dénombrer les carrés de 2 × 2, de 3 × 3… jusqu'au grand carré de 8 × 8.

Le total correspond à la somme des carrés des entiers de 1 à 8 : 1 + 4 + 9 + … + 64 = 204. Pour aller plus loin : un échiquier renferme 1 296 rectangles (carrés compris), puisqu'un rectangle est déterminé par le choix de 2 lignes parmi les 9 du quadrillage et de 2 colonnes parmi 9, soit 36 × 36.

Pour poursuivre

Ces problèmes mettent en jeu des notions précises : parité, coloration, dénombrement, graphes. Nous les détaillons, avec des exercices destinés à l'école et au collège, sur la page les notions mobilisées sur l'échiquier. Pour de très grands nombres, voir l'échiquier de Sissa. Et pour les amateurs d'énigmes, le blog du Palais des Échecs propose les défis de logique du Palais des Échecs, renouvelés régulièrement. Les lecteurs du Luxembourg, qu'ils habitent Luxembourg-Ville, Esch-sur-Alzette ou Differdange, trouveront aussi des pistes de pratique auprès de la FLDE, la fédération luxembourgeoise.