Emma Rahoual
Lena Pham
Échecs et maths
Introduction
Bonjour à tous et à toutes. Je m’appelle Emma. Aujourd’hui, ma collègue Lena et moi vous
soumettrons notre proposition initiale de projet. Ces dernières semaines, nous avons entrepris
une réflexion méthodique portant sur les interactions fondamentales entre les mathématiques et
les échecs. Il est évident que les deux disciplines convoquent des aptitudes intellectuelles
largement similaires. Intuition, visualisation, imagination, calcul, analyse… La liste n’est pas
exhaustive, mais le système éducatif convient naturellement de la pertinence du jeu et s’efforce
de l’introduire à ses programmes. Par exemple, au Canada, sous l’impulsion de l’association
Échecs et Maths, toutes les écoles primaires francophones du Nouveau-Brunswick ont intégré les
64 cases à leurs pratiques pédagogiques. Dans cette province, les résultats sont éloquents : en
quelques années seulement, le secteur francophone a surclassé le secteur anglophone en matière
de mathématiques. Si les grands joueurs d’échecs semblent présenter une forte disposition pour
le raisonnement logique, c’est aussi parce que leur spécialité, d’origine indienne, sert de matrice
à nombre de problèmes ludiques. Ainsi, nous formons le dessein d’examiner le plus notoire, soit
le problème des huit dames et ses déclinaisons. D’une part, nous l’étudierons en profondeur, en
accordant une attention particulière à l’algorithme facilitant sa résolution. D’autre part, nous
expliquerons le code informatique du moteur d’échecs Stockfish pour le situer par rapport aux
processus décisionnels humains. Cette dernière partie, à visée interactive, s’appuiera sur trois
positions didactiques que des volontaires seront invités à considérer au meilleur de leurs
capacités.
Problème des huit dames
Le sort des mathématiciens en Bavière étant peu enviable, Max Bezzel
aspire plutôt à devenir avocat. Bien que son métier l’accapare, il refuse de
renoncer à ses ambitions mathématico-échiquéennes. Ainsi, en 1848, sans
entrevoir immédiatement la fécondité de son idée, il publie le célèbre
problème de la pièce la plus puissante des échecs dans la revue
allemande Schachzeitung. Il recherche alors le nombre de façons de placer
huit dames sur un échiquier 8 x 8 de sorte qu’elles ne se menacent pas
mutuellement. Seul un traitement mathématique permet de déterminer
l’ensemble des solutions. La démarche que nous détaillerons sera calquée
sur celle de l’illustre mathématicien Gauss. En effet, en septembre 1850, il
tombe sur un article de Franz Nauck et relève rapidement l’erreur de son
Figure 1. Max confrère, qui ne proposait alors que 60 solutions. Quelques mois plus tard,
Friedrich William Nauck rectifie le tir et donne les 92 solutions. Dans ses correspondances,
Bezzel (1824 - Gauss fournit des « tâtonnements méthodiques » susceptibles de vérifier
1871)
ce résultat à la main. En voici un survol.
Méthode gaussienne
Avant tout, rappelons que la dame peut se déplacer d’autant de cases qu’elle le désire de manière
linéaire. Par conséquent, son mouvement peut être décrit comme l’intersection de quatre droites
sur l’échiquier : une droite verticale, une droite horizontale et deux droites diagonales (une Nord-
Est de pente 1 et l’autre Sud-Est de pente -1). Si aucune de ces droites ne peut contenir plus
d’une dame, il est possible de donner les positions potentielles selon une liste de huit chiffres
( 1, 2, 3, 4, 5, 6, 7, 8),
où Di désigne la rangée occupée par la dame placée dans la colonne i , en numérotant les rangées
de bas en haut. La suite constitue alors une permutation des nombres de 1 à 8. Toutes les
solutions du problème des huit dames sont nécessairement de cette forme, mais l’ensemble des
permutations possibles,
8!=8×7×6×5×4×3×2×1=40320,
contient une immense majorité de configurations invalides. La difficulté réside dans la gestion
des diagonales. Deux dames situées respectivement aux positions (j, ) et (k, ) appartiennent
à une même diagonale Nord-Est si elles vérifient la même équation de la forme
y=x+b
ce qui revient à exiger que les différences
Dj - j et Dk - k
soient égales. De même, deux dames sont alignées sur une diagonale Sud-Est si elles satisfont
une équation de la forme
y = −x + b
c’est-à-dire si les sommes
Dj + j et Dk + k
coïncident.
La condition nécessaire et suf sante pour qu’une permutation corresponde à une solution du
problème est donc la suivante :
𝐷
𝐷
𝐷
𝐷
𝐷
𝐷
𝐷
𝐷
fi
𝐷
𝐷
• toutes les différences - k, pour 1 ≤ k ≤ 8 doivent être distinctes ;
• toutes les sommes + k, pour 1 ≤ k ≤ 8 doivent également être distinctes.
Cette reformulation arithmétique permet de véri er systématiquement les permutations possibles
et d’éliminer immédiatement celles qui présentent des con its diagonaux.
Considérons la permutation
(6, 1, 5, 2, 8, 3, 7, 4).
Dans ce cas, l’ensemble des différences - k et celui des sommes + k ne contiennent
aucune valeur répétée. Aucune paire de dames ne partage une diagonale Nord-Est ou Sud-Est, ce
qui fait de cette con guration une solution valide.
Figure 3. Vérification des sommes et
Figure 2. Solution
des différences de la la solution
(6, 1, 5, 2, 8, 3, 7, 4)
À l’inverse, la permutation
(1, 7, 4, 6, 2, 8, 5, 3)
échoue à satisfaire ces conditions. Certaines différences apparaissent en double, indiquant la
présence de deux dames sur une même diagonale Sud-Est. Certaines sommes coïncident
également, révélant un con it sur une diagonale Nord-Est. Cette con guration ne constitue donc
pas une solution.
𝐷
fi
𝐷
fl
𝐷
fi
fl
fi
𝐷
Figure 5. Vérification des sommes et
des différences de la solution fautive
Figure 4. Solution fautive
(1, 7, 4, 6, 2, 8, 5, 3)
Les 92 solutions peuvent être regroupées en 12 solutions fondamentales (les autres s’obtenant
par rotation et symétries). Nous nous appesantirons éventuellement sur ce qui les caractérise.
Figure 6. Solutions récapitulatives
Généralisation et algorithme
Gauss était optimiste : il affirmait qu’il suffisait d’une heure ou deux pour en finir sans aide
informatique. Effectivement, il existe plusieurs astuces pour éliminer rapidement des
configurations incompatibles.
Par exemple, toute disposition débutant par
(1, 2, x, x, x, x, x, x)
est vouée à l’échec indépendamment de la position des six autres dames, car les deux premières
sont placées sur la même diagonale. On écarte donc d’emblée
6! = 720.
On place donc les dames une à une. Sur un échiquier 4 x 4, la con guration (1, 3, x, x) semble
admissible, mais conduit éventuellement à une impasse. Étant donné que les possibilités (1, 3, 2,
x) et (1, 3, 4, x) opent, il faut revenir en arrière et tenter (1, 4, x, x). Cette approche récursive
repose sur des heuristiques, c’est-à-dire des méthodes d’exploration qui réduisent le travail
inutile en disquali ant les pistes défectueuses le plus tôt possible. Toutefois, elles ne constituent
pas une preuve de complétude en soi : elles accélèrent, mais ne garantissent pas de ne rien
oublier. Grâce à l’algorithme de retour sur trace (backtracking), il est possible d’appliquer
systématiquement ces heuristiques jusqu’à obtenir l’ensemble des solutions.
Figure 7. Arbre de décision pour un échiquier 4 x 4
fl
fi
fi
Les retours sont en pointillé. Chaque noeud représente un état partiel ; chaque feuille, une
impasse ou une solution complète. On peut étendre l’algorithme du cas de quatre dames au
problème des n dames : quel est le nombre maximal de dames que l’on peut placer sur un
échiquier n x n en respectant la contrainte. Exposons ses grandes lignes.
Voici une liste des étapes logiques que nous implémenterons dans un langage de programmation.
1. Commencer avec un échiquier N × N initialisé uniquement avec des zéros, où N est le
nombre de dames et la taille de l’échiquier.
2. Définir une fonction isSafe(board, row, col) pour vérifier si une dame peut être placée à la
position board[row][col].
3. Cette fonction vérifie qu’aucune autre dame ne se trouve dans la même colonne, sur la
diagonale supérieure gauche ou sur la diagonale supérieure droite.
4. Définir une fonction solveNQueens(board, row) qui tente de placer les dames sur l’échiquier
ligne par ligne.
5. Si toutes les dames sont placées avec succès (cas de base : row = N), la fonction retourne
vrai.
6. Pour chaque colonne de la ligne courante, vérifier si la position board[row][col] est sûre à
l’aide de isSafe. Si oui, placer la dame à cette position.
7. Appeler récursivement la fonction pour placer la dame suivante (solveNQueens(board, row
+ 1)).
8. Si le placement mène à une solution, retourner vrai.
9. Sinon, retirer la dame de la position courante et essayer la colonne suivante.
10. Si aucune colonne ne permet de placer une dame sur la ligne courante, retourner faux.
11. Afficher la solution si elle existe. Sinon, indiquer qu’aucune solution n’a été trouvée.
Mentionnons que la fonction isSafe() peut être optimisée en mémorisant, à l’aide des tableaux
col[], diag1[] et diag2[], les colonnes et diagonales déjà attaquées. Cela réduit le nombre de
vérifications nécessaires à chaque tentative de placement.
Bien que nous soyons deux étudiantes en sciences de la santé, nous nous hasarderons à la
reproduction de cet algorithme, lequel sera remis avec notre document final. Ce dernier
rassemblera l’ensemble de nos recherches, calculs, analyses, etc.
Le problème toroïdal des n dames
A n de mieux comprendre le problème généralisé des dames, les
mathématiciens ont étudié des variantes modi ant la structure
même de l’échiquier. L’exemple classique est l’échiquier toroïdal,
introduit par Pólya en 1918. Il est obtenu en supprimant les
frontières : une pièce quittant l’échiquier par un côté réapparaît
du côté opposé. Le bord gauche est collé au droit ; le bord
supérieur, à l’inférieur. Il suf t de répéter mentalement
l’échiquier à l’in ni par translation horizontales et verticales.
Ainsi, pas nécessairement besoin de mettre la main sur un
beigne quadrillé pour imaginer le mouvement des pièces ! Leurs Figure 8. Échiquier toroïdal
positions sont décrites par des coordonnées (c, r) considérées
modulo n.
L’arithmétique modulaire est la branche étudiant les restes des divisions euclidiennes. Quand on
dit que deux nombres a et b sont congrus modulo n, on ne dit pas qu’ils sont égaux. On dit qu’ils
sont équivalents du point de vue des restes quand on les divise par n. Par exemple, prenons
n = 8.
Le reste de 3 ÷ 8 est 3. Les reste de 11 ÷ 8 est aussi 3. On peut écrire 11 = 1 x 8 + 3. Donc, 3 = 11
(mod 8). autrement dit, a et b doivent satisfaire l’équation
a = kn + b, où k ∈ ℤ.
On peut alors reformuler les contraintes du problème des n dames toroïdal, cette fois-ci en termes
de congruences. Leurs coordonnées devant être comparées à un multiple de n près, deux dames
situées en ( , ) et ( , ) partagent une même diagonale si et seulement si
+ = + (mod ) ou − = – (mod ).
Pólya pose finalement son théorème. Pour n ≥ 4, le problème des n dames sur un échiquier
toroïdal n × n admet une solution si et seulement si le seul diviseur commun à n et à 6 est 1, soit
que 2 et 3 ne divisent pas n.
𝑟
fi
𝑐
𝑟
𝑐
𝑟
𝑐
fi
𝑐
𝑟
𝑛
fi
𝑟
𝑐
fi
𝑟
𝑐
𝑛
La preuve, que nous ne détaillerons pas tout de suite, consiste à présupposer l’existence d’une
solution et à exploiter le fait que les colonnes, les rangées et les diagonales occupées forment des
permutations des entiers de 1 à n. On commencera donc par écrire l’identité
Stock sh
Très brièvement, puisque nous approfondirons ce sujet ultérieurement, Stock sh est un moteur
d’échecs, c’est-à-dire un programme capable de sélectionner un coup optimal à partir d’un calcul
systématique. Il représente l’échiquier à l’aide de bitboards, soit des entiers binaires de 64 bits.
Chaque bit correspond à une case. À partir de cette abstraction, le moteur génère des coups
candidats et les organise dans un arbre de recherche. Des optimisations algorithmiques, un peu
comme celle que nous avons mentionné sur isSafe(), rendent cette opération particulièrement
rapide et ef cace. Son ELO est estimé à 3600 points. Cela dépasse largement le meilleur niveau
humain, avoisinant les 2900 points.
Les trois positions suivantes ont été sélectionnées a n d’illustrer la dernière partie de notre
projet. Elles sont extraites de l’ouvrage Sicilian Grand Prix Attack de James Plaskett. Elles sont
issue d’une partie opposant Rosich à Kasparov lors d’une simultanée, en 1988. En comparant nos
propres évaluations d’amateurs à celles d’experts, puis à celles produites par Stock sh, nous
mettrons en évidence la puissance et la complexité du calcul algorithmique et des outils
mathématiques.
Figure 9. Position un Figure 10. Position deux Figure 11. Position trois
fi
fi
fi
fi
fi
Sources
Principale
[Link]
Secondaires
[Link]
[Link]
h t t p s : / / w w w . g o o g l e . c o m / s e a r c h ?
q=how+to+write+the+code+for+the+queens+problem&sca_esv=d4cfef7d5aeed196&biw=1440
&bih=812&sxsrf=ANbL-n4kBNRtSr452QgIkAXkHGua-
JJUpQ%3A1770710845749&ei=PeeKaam5LZat5NoPz82-
o A Y & v e d = 0 a h U K E w j p y 9 f 3 u 8 6 S A x W W F l k F H c -
mD2QQ4dUDCBQ&uact=5&oq=how+to+write+the+code+for+the+queens+problem&gs_lp=E
gxnd3Mtd2l6LXNlcnAiLGhvdyB0byB3cml0ZSB0aGUgY29kZSBmb3IgdGhlIHF1ZWVucyBw
cm9ibGVtSJsUULIHWO8ScAF4AZABAJgBgAGgAbEDqgEDMS4zuAEDyAEA-
AEBmAIEoALwAsICChAAGLADGNYEGEfCAgcQIxiwAhgnwgIFEAAY7wXCAggQABiAB
B i i B M I C C h A h G K A B G M M E G A q YAw C I B g G Q B g i S B w M y L j K g B -
MTsgcDMS4yuAfnAsIHBTAuMS4zyAcWgAgA&sclient=gws-wiz-serp
[Link]
[Link]
engine-7fddd1d83579