Cinq dames, toutes posées sur la même colonne, et pas une case de l’échiquier qui leur échappe. Dudeney demande d’en déplacer quatre, une par une, sans jamais laisser une seule case sans surveillance — et qu’à l’arrivée, aucune ne défende plus sa voisine. Puis il ajoute, comme en passant : « je crois que c’est l’unique solution ».
L’énoncé, publié à Londres en 1917
Traduit intégralement. Regardez la gravure avant de lire : les cinq dames sont alignées sur une seule colonne, et pourtant les soixante-quatre cases sont tenues. Vérifiez-le, c’est déjà un exercice.
Voici un casse-tête à cinq dames que j’ai donné sous un habillage fantaisiste en 1897. Comme les dames y étaient représentées par des chapeaux accrochés à soixante-quatre patères, je garderai le titre de « casse-tête des patères ». On verra que chaque case est occupée ou attaquée. Le problème consiste à déplacer une dame sur une autre case de telle sorte que chaque case soit encore occupée ou attaquée, puis à déplacer une deuxième dame dans les mêmes conditions, puis une troisième dame, et enfin une quatrième. Après le quatrième coup, chaque case doit être attaquée ou occupée, mais aucune dame ne doit alors en attaquer une autre. Bien entendu, les déplacements n’ont pas besoin d’être des « coups de dame » : vous pouvez porter une dame en n’importe quel point de l’échiquier.
Henry Ernest Dudeney, Amusements in Mathematics, 1917
Ce qu’on lit aujourd’hui
« Je crois que c’est l’unique solution. » En 1917, Dudeney n’avait aucun moyen d’en être sûr : il aurait fallu passer en revue des millions de positions à la main. On peut le faire aujourd’hui, et le recensement complet lui donne raison. Mieux : il n’y a aucun choix au premier coup — une seule dame peut bouger, vers une seule case, sans que l’échiquier cesse d’être entièrement tenu. Trois cent dix parcours de quatre déplacements gardent la couverture du début à la fin ; exactement deux se terminent par cinq dames qui ne se défendent plus.
Et ces deux-là, il les avait vues. Son corrigé donne la solution, puis ajoute que la dame du haut « aurait pu aussi bien être déplacée d’une case plus à gauche ». C’est précisément la seconde, et il n’y en a pas de troisième. Dudeney écrit « je crois » là où il ne sait pas et décrit exactement ce qu’il a trouvé : une machine lui a donné raison sur les deux points un siècle plus tard. C’est ce qui rend ses aveux d’incertitude si agréables à vérifier — ils sont toujours à l’endroit où il fallait chercher.
Ce que le problème demande vraiment
Cinq, et pas quatre. La question de fond n’est pas dans l’énoncé, elle est dessous : combien faut-il de dames pour qu’aucune case de l’échiquier n’échappe à leur contrôle ? La réponse est cinq, et c’est un minimum : aucun des 635 376 placements de quatre dames ne couvre les soixante-quatre cases — pas un seul. Dudeney part donc du plus petit effectif possible, ce qui explique que tout soit si serré : avec une dame de plus, le casse-tête se dégonflerait.
Il y a 4 860 façons de tenir l’échiquier avec cinq dames, et parmi elles 728 où aucune dame n’en défend une autre. La position de départ appartient à la grande famille, la position d’arrivée doit appartenir à la petite — et tout le problème consiste à passer de l’une à l’autre en quatre pas, sans jamais poser le pied hors des 4 860. Dit comme cela, on voit ce qui rend l’exercice difficile : ce n’est pas la destination, c’est le chemin.
La dame qu’on soulève doit être remplaçable. Voilà le raisonnement qui fait gagner du temps, et il se mène à la main : avant de choisir où poser une dame, retirez-la et regardez ce qui devient libre. Ces cases-là, sa nouvelle place devra toutes les reprendre à elle seule. Le plus souvent, elles sont éparpillées aux quatre coins de l’échiquier et aucune case unique ne peut les rattraper : le coup est éliminé sans qu’on ait rien essayé. C’est ce tri, et non la force brute, qui réduit le premier coup à une seule possibilité.
« Occupée ou attaquée » a reçu un nom, un demi-siècle plus tard. Les mathématiciens appellent cela un ensemble dominant : un groupe de cases tel que toute case du plateau soit dans le groupe ou touchée par lui. Le vocabulaire date des années 1960, mais le problème des cinq dames, lui, est posé depuis 1862 — c’est l’un des ancêtres reconnus de cette théorie, qui sert aujourd’hui à placer des antennes, des capteurs ou des casernes de pompiers. Dudeney manipule la notion sans disposer du mot ; c’est en général le meilleur moment d’une idée.
Ce que ce problème fait travailler
D’abord les lignes d’action d’une dame, et le repérage sur l’échiquier : colonne, rangée, deux diagonales. Vérifier que les soixante-quatre cases sont tenues, c’est soixante-quatre petites questions de repérage à la file — exactement ce que font les fiches La dame et ses libertés, à ceci près qu’ici les réponses doivent toutes être « oui ».
Ensuite le raisonnement d’élimination, qui est le cœur du problème : on n’essaie pas les coups, on démontre que presque tous sont impossibles, et ce qui reste est la solution. C’est la même gymnastique que devant La tour et ses libertés ou les autres séries de problèmes du site : chercher d’abord ce qui ne peut pas être.
Et enfin l’idée qu’un recensement complet est une démonstration. Six cent trente-cinq mille positions passées en revue, c’est hors de portée d’une classe, mais la question « combien y en a-t-il, au juste ? » est, elle, parfaitement à sa portée — et c’est la bonne question à poser avant de lancer quoi que ce soit.
À vous
- d’abord la mise en jambes : vérifiez que la position de la gravure tient bien les soixante-quatre cases.
- puis le casse-tête : quatre déplacements, la couverture intacte après chacun, et personne qui ne se défende à l’arrivée.
- et la vraie question, celle que Dudeney ne pose pas : pourquoi quatre dames ne peuvent-elles jamais suffire ? Le recensement le constate ; une démonstration à la main, c’est une autre affaire.
Un échiquier et cinq pièces, ou une feuille quadrillée et cinq bouchons : c’est tout ce qu’il faut. En commentaire, avec vos coups — et la solution de Dudeney viendra s’y poser, comme toujours dans cette série.
Dans la même série. Rétro Math’s reprend les 430 problèmes d’Amusements in Mathematics (1917) : l’énoncé traduit tel quel, ce qu’on en sait aujourd’hui, et la solution en commentaire. Les autres épisodes en ligne : CHINESE MONEY, CHANGING PLACES, THE STOP-WATCH, MRS. PERKINS’S QUILT, WATER, GAS, AND ELECTRICITY, THE INDUSTRIOUS BOOKWORM, SIR EDWYN DE TUDOR, THE NINE COUNTERS, THE SIX FROGS, A CENSUS PUZZLE, THE BARREL PUZZLE, A TRICK WITH DICE, CROSSING THE RIVER AXE, THE MILKMAID PUZZLE, THE TROUBLESOME EIGHT, THE FOUR POSTAGE STAMPS, A CHAIN PUZZLE, THE ROUND TABLE, THE CAB NUMBERS, THE POTATO PUZZLE, THE ECCENTRIC CHEESEMONGER, THE CLUB CLOCK, THE TWELVE MINCE-PIES, THE ARTILLERYMEN’S DILEMMA, PAPA’S PUZZLE, THE SPANISH DUNGEON.
Problème n° 315 d’Amusements in Mathematics, de Henry Ernest Dudeney (Londres, 1917). Texte et gravure sont dans le domaine public : Dudeney est mort en 1930. Le livre est intégralement disponible sur Project Gutenberg, et l’énoncé original se lit ici.