← Retour au blog

Résoudre le Démineur par les équations : la méthode du système linéaire

Quand tu compares un 1 et un 2 voisins pour en tirer une case sûre, tu fais déjà de l'algèbre sans le dire : tu soustrais une équation à une autre. Cet article pousse l'idée jusqu'au bout. Chaque chiffre ouvert devient une équation, chaque case fermée une inconnue, et toute une portion de frontière se transforme en système, du même genre que ceux qu'on résout au lycée. Avec une particularité qui change tout : ici, les inconnues ne peuvent valoir que 0 ou 1. Tu vas voir comment écrire ce système, comment l'éliminer, pourquoi cette particularité fait sortir des cases que l'œil ne voit pas, comment le compteur de mines s'ajoute au système, et surtout où la méthode s'arrête.

🎮 Jouer au démineur

Une case fermée, une inconnue ; un chiffre, une équation

Commence par donner un nom à chaque case fermée qui touche au moins un chiffre ouvert : a, b, c… Chaque nom désigne une inconnue qui vaut 1 si la case cache une mine, 0 sinon. Un chiffre dit alors exactement une chose : la somme des inconnues qui l'entourent vaut ce chiffre. Les cases déjà ouvertes autour de lui comptent pour 0, et les drapeaux déjà posés comptent pour 1, qu'on passe de l'autre côté du signe égal. Un 3 qui touche un drapeau et quatre cases fermées c, d, e, f s'écrit donc c + d + e + f = 3 − 1 = 2.

Voici une position bloquée, dans le coin inférieur gauche d'une grille. Toutes les déductions évidentes ont été faites (les trois drapeaux sont sûrs), et il reste huit cases fermées au contact des chiffres :

Huit inconnues, de a à h. Les chiffres du bas ne touchent plus aucune case fermée : ils sont déjà satisfaits.

Quatre chiffres touchent encore des cases fermées. On les lit un par un :

Quatre équations pour huit inconnues. En cours de maths, on s'arrêterait là : un tel système a une infinité de solutions, on ne peut rien en tirer de précis. Au Démineur, c'est le point de départ. D'abord parce qu'on cherche rarement à tout résoudre : une seule case sûre suffit à relancer la partie. Ensuite parce que nos inconnues ne prennent que deux valeurs, et c'est une information énorme que le système ne contient pas encore.

Éliminer : la soustraction de lignes, c'est déjà Gauss

La méthode du pivot de Gauss consiste à combiner les équations entre elles (les additionner, les soustraire, les multiplier par un nombre) pour faire disparaître des inconnues. Au Démineur, l'opération qui sert presque toujours est la soustraction de deux chiffres voisins, parce qu'ils partagent des cases et que ces cases partagées s'annulent.

Premier essai, (1) − (2) : b et c s'annulent, il reste a − d = 0. Autrement dit, a et d sont dans le même état : soit les deux sont des mines, soit aucune. Ce n'est pas une case trouvée, mais c'est un lien, et un lien se note.

Deuxième essai, (3) − (2) : c et d s'annulent, il reste e + f + g − b = 2. Cette nouvelle ligne partage encore f et g avec l'équation (4). On continue donc : on retranche (4), et f et g disparaissent à leur tour :

Trois équations combinées, et il ne reste plus que trois inconnues. Sur un système ordinaire, cette ligne ne dirait toujours rien : elle a une infinité de solutions. C'est maintenant que le 0 ou 1 entre en jeu.

Le vrai atout : des inconnues qui valent 0 ou 1

Regarde la ligne e − b − h = 1 et demande-toi quelle est la plus grande valeur qu'elle puisse atteindre. Pour la rendre maximale, il faut mettre à 1 les inconnues précédées d'un plus (e) et à 0 celles précédées d'un moins (b et h). Le maximum vaut donc 1. Or la ligne vaut justement 1 : elle est à son maximum, et la seule façon d'y être est ce choix-là. Conclusion : e est une mine, b et h sont sûres.

C'est la règle des bornes, et elle vaut pour n'importe quelle ligne :

Exemple d'école : a + b − c = 2. Le maximum vaut 1 + 1 = 2, atteint seulement si a = b = 1 et c = 0. La ligne a − d = 0 de tout à l'heure, elle, a pour minimum −1 et pour maximum 1 : le 0 est au milieu, d'où un simple lien et pas de conclusion. Les deux lignes ont la même forme, c'est le second membre qui fait toute la différence.

Pour s'assurer que l'algèbre ne s'est pas trompée, on peut faire la vérification brute : sur les 256 façons de remplir les huit cases a à h, exactement 4 respectent les quatre chiffres, et dans les 4, e est une mine, b et h sont libres. Les autres cases varient d'une configuration à l'autre : a et d sont liées, comme prévu, et f et g se partagent une mine. Pour les trancher, il faudra ouvrir b et h et lire les nouveaux chiffres.

Quand les coefficients grandissent

En additionnant des lignes, tu obtiens parfois des coefficients 2 ou 3. La règle des bornes reste valable, et elle s'affine : si le coefficient d'une case dépasse l'écart entre le maximum et le second membre, cette case est forcée. Prends a + b + 2c = 3. Le maximum vaut 4, l'écart vaut 1. Si c était libre, la ligne plafonnerait à 2, trop peu : c est une mine, et il reste a + b = 1. Ce raisonnement-là, contrairement au précédent, s'appuie sur le fait que les cases ne contiennent jamais une fraction de mine. On y reviendra, c'est exactement là que se cache la limite de la méthode.

Ce que l'algèbre ajoute à la règle des sous-ensembles

La règle des sous-ensembles, c'est le cas le plus simple de soustraction : quand toutes les cases d'un chiffre font aussi partie d'un autre, la différence porte uniquement sur les cases en trop, avec des coefficients tous positifs. Un 1 dont les deux cases sont incluses dans les trois cases d'un 2 voisin te dit que la troisième case du 2 est une mine. La soustraction avec les bornes va un cran plus loin et gère les chevauchements partiels (le célèbre 1-2 en est l'exemple type). Ces deux réflexes sont détaillés dans les patterns avancés du Démineur.

Dans notre position, ni l'un ni l'autre ne suffit. Aucune des quatre équations n'est incluse dans une autre, et nous avons vérifié les six paires possibles, en somme comme en différence : aucune ne donne de ligne à son minimum ou à son maximum. Il a fallu trois équations, (3) − (2) − (4), pour faire apparaître e, b et h. C'est le vrai apport du point de vue algébrique : il te pousse à continuer d'éliminer tant qu'une ligne obtenue partage encore des cases avec une autre, là où l'œil s'arrête naturellement aux chiffres qui se touchent deux par deux.

Le compteur de mines : une équation de plus

Le compteur au-dessus du plateau est lui aussi une équation : la somme de toutes les cases fermées non marquées vaut le nombre de mines restantes. En début et en milieu de partie, elle porte sur des dizaines de cases fermées, son second membre reste loin de ses bornes et elle ne force rien. En fin de partie, quand il ne reste qu'une poignée de cases, elle devient décisive.

Fin de partie : tout le reste de la grille est ouvert, toutes les autres mines portent un drapeau.

Le 4 touche trois drapeaux, a et b : a + b = 1. Le 2 de droite touche un drapeau, b et c : b + c = 1. Avec ces deux équations seules, a et c sont dans le même état, et deux configurations restent possibles : une mine en b, ou deux mines en a et c. Les chiffres ne peuvent pas trancher.

Le compteur, lui, le peut. S'il affiche 1, on ajoute l'équation a + b + c = 1. On lui retranche a + b = 1, il reste c = 0 ; puis b + c = 1 donne b = 1, et a + b = 1 donne a = 0. La mine est en b. S'il affichait 2, le même calcul donnerait l'autre configuration, a et c minées. Les deux cas sont tranchés, sans le moindre pari. Le compteur s'ajoute au système comme n'importe quelle autre ligne, et c'est la seule ligne qui touche aussi les cases éloignées de tout chiffre.

Ce que l'algèbre ne trouve pas : la position des demi-mines

Jusqu'ici, combiner des lignes et regarder leurs bornes a tout résolu. Ce n'est pas toujours le cas. Voici une position dans le coin supérieur gauche d'une grille, où quatre cases fermées sont prises dans un nœud de chiffres :

Trois chiffres, quatre cases fermées. Chaque chiffre voit d et deux des trois autres.

Le 1 du coin voit a, b et d. Le 3 du haut voit b, c, d et deux drapeaux. Le 3 du milieu voit a, c, d et deux drapeaux. Le système est d'une symétrie parfaite :

Les différences deux à deux donnent a = c, a = b, b = c : des liens, aucune case. La somme des trois donne 2a + 2b + 2c + 3d = 3, dont le maximum vaut 9 et le minimum 0 : rien. Et pourtant la position a une solution unique. Raisonne par l'absurde : si d était libre, il resterait a + b = 1, b + c = 1 et a + c = 1. En additionnant, 2 × (a + b + c) = 3. Un nombre pair qui vaut 3, c'est impossible. Donc d est une mine, et a, b, c sont sûres. L'énumération des 16 façons de remplir les quatre cases le confirme : une seule respecte les trois chiffres.

Pourquoi l'algèbre échoue-t-elle ? Essaie a = b = c = ½ et d = 0 : chaque équation vaut ½ + ½ + 0 = 1. Cette « solution à demi-mines » satisfait tout le système. Or combiner des lignes et comparer le résultat à ses bornes, c'est raisonner comme si les inconnues pouvaient prendre n'importe quelle valeur entre 0 et 1 : toute conclusion obtenue ainsi devrait aussi être vraie pour la solution à demi-mines, dans laquelle d n'est pas une mine. Aucune combinaison, si astucieuse soit-elle, ne peut donc conclure que d est une mine avec la seule règle du minimum et du maximum.

Ce qui manque, c'est le fait que les mines sont des objets entiers. L'argument « un nombre pair ne vaut pas 3 » l'utilise, tout comme l'affinage des coefficients vu plus haut : appliqué à une combinaison bien choisie des trois lignes, cet affinage vient d'ailleurs lui aussi à bout de la position. C'est le même ressort que l'analyse de parité présentée dans les patterns avancés. Quand une portion de frontière résiste à toutes les éliminations, demande-toi s'il existe une solution « à moitié » : si oui, c'est le moment de passer à l'hypothèse ou à la parité.

La technique du tank, l'arme qui voit tout

La technique du tank consiste à énumérer toutes les configurations de mines compatibles avec les chiffres, puis à garder ce qui est commun à toutes. Elle trouve tout ce qui peut se déduire des chiffres visibles : si une case est sûre dans toutes les configurations valides, le tank la voit, demi-mines ou pas. Son défaut est son coût. Avec n cases, il y a 2n configurations à passer en revue : 16 pour quatre cases, 256 pour huit, plus d'un million pour vingt. Sur papier, on ne l'applique qu'à de petits morceaux de frontière, en élaguant dès qu'un chiffre est dépassé.

L'algèbre est l'inverse : elle passe à l'échelle (éliminer dix ou vingt équations reste un travail régulier, que les programmes font sans effort) mais elle ne voit pas tout. Les deux se complètent bien. Les éliminations font le gros du travail et réduisent le problème ; il ne reste ensuite que quelques cases à énumérer à la main, sur lesquelles le tank devient raisonnable.

Reste un dernier cas : celui où même le tank laisse des cases indécidées, parce que plusieurs configurations respectent réellement tous les chiffres et le compteur. Au démineur classique, il faut alors parier, et le seul choix raisonnable est de miser sur la case la moins risquée, ce que détaille l'article sur le démineur probabiliste.

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.

Qui trouve quoi : le tableau récapitulatif

MéthodeCe qu'elle trouveCe qu'elle rateEffort
Sous-ensemblesUn chiffre dont les cases sont toutes incluses dans celles d'un autreLes chevauchements partielsImmédiat, à l'œil
Soustraction de deux chiffres et bornesLes chevauchements partiels, type 1-2Ce qui demande trois lignes ou plusFaible
Système complet et bornesTout ce qu'une combinaison de lignes fait apparaîtreCe qui exige des mines entières (parité, demi-mines)Moyen, régulier
Tank (énumération)Tout ce que les chiffres permettent de déduireRien, mais le coût explose avec le nombre de casesFort au-delà de quelques cases

Le compteur de mines s'ajoute à chacune de ces méthodes comme une ligne supplémentaire, utile surtout en fin de partie. Et derrière ce tableau se cache une raison de fond : décider en toute généralité si une position du Démineur est cohérente est un problème réputé très difficile pour les ordinateurs eux-mêmes, comme l'explique l'article sur le Démineur vu comme un réseau. Aucune méthode rapide ne peut tout voir sur toutes les grilles ; on combine donc des méthodes rapides et incomplètes avec une méthode complète et lente.

La méthode sur papier, ou de tête

Inutile d'écrire un système de trente équations. La méthode est faite pour les blocages : une zone où plus rien ne se lit à vue. Voici l'ordre qui marche le mieux.

  1. Isole un morceau de frontière de cinq à dix cases fermées, là où tu es bloqué. Ne prends pas toute la grille.
  2. Nomme les cases dans l'ordre de la frontière : a, b, c… Des noms qui se suivent rendent les équations voisines faciles à repérer.
  3. Écris une équation par chiffre : le chiffre, moins ses drapeaux, égale la somme de ses cases fermées. Oublie les chiffres qui ne touchent plus rien.
  4. Soustrais les chiffres voisins deux à deux, et après chaque ligne obtenue, calcule son minimum et son maximum. Un second membre égal à l'une des bornes, et tu as une ou plusieurs cases.
  5. Ne t'arrête pas aux paires : si une ligne obtenue partage encore des cases avec une troisième équation, combine encore. C'est le (3) − (2) − (4) de notre premier exemple.
  6. Note les liens du type a = d ou a + c = 1 : ils permettent de remplacer une inconnue par une autre et de raccourcir le système.
  7. Remplace chaque case trouvée dans toutes les équations. Elles raccourcissent, et une équation qui ne disait rien peut d'un coup tomber sur une borne.
  8. En fin de partie, ajoute le compteur comme une équation sur toutes les cases fermées.
  9. Si plus rien ne sort, cherche une solution à demi-mines. S'il en existe une, passe à l'hypothèse sur la case la plus partagée, ou à un argument de parité.

De tête, la méthode se pratique sans écrire de signes égal. On pense en termes d'écarts : « le 3 a deux mines de plus que le 1, réparties sur e, f, g ; le 2 en met une sur f, g, h ». Avec un peu d'habitude, la combinaison de trois chiffres devient un réflexe, au même titre que le 1-2. Et si tu t'entraînes sur papier, prends des positions réelles de tes parties, une grille Expert en fournit à chaque blocage.

Ce qu'il faut retenir

La prochaine fois que tu bloques sur une frontière tordue, sors un bout de papier, nomme les cases et écris les chiffres. Tu seras surpris de voir combien de « 50/50 » apparents tombent en trois lignes de soustraction.

À 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 →