← Retour au blog

Grilles sans hasard au Démineur : quelles déductions faut-il vraiment ?

Sur notre démineur, aucune grille ne t'oblige à deviner : avant de te la proposer, un solveur vérifie qu'elle se résout par la logique seule depuis ton premier clic. Mais « par la logique » recouvre des raisonnements très différents, de l'évidence (un 1 qui touche une seule case fermée) au casse-tête. Alors, qu'est-ce qu'une grille du site te demande vraiment de savoir faire ? Nous avons posé la question au solveur lui-même, sur 15 000 grilles tirées par le vrai générateur du jeu. La réponse tient en une phrase : en Débutant, la règle simple suffit le plus souvent ; en Expert, presque jamais, et la compétence qui manque est presque toujours la même, croiser deux chiffres.

🎮 Jouer au démineur

Les quatre outils du solveur

Le solveur qui garantit les grilles raisonne par tours. À chaque tour, il regarde tous les chiffres ouverts et essaie quatre déductions, dans cet ordre, en ne passant à la suivante que si la précédente n'a rien donné nulle part sur la grille :

  1. La règle simple. Un chiffre qui a déjà toutes ses mines : ses autres voisines fermées sont sûres. Un chiffre qui a exactement autant de voisines fermées que de mines manquantes : elles sont toutes minées.
  2. L'inclusion. Toutes les cases fermées autour d'un chiffre A touchent aussi un chiffre B. La différence entre leurs mines manquantes se trouve alors dans les cases propres à B : si elle vaut zéro, ces cases sont sûres ; si elle égale leur nombre, elles sont minées.
  3. Le compte total. Si toutes les mines sont trouvées, les cases fermées restantes sont sûres ; s'il reste autant de cases fermées que de mines, elles sont toutes minées.
  4. L'énumération. Pour chaque groupe de cases fermées reliées par des chiffres (jusqu'à 22 cases), il passe en revue toutes les façons d'y placer les mines qui respectent les chiffres. Une case vide dans toutes est sûre, une case minée dans toutes est une mine.

Si aucun des quatre ne donne rien, la grille est refusée et le jeu en tire une autre. Pour notre mesure, nous avons repris le code du jeu, sans en changer la logique, et noté, à chaque tour, l'outil qui a servi. Nous avons aussi rejoué chaque grille avec un solveur bridé, privé des outils 2 à 4, puis des outils 3 et 4, puis du seul outil 4, pour voir lesquelles il finit encore.

Ce que chaque niveau exige

Premier clic au centre, 2 500 grilles par niveau, celles que le jeu sert réellement en solo :

Grilles résolues avec…DébutantIntermédiaireExpert
La règle simple seule78,4 %42,3 %1,4 %
+ l'inclusion96,3 %89,5 %49,9 %
+ le compte total97,2 %91,2 %53,0 %
Les quatre outils100 %100 %100 %
Blocages par grille (médiane)014
Grilles à 6 blocages ou plus0,1 %0,7 %22,9 %

Nous appelons blocage un tour où aucun chiffre de toute la grille ne donne quoi que ce soit à lui seul. C'est un minimum : le solveur voit toute la grille d'un coup, toi non, et tu te sentiras sans doute bloqué plus souvent que lui.

Le saut est brutal. En Débutant, plus de trois grilles sur quatre se finissent sans jamais regarder deux chiffres ensemble. En Expert, c'est 36 grilles sur 2 500 : la quasi-totalité te demandera au moins une fois de croiser des chiffres, et une grille sur deux ira au-delà de l'inclusion. Pourtant, même en Expert, la règle simple reste la bête de somme : elle a produit 94,4 % des cases déduites par le solveur. Le reste, moins de 6 %, c'est là que se jouent les parties.

Pour comparaison, sur des grilles tirées sans aucun filtre (comme dans un démineur classique), ce même solveur ne finit sans pari que 82,8 % des Débutant, 59,4 % des Intermédiaire et 8,4 % des Expert. Le filtre du site écarte les grilles où la logique ne suffit pas, il ne retient pas pour autant des grilles faciles : une grille Expert sur deux reste hors de portée de la règle simple et de l'inclusion réunies.

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.

Le chiffre qui manque presque toujours : deux chiffres qui se chevauchent

L'outil 4, l'énumération, a l'air redoutable : les groupes qu'il passe en revue font 15 cases en médiane en Expert, jusqu'à 22. Aucun humain ne fait ça de tête. Mais le solveur énumère tout le groupe parce que c'est sa méthode, pas parce que la déduction l'exige. Nous avons donc repris chacun de ces tours et cherché le plus petit groupe de chiffres voisins qui suffisait à trouver une case :

Tours où l'énumération a serviDébutantIntermédiaireExpert
Deux chiffres suffisaient85,9 %88,1 %91,6 %
Il en fallait trois8,5 %9,4 %6,3 %
Quatre ou plus5,6 %2,6 %2,1 %

(Premier clic au centre. En Débutant, l'énumération n'a servi que 71 fois sur 2 500 grilles : ce pourcentage est à prendre avec prudence.)

Comme l'inclusion avait déjà échoué à ces tours, ces paires de chiffres sont des chevauchements partiels : chacun des deux chiffres a des cases que l'autre ne voit pas. Exemple : un chiffre A attend encore 1 mine parmi trois cases x, y, z, et son voisin B en attend 2 parmi y, z, w. Les cases communes y et z ne peuvent pas porter plus d'une mine, à cause de A. Pour en avoir deux, B a donc besoin de w : w est une mine. Et puisque la mine de A est forcément en y ou en z, x est sûre. Les deux seules configurations possibles le confirment ; y et z, elles, restent à trancher plus tard. C'est le raisonnement du motif que les joueurs appellent 1-2, et c'est la soustraction de deux équations détaillée dans l'article sur la méthode du système linéaire.

Autrement dit, la boîte à outils d'un joueur Expert sur ce site tient en trois gestes : la règle simple, l'inclusion, et la soustraction de deux chiffres qui se chevauchent. Les raisonnements à trois chiffres ou plus existent, mais ils sont rares : environ un tour d'énumération sur douze en Expert. Les patterns avancés sont utiles à connaître, mais ce n'est pas eux qui te manqueront le plus souvent.

Le compteur de mines ne sert qu'à la toute fin

Le compte total est l'outil le moins utilisé : le solveur y fait appel sur 6,0 % des grilles Expert (premier clic au centre), et sur les six séries mesurées, il n'a jamais servi avant que 96 % des cases sûres soient ouvertes. Ce sont les fins de partie avec des cases enclavées, qu'aucun chiffre ouvert ne touche : quand toutes les mines sont trouvées, elles sont sûres ; quand il en reste autant que de cases fermées, ce sont toutes des mines. Le compteur 💣 au-dessus du plateau t'y aide, à condition que tes drapeaux soient justes, puisqu'il retire simplement tes drapeaux du nombre total de mines.

Le premier clic décide du moment du premier blocage

Où le premier blocage tombe-t-il dans la partie ? Nous avons mesuré l'avancement (la part des cases sûres déjà ouvertes) au moment où les règles simples ne suffisent plus pour la première fois, en partant du centre puis du coin en haut à gauche :

Expert, 2 500 grillesPremier clic au centrePremier clic dans un coin
Premier blocage (avancement médian)57 %8 %
Blocages par grille (médiane)45
Grilles à 6 blocages ou plus22,9 %42,7 %

Depuis un coin, environ 70 % des grilles Expert te bloquent avant le premier quart de la partie, contre 23 % depuis le centre. L'effet se voit à tous les niveaux : la part des grilles qui se finissent avec la seule règle simple passe de 78,4 % à 60,0 % en Débutant et de 42,3 % à 28,3 % en Intermédiaire. L'article sur le premier clic rappelle que l'ouverture est en général plus petite près d'un bord ; ici, on voit ce que ça coûte en raisonnements.

Pourquoi le solveur s'arrête à 22 cases

Décider si un démineur peut se gagner sans jamais deviner n'a rien d'une formalité. Richard Kaye a montré en 2000 que savoir si une position est seulement cohérente (s'il existe un placement de mines compatible avec les chiffres) est un problème NP-complet (« Minesweeper is NP-complete », The Mathematical Intelligencer, vol. 22). En 2024, Della Hendrickson et Andy Tockman, du MIT Hardness Group, ont étudié la question qui nous intéresse ici, savoir si le joueur peut finir la partie par une suite de clics tous prouvés sûrs, et l'ont montrée coNP-complète. Ces résultats portent sur des grilles de taille quelconque : ils disent qu'aucune méthode connue ne tranche rapidement tous les cas, pas qu'une grille Expert est insoluble en pratique.

Le solveur du site ne cherche donc pas à tout voir. Il plafonne l'énumération à 22 cases et, au-delà, il renonce simplement. Ce choix ne peut que lui faire refuser une grille jouable, jamais en accepter une qui demanderait un pari. Dans notre mesure, l'énumération est d'ailleurs allée jusqu'à ce plafond : dans cinq des six séries, la plus grande frontière qui a donné une déduction faisait 22 cases (18 dans la sixième, Débutant avec premier clic dans un coin).

Ce qu'il faut retenir

À lire aussi

← Retour au blog Jouer au démineur
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →