Huit dames, tour du cavalier, échiquier tronqué : les casse-têtes mathématiques phares de l'échiquier

Ces défis s'appuient sur les pièces ou sur le quadrillage, sans toutefois relever de la partie elle-même : il s'agit de véritables questions de mathématiques, abordables dès le collège, et que certaines grandes figures de la discipline ont travaillées. Ils conviennent parfaitement à un club de mathématiques, à un exposé ou à un sujet de grand oral.

Tableau récapitulatif

Le casse-tête des huit dames

Problème des huit dames

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

Le problème a été publié en 1848 par Max Bezzel, auteur de problèmes d'échecs. Franz Nauck en a livré les 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 s'y sont penchés.

Objectif : dénicher une disposition, puis toutes les autres. On en recense 92. Un grand nombre se déduisent les unes des autres par rotation ou par symétrie de l'échiquier ; en les regroupant, il demeure 12 solutions fondamentales. En voici une, avec les dames placées en d8, g7, c6, h5, b4, e3, a2 et f1 :

Il est aisé de constater qu'une dame se trouve sur chaque ligne et sur chaque colonne. Pour les diagonales, il suffit de vérifier que, pour deux dames données, l'écart entre colonnes n'est jamais identique à l'écart entre lignes.

Comment le résoudre ?

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 ; lorsqu'aucune case ne convient, on revient en arrière pour déplacer la dame précédente. Il s'agit d'un exercice fort 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 casse-tête du cavalier d'Euler

Problème du cavalier

Déterminer une suite de déplacements du 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 permet de reprendre la boucle.

La question est fort ancienne : un parcours du cavalier sur un demi-échiquier apparaît 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 », remis 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 13 267 364 410 532 lorsqu'on considère qu'un parcours et son inverse ne forment qu'une seule solution.

Un parcours à contrôler sur un échiquier de 5 × 5

Pour s'exercer, on peut commencer par plus petit. Voici un parcours ouvert qui visite les 25 cases d'un échiquier de 5 × 5 : suivez les nombres de 1 à 25, chacun se trouvant à un saut de cavalier du précédent.

Ce parcours a été construit à l'aide de la règle de Warnsdorff, et chaque saut a été contrôlé. Défi : en trouver un autre qui débute au centre.

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

Le sujet se prête bien à l'oral du baccalauréat en spécialité mathématiques ou NSI : modélisation par un graphe (les cases constituent les sommets, les sauts possibles forment les arêtes), recherche d'un chemin passant par tous les sommets, algorithme de retour sur trace, règle de Warnsdorff et son efficacité. On peut également expliquer 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 tronqué

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

Réponse : non. Chaque domino recouvre nécessairement une case blanche et une case noire. Les 31 dominos couvriraient donc 31 cases blanches et 31 cases noires. Or les deux coins retirés sont de même couleur : il reste 32 cases d'une couleur et 30 de l'autre. Le recouvrement est 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 chronique de Scientific American.

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

Polyominos et pentominos

Un polyomino désigne une figure formée de carrés identiques accolés par leurs côtés ; le domino en compte deux, le pentomino en compte cinq. Le mathématicien Solomon Golomb a introduit et étudié ces figures à partir de 1953. On dénombre 12 pentominos distincts (une pièce retournée ou tournée étant considérée comme identique), qui couvrent ensemble 60 cases.

Or un échiquier compte 64 cases, soit 60 + 4 : on peut donc chercher à 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 du retour sur trace : on obtient 65 solutions. Autre défi célèbre : le rectangle de 6 × 10 peut être pavé de 2 339 façons différentes avec les 12 pentominos.

Quel est le nombre de carrés présents sur un échiquier ?

La réponse « 64 » est erronée, ou du moins incomplète : elle ne prend en compte que les petits carrés. Il faut aussi 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éfini par le choix de 2 lignes parmi les 9 lignes du quadrillage et de 2 colonnes parmi 9, soit 36 × 36.

Pour continuer

Ces problèmes font appel à des notions précises : parité, coloration, dénombrement, graphes. Nous les détaillons, accompagnés d'exercices destinés à l'école et au collège, sur la page les notions mathématiques mobilisées sur l'échiquier. Pour d'autres nombres très grands, consultez l'échiquier de Sissa. Et si les énigmes vous plaisent, le blogue du Palais des Échecs propose les défis de logique du Palais des Échecs, mis à jour régulièrement. Si vous habitez au Québec et souhaitez pratiquer ou organiser des activités de ce type, la Fédération québécoise des échecs (FQE) ou la Chess Federation of Canada peuvent vous renseigner sur les clubs et les événements près de chez vous, à Montréal, Québec, Sherbrooke ou Gatineau.