Huit dames, cavalier d'Euler, échiquier amputé : les grands défis mathématiques du damier

Ces défis se jouent avec les pièces ou le quadrillage du damier, mais ils ne relèvent pas 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. Ils conviennent parfaitement à un club de mathématiques, à un exposé ou à une épreuve orale.

Tableau de synthèse

Le problème des huit dames

Problème des huit dames

Disposer huit dames sur un damier de 8 × 8 de sorte 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 fait paraître les premières solutions en 1850 et l'a étendu au cas de n dames sur un damier de n × n cases. Carl Friedrich Gauss figure parmi les mathématiciens qui se sont penchés sur cette question.

Objectif du problème : trouver une disposition, puis toutes les autres. Il en existe 92. Un grand nombre s'obtiennent les unes à partir des autres par rotation ou symétrie du damier ; en les regroupant, il ne subsiste que 12 solutions fondamentales. En voici une, avec les dames en d8, g7, c6, h5, b4, e3, a2 et f1 :

On contrôle aisément qu'il y a une dame par ligne et par colonne. Pour les diagonales, il suffit de vérifier que, pour deux dames quelconques, l'écart entre colonnes n'est jamais égal à l'écart entre lignes.

Comment s'y prendre ?

La méthode traditionnelle est le retour sur trace (en anglais backtracking) : on place une dame dans la première colonne, puis une autre 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 et l'on déplace 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 tout 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 problème du cavalier d'Euler

Problème du cavalier

Trouver une suite de sauts de cavalier qui passe une fois et une seule par chacune des 64 cases. Le circuit 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é sanskrit de poétique du IX^e siècle, le Kavyalankara de Rudrata. Leonhard Euler y 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 construire un parcours : se diriger toujours vers la case d'où le cavalier disposera du moins grand nombre de sorties.

Le damier ordinaire offre un nombre considérable de circuits fermés : 26 534 728 821 064 en tenant compte du sens de parcours, soit la moitié, 13 267 364 410 532, si l'on considère qu'un circuit et son inverse sont identiques.

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

Pour s'exercer, on peut commencer par un format plus réduit. 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 à l'oral

Ce sujet se prête bien à l'épreuve orale du baccalauréat en spécialité mathématiques ou NSI : modélisation par un graphe (les cases sont les sommets, les sauts possibles sont les arêtes), recherche d'un chemin qui passe par tous les sommets, algorithme de retour sur trace, règle de Warnsdorff et son efficacité. On peut également expliquer pourquoi aucun circuit fermé n'existe sur un damier de 5 × 5 : le cavalier change de couleur à chaque saut, donc une boucle comporte nécessairement un nombre pair de cases, or 25 est impair.

L'échiquier amputé

Le philosophe Max Black a posé ce problème en 1946 dans son ouvrage Critical Thinking. On retire deux coins opposés du damier (par exemple a1 et h8). Peut-on 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. 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 pavage 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 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 supprimées.

Polyominos et pentominos

Un polyomino est une figure composé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 différents (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 confié la résolution de ce problème à un ordinateur, l'un des premiers usages de la méthode de retour sur trace : on obtient 65 solutions. Autre défi célèbre : le rectangle de 6 × 10 se pave de 2 339 façons 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 retient que les petits carrés. Il faut aussi compter 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 comporte 1 296 rectangles (carrés compris), car un rectangle est déterminé par le choix de 2 lignes parmi les 9 lignes du quadrillage et de 2 colonnes parmi 9, soit 36 × 36.

Pour aller plus loin

Ces problèmes font appel à des notions précises : parité, coloration, dénombrement, graphes. Nous les détaillons, avec des exercices destinés à l'école primaire et au collège, sur la page les notions mathématiques mises en jeu 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 les défis de logique du Palais des Échecs, renouvelés régulièrement. Les lecteurs belges peuvent aussi se renseigner auprès de la FRBE-KBSB, la fédération francophone et néerlandophone des échecs en Belgique.