Les mathématiques cachées derrière le démineur
Le démineur a l'air d'un jeu simple. Et pourtant, il cache des problèmes mathématiques fascinants qui occupent les chercheurs depuis des décennies. De la théorie de la complexité au calcul de probabilités, plonge dans les mathématiques qui se cachent derrière chaque clic.
Le démineur est NP-complet
En 2000, le mathématicien Richard Kaye a démontré que le problème de la consistance du démineur est NP-complet. Qu'est-ce que cela signifie concrètement ?
Un problème NP-complet est un problème pour lequel :
- Vérifier une solution proposée est facile (temps polynomial)
- Trouver la solution depuis zéro est potentiellement extrêmement long (temps exponentiel)
Appliqué au démineur : si quelqu'un te montre où sont toutes les mines, tu peux vérifier facilement que cette configuration est compatible avec les chiffres affichés. Mais déterminer si une configuration existe (si la grille est résoluble) est un problème fondamentalement difficile.
Le démineur appartient à la même famille de difficulté que le problème du voyageur de commerce ou la satisfaisabilité booléenne. Un simple jeu Windows qui cache un des problèmes les plus profonds de l'informatique théorique !
Le calcul de probabilités au démineur
Quand la logique pure ne suffit plus (le fameux 50/50), les mathématiques prennent le relais. Calculer la probabilité qu'une case donnée contienne une mine est essentiel pour prendre la meilleure décision possible.
Et sur ce site ? Ce qui est dit ici du pari vaut pour le démineur classique, où les mines sont posées au hasard et où il faut parfois deviner. Sur notre démineur, chaque grille est vérifiée par un solveur avant de t'être proposée : elle se résout entièrement par la logique, sans jamais avoir besoin de deviner, en solo, en multijoueur comme au défi du jour. Seule la réflexion compte. Unique exception, une grille personnalisée surchargée de mines, que le jeu te signale.
Probabilité naïve vs probabilité réelle
L'approche naïve consisterait à dire : s'il reste 20 mines pour 80 cases inconnues, chaque case a 25% de chances d'être une mine. Mais c'est faux dès qu'on tient compte des contraintes locales : la densité de mines de la grille n'est qu'une moyenne.
En réalité, chaque chiffre affiché sur la grille impose une contrainte sur ses voisines. Ces contraintes créent des probabilités très inégales : certaines cases à 5%, d'autres à 80%, même si la moyenne globale est à 25%. On retrouve ce même type de raisonnement probabiliste dans d'autres jeux, comme la bataille navale et son analyse probabiliste des tirs. C'est pourquoi les bons joueurs ne devinent pas « au hasard » - ils évaluent intuitivement ces probabilités. Cela fait partie des techniques avancées du jeu.
Le calcul exact
Pour calculer la probabilité exacte qu'une case soit minée, il faut :
- Énumérer toutes les configurations valides de mines le long de la frontière
- Pour chaque configuration, calculer le nombre de manières de placer les mines restantes dans les cases intérieures (non adjacentes à la frontière)
- Compter dans combien de ces configurations la case considérée est minée
Ce calcul fait intervenir des coefficients binomiaux (combinaisons) et peut devenir très lourd. Les solveurs informatiques le font en quelques millisecondes, mais un humain ne peut qu'en faire une approximation intuitive, par exemple avec le raisonnement bayésien au démineur, qui ajuste ses estimations à chaque chiffre révélé.
La théorie des contraintes appliquée
Chaque case numérotée du démineur définit une contrainte : la somme des mines dans son voisinage égale son chiffre. L'ensemble de ces contraintes forme un système que les mathématiciens appellent un problème de satisfaction de contraintes (CSP).
Les techniques utilisées pour résoudre les CSP se retrouvent dans de nombreux domaines : planification d'emplois du temps, allocation de fréquences radio, coloration de graphes, compilation de code... Jouer au démineur, c'est résoudre un CSP à la main. La grille se prête aussi à une lecture par la théorie des graphes et des réseaux.
Propagation de contraintes
La technique de base pour résoudre un CSP est la propagation : quand tu déduis qu'une case est une mine, cette information modifie les contraintes de toutes les cases numérotées voisines. Ces nouvelles contraintes peuvent à leur tour révéler d'autres mines ou cases sûres, en cascade.
C'est exactement ce que tu fais quand tu joues : saturation → complétion → réduction → nouvelle saturation... Cette cascade de déductions est de la propagation de contraintes en action.
Les solveurs de démineur
Plusieurs algorithmes ont été développés pour résoudre automatiquement le démineur :
- Solveur par règles simples : applique saturation et complétion. Résout ~30% des situations en Expert
- Solveur par soustraction : ajoute la réduction entre contraintes voisines. Résout ~60% des situations
- Solveur par énumération : teste toutes les configurations possibles de la frontière. Résout ~90% des situations déterministes
- Solveur probabiliste : quand la logique ne suffit pas, calcule les probabilités exactes et choisit la case la plus sûre. Maximise le taux de victoire (~35% en Expert)
Un humain expert se situe généralement entre le solveur par soustraction et le solveur par énumération - avec en plus une bonne intuition probabiliste.
Les nombres de la grille : quelques statistiques
Voici des chiffres intéressants sur les grilles du démineur, calculés par simulation :
- En Expert (99 mines, 480 cases), une case aléatoire a 20,6% de chances d'être minée
- Le chiffre le plus fréquent est « 1 » (~35% des cases révélées), suivi de « 2 » (~25%)
- Les « 5 », « 6 », « 7 » et « 8 » sont extrêmement rares. Un « 8 » (toutes les voisines sont minées) est quasi impossible en mode standard
- Le premier clic révèle en moyenne 15 à 25 cases au centre d'une grille Expert
- Environ 10 à 15% des grilles Expert sont résolubles uniquement par la logique (sans aucun guess) - une question de solubilité qu'on retrouve aussi dans l'analyse probabiliste du solitaire
Le lien avec l'intelligence artificielle
Le démineur est un terrain de jeu pour les chercheurs en IA. Il combine information partielle (tu ne vois pas toutes les mines), raisonnement logique et prise de décision sous incertitude - trois défis majeurs de l'IA.
Des approches variées ont été testées : réseaux de neurones, apprentissage par renforcement, algorithmes génétiques... Mais à ce jour, les meilleurs solveurs restent les algorithmes de satisfaction de contraintes classiques, combinés au calcul probabiliste. L'IA n'a pas encore surpassé la bonne vieille logique mathématique pour ce problème.
Pourquoi tout cela compte pour toi
Comprendre les mathématiques derrière le démineur ne te rendra pas forcément meilleur du jour au lendemain. Mais cela t'aidera à :
- Comprendre pourquoi, sur un démineur classique, certaines parties sont impossibles à gagner sans chance, et pourquoi nos grilles sont filtrées par un solveur
- Faire de meilleurs choix quand un démineur classique t'oblige à deviner (choisir la case la moins probable d'être minée)
- Apprécier la profondeur insoupçonnée de ce jeu que tu pensais connaître
Si tu enseignes, découvre aussi comment utiliser le démineur pour apprendre les probabilités en classe.
Pour en savoir plus sur l'histoire fascinante du démineur, découvre notre article dédié.
