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

Ces casse-têtes se jouent avec les pièces ou le quadrillage de l'échiquier, mais ils n'ont rien à voir avec une partie : ce sont de vrais problèmes de mathématiques, accessibles dès le collège, et dont certains ont occupé de grands noms de la discipline. Ils sont parfaits pour un club de maths, un exposé ou un sujet de grand oral.

Tableau récapitulatif

Le problème des huit dames

Problème des huit dames

Placer huit dames sur un échiquier de 8 × 8 de façon qu'aucune ne puisse en prendre une autre : jamais deux dames sur la même ligne, la même colonne ou la même diagonale.

Le problème a été publié en 1848 par Max Bezzel, un compositeur de problèmes d'échecs. Franz Nauck en a publié les premières solutions en 1850 et l'a généralisé à n dames sur un échiquier de n × n cases. Carl Friedrich Gauss compte parmi les mathématiciens qui s'y sont intéressés.

But du problème : trouver une disposition, puis toutes. Il en existe 92. Beaucoup se déduisent les unes des autres par rotation ou symétrie de l'échiquier ; si on les regroupe, il reste 12 solutions fondamentales. En voici une, avec les dames en d8, g7, c6, h5, b4, e3, a2 et f1 :

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

Comment le résoudre ?

La méthode classique est le retour sur trace (en anglais backtracking) : on place une dame dans la première colonne, puis une dame dans la deuxième colonne sur une case non attaquée, et ainsi de suite ; quand aucune case n'est possible, on revient en arrière et on déplace la dame précédente. C'est un exercice très apprécié en cours d'informatique au lycée. La version à n dames a 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 coups de cavalier qui passe une fois et une seule par chacune des 64 cases. Le parcours est dit fermé si la dernière case est à un saut de cavalier de la première, ce qui permet de recommencer la boucle.

Le problème est très 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 », 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 proposé une règle simple pour trouver un parcours : aller toujours vers la case d'où le cavalier aura le moins de sorties possibles.

Il existe un nombre gigantesque de parcours fermés sur l'échiquier ordinaire : 26 534 728 821 064 en comptant le sens de parcours, soit la moitié, 13 267 364 410 532, si l'on considère qu'un parcours et son inverse sont le même.

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

Pour s'entraîner, on peut commencer plus petit. Voici un parcours ouvert qui visite les 25 cases d'un échiquier de 5 × 5 : suivez les nombres de 1 à 25, chaque nombre est à un saut de cavalier du précédent.

Ce parcours a été obtenu avec la règle de Warnsdorff, et chaque saut a été vérifié. Défi : en trouver un autre qui commence au centre.

Le problème du cavalier au grand oral

Le 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 passant par tous les sommets, algorithme de retour sur trace, règle de Warnsdorff et son efficacité. On peut aussi expliquer pourquoi aucun parcours fermé n'existe sur un échiquier de 5 × 5 : le cavalier change de couleur à chaque saut, donc une boucle a forcément un nombre pair de cases, or 25 est impair.

L'échiquier mutilé

Le philosophe Max Black a posé le problème en 1946 dans son livre Critical Thinking. On retire deux coins opposés d'un échiquier (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 couvre forcément 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 avoir besoin d'essayer une seule 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 possible, quelles que soient les deux cases retirées.

Polyominos et pentominos

Un polyomino est une forme faite de carrés identiques collés par leurs côtés ; le domino en a deux, le pentomino cinq. Le mathématicien Solomon Golomb a introduit et étudié ces formes à partir de 1953. Il existe 12 pentominos différents (en considérant qu'une pièce retournée ou tournée reste la même), qui couvrent ensemble 60 cases.

Or un échiquier compte 64 cases, soit 60 + 4 : on peut donc chercher à poser les 12 pentominos sur l'échiquier en laissant libre un carré de 2 × 2 au centre. En 1958, Dana Scott a fait résoudre ce problème par un ordinateur, l'un des premiers usages de la méthode de retour sur trace : il existe 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 échiquier ?

La réponse « 64 » est fausse, ou plutôt incomplète : elle ne compte 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 est la somme des carrés des entiers de 1 à 8 : 1 + 4 + 9 + … + 64 = 204. Pour aller plus loin : un échiquier contient 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 continuer

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 mobilisées sur l'échiquier. Pour d'autres très grands nombres, voir l'échiquier de Sissa. Et pour ceux qui aiment les énigmes, le blog du Palais des Échecs propose les défis de logique du Palais des Échecs, renouvelés régulièrement.