Huit dames, parcours du cavalier et damier amputé : les grands casse-têtes mathématiques du plateau

Ces énigmes se résolvent avec les pièces ou le quadrillage du damier, mais elles relèvent avant tout des mathématiques et non d'une partie : elles sont à la portée d'élèves dès le collège, et certaines ont retenu l'attention de grands noms de la discipline. Elles conviennent parfaitement à un cercle de mathématiques, à un exposé ou à un sujet d'oral de fin d'études, en Suisse romande comme ailleurs.

Tableau de synthèse

Le casse-tête des huit dames

Le problème des huit dames

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

Ce 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 damier de n × n cases. Carl Friedrich Gauss figure parmi les mathématiciens qui s'y sont intéressés.

Objectif : trouver une disposition, puis toutes les autres. Il en existe 92. Un grand nombre d'entre elles se déduisent les unes des autres par rotation ou symétrie du damier ; si l'on procède à ce regroupement, il subsiste 12 solutions fondamentales. En voici une, les dames occupant les cases d8, g7, c6, h5, b4, e3, a2 et f1 :

On constate sans peine qu'il n'y a qu'une dame par ligne et par colonne. Pour les diagonales, il suffit de vérifier que, pour deux dames données, l'écart entre leurs colonnes n'est jamais égal à l'écart entre leurs lignes.

Comment le résoudre ?

La méthode traditionnelle consiste en un retour arrière (en anglais backtracking) : 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. Ce procédé est très apprécié en cours d'informatique au lycée. La version à n dames admet des solutions pour toute valeur de n, sauf 2 et 3 : par exemple 2 solutions pour n = 4, 10 pour n = 5, 4 pour n = 6, 40 pour n = 7.

Le tour du cavalier selon Euler

Le problème du cavalier

Il s'agit de trouver une suite de sauts de cavalier qui passe une seule fois par chacune des 64 cases. Le parcours est dit fermé si la dernière case se trouve à un saut de cavalier de la première, ce qui permet de reprendre la boucle depuis le début.

Le problème est fort ancien : 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, « 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 proposé une règle simple pour bâtir un parcours : se diriger toujours vers la case depuis laquelle le cavalier disposera du moins de sorties possibles.

Le damier ordinaire offre un nombre prodigieux 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, si l'on considère qu'un trajet et son inverse ne font qu'un.

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

Pour s'exercer, on peut commencer par plus petit. Voici un parcours ouvert qui visite les 25 cases d'un damier 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 avec 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 pour l'oral

Le sujet se prête bien à une épreuve orale du baccalauréat, qu'il s'agisse de la spécialité mathématiques ou de NSI (en France, pour les lecteurs qui s'y intéressent) : modélisation par un graphe (les cases sont les sommets, les sauts possibles en constituent les arêtes), recherche d'un chemin qui passe par tous les sommets, algorithme de retour arrière, règle de Warnsdorff et son efficacité. On peut aussi expliquer pourquoi aucun parcours fermé n'existe sur un damier de 5 × 5 : à chaque saut, le cavalier change de couleur, donc une boucle compte forcément un nombre pair de cases, alors que 25 est impair.

Le damier amputé

Le philosophe Max Black a formulé ce problème en 1946 dans son ouvrage Critical Thinking. On retire deux coins opposés d'un damier (par exemple a1 et h8). Peut-on recouvrir les 62 cases restantes avec 31 dominos, chaque domino occupant 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 la même couleur : il reste 32 cases d'une couleur et 30 de l'autre. Le recouvrement est impossible, sans qu'il soit besoin 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 ôte une case blanche et une case noire ? Ralph Gomory a démontré (résultat publié en 1973) que le recouvrement est alors toujours réalisable, quelles que soient les deux cases retiré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 (une pièce retournée ou tournée étant considérée comme identique), qui recouvrent ensemble 60 cases.

Or un damier compte 64 cases, soit 60 + 4 : on peut donc chercher à poser les 12 pentominos sur le damier en laissant libre un carré de 2 × 2 au centre. En 1958, Dana Scott a fait résoudre ce problème par ordinateur, l'un des premiers emplois de la méthode du retour arrière : il existe 65 solutions. Autre défi célèbre : le rectangle de 6 × 10 se pave de 2 339 manières différentes avec les 12 pentominos.

Combien de carrés sur un damier ?

La réponse « 64 » est fausse, 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 damier contient 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 poursuivre

Ces problèmes mobilisent des notions précises : parité, coloration, dénombrement, graphes. Nous les détaillons, avec des exercices pour l'école et le collège, sur la page les notions mathématiques mobilisées sur le damier. Pour de très grands nombres, voir l'échiquier de Sissa. Et pour les amateurs d'énigmes, le blog du Palais des Échecs propose ses défis de logique, renouvelés régulièrement.