Coder un démineur en JavaScript : génération, chiffres, cascade et premier clic
Le démineur est un excellent premier vrai projet de jeu. Les règles tiennent en trois phrases, il n'y a ni physique ni animation obligatoire, et pourtant chaque étape cache un petit piège d'algorithmique : tirer des mines sans biais, ouvrir une zone vide sans faire exploser la pile d'appels, protéger le premier clic sans fausser la grille. Ce tutoriel te guide de la structure de données jusqu'à une partie jouable dans le navigateur, avec du JavaScript moderne et sans aucune bibliothèque. Chaque morceau de code est court, commenté, et tous ont été assemblés et testés ensemble avant publication : mis bout à bout, ils forment un démineur complet.
Le plan : ce qu'il faut programmer
Avant d'écrire une ligne, fais la liste des pièces. Un démineur, c'est :
- une grille de cases, chacune avec deux informations bien séparées : ce qu'elle contient (mine ou chiffre) et ce que le joueur en voit (fermée, ouverte, drapeau) ;
- un placement des mines équitable, qui n'intervient qu'au premier clic ;
- le calcul des chiffres ;
- la révélation d'une case, avec la cascade quand elle vaut 0 ;
- les drapeaux, le chord (le double clic qui ouvre les voisines d'un chiffre) et le compteur de mines ;
- la détection de la victoire et de la défaite, et un chronomètre ;
- enfin, l'affichage et la souris.
On garde la logique du jeu à l'écart du DOM : presque toutes les fonctions travaillent sur un simple objet JavaScript, ce qui permet de les tester sans navigateur et de changer d'affichage sans rien réécrire.
Représenter la grille
Le réflexe naturel est un tableau à deux dimensions, grille[ligne][col], rempli d'objets { mine, chiffre, ouverte, drapeau }. Ça marche, mais on peut faire plus simple et plus rapide : quelques tableaux plats, un par information, où la case (ligne, col) se trouve à l'indice ligne * largeur + col. Une case est alors désignée par un seul nombre, ce qui simplifie les piles, les ensembles et les comparaisons. Les Uint8Array (un octet par case, initialisé à 0) sont parfaits pour ça : une grille d'un million de cases ne pèse que quelques mégaoctets.
// États possibles d'une case, du point de vue du joueur.
const FERMEE = 0, OUVERTE = 1, DRAPEAU = 2;
// Une partie tient dans quelques tableaux plats : la case (ligne, col)
// est rangée à l'indice ligne * largeur + col.
function creerPartie(largeur, hauteur, nbMines) {
const total = largeur * hauteur;
return {
largeur, hauteur, nbMines,
mine: new Uint8Array(total), // 1 si la case cache une mine
chiffre: new Uint8Array(total), // mines voisines, de 0 à 8
etat: new Uint8Array(total), // FERMEE, OUVERTE ou DRAPEAU
minesPosees: false, // les mines arrivent au premier clic
ouvertes: 0, // cases sans mine déjà ouvertes
drapeaux: 0,
debut: null, // instant du premier clic
duree: 0,
fin: null // null, 'gagne' ou 'perdu'
};
}
Note la séparation entre mine/chiffre, la vérité de la grille, et etat, la vue du joueur. Si ton jeu a un jour un classement, cette séparation devient vitale : seule la vue du joueur devra quitter le serveur, sinon n'importe qui lirait les mines dans les outils de développement du navigateur.
Trouver les voisines
Presque tout le reste du code repose sur une seule question : quelles sont les voisines de cette case ? Il faut simplement parcourir les huit directions et écarter celles qui sortent de la grille. C'est ici que se joue la différence entre un coin (3 voisines), un bord (5) et l'intérieur (8).
// Indices des voisines d'une case : 3 dans un coin, 5 sur un bord, 8 ailleurs.
function voisines(p, i) {
const ligne = Math.floor(i / p.largeur), col = i % p.largeur;
const res = [];
for (let dl = -1; dl <= 1; dl++) {
for (let dc = -1; dc <= 1; dc++) {
if (dl === 0 && dc === 0) continue; // la case elle-même
const l = ligne + dl, c = col + dc;
if (l >= 0 && l < p.hauteur && c >= 0 && c < p.largeur) {
res.push(l * p.largeur + c);
}
}
}
return res;
}
Le test sur la ligne et la colonne est indispensable. Avec des indices plats, la case juste « à gauche » de la première colonne n'est pas hors du tableau : c'est la dernière case de la ligne du dessus. Oublier ce test donne un démineur où les mines du bord droit comptent pour le bord gauche, un bug classique et très discret. La fonction crée un petit tableau à chaque appel : négligeable en Expert, et optimisable plus tard en précalculant les voisines de chaque case.
Placer les mines sans remise
Il faut choisir n cases distinctes parmi les cases autorisées, chaque combinaison ayant la même chance de sortir. C'est un tirage sans remise, et la façon de le faire compte.
La fausse bonne idée : tirer en boucle
La première version qui vient à l'esprit consiste à tirer une case au hasard, recommencer si elle est déjà minée ou interdite, et s'arrêter quand on a posé assez de mines :
// À NE PAS FAIRE : tirer une case au hasard jusqu'à en trouver une libre.
function placerMinesNaif(p, interdites) {
let posees = 0;
while (posees < p.nbMines) {
const i = Math.floor(Math.random() * p.mine.length);
if (p.mine[i] || interdites.includes(i)) continue; // raté, on retire
p.mine[i] = 1;
posees++;
}
}
Sur une grille Débutant, elle fonctionne, et le résultat est même uniforme. Mais elle a deux défauts sérieux. D'abord, elle ne s'arrête jamais si on lui demande plus de mines qu'il n'y a de cases libres : une grille personnalisée mal réglée suffit à geler l'onglet. Ensuite, sa durée n'est pas bornée et se dégrade avec la densité. Quand il ne reste que k cases libres sur N, chaque tirage tombe sur une case libre avec la probabilité k / N, il faut donc en moyenne N / k tirages pour poser la mine suivante. Sur une grille de 480 cases où il ne reste que 10 places, c'est 48 tirages en moyenne pour une seule mine, et rien n'empêche d'en faire bien plus.
Fisher-Yates partiel : exactement n tirages
Le bon outil est le mélange de Fisher-Yates, qu'on arrête en route. On met toutes les cases autorisées dans un tableau. Pour la position 0, on tire au hasard une case parmi toutes et on l'échange avec la première ; pour la position 1, on tire parmi toutes sauf la première ; et ainsi de suite. Après n échanges, les n premières cases du tableau forment un tirage sans remise parfaitement uniforme. Inutile de mélanger le reste : on s'arrête là.
// Place p.nbMines mines sans remise, hors des cases interdites.
// hasard : une fonction qui renvoie un nombre dans [0, 1[.
function placerMines(p, interdites, hasard = Math.random) {
const exclues = new Set(interdites);
const candidates = [];
for (let i = 0; i < p.mine.length; i++) {
if (!exclues.has(i)) candidates.push(i);
}
if (p.nbMines > candidates.length) {
throw new Error('Trop de mines pour cette grille');
}
// Fisher-Yates partiel : seules les nbMines premières places sont mélangées.
for (let k = 0; k < p.nbMines; k++) {
const j = k + Math.floor(hasard() * (candidates.length - k));
const tmp = candidates[k];
candidates[k] = candidates[j];
candidates[j] = tmp;
p.mine[candidates[k]] = 1;
}
p.minesPosees = true;
}
Le coût est connu d'avance : un passage sur la grille pour construire la liste, puis exactement un tirage par mine, quelle que soit la densité. Le cas impossible est détecté au lieu de boucler. Le point délicat est la borne du tirage : j doit être pris entre k et la fin du tableau, k compris. Tirer j dans tout le tableau à chaque tour, une erreur fréquente, produit un mélange biaisé.
Une graine pour rejouer la même grille
Le paramètre hasard n'est pas là pour faire joli. Avec Math.random, chaque grille est unique et impossible à reproduire. Avec un générateur à graine, la même graine donne toujours la même grille : c'est ce qu'il te faut pour un défi du jour identique pour tous, pour rejouer une partie, ou pour écrire des tests. Voici un générateur minuscule et largement utilisé, mulberry32 :
// Petit générateur à graine (mulberry32) : même graine, même grille.
// Suffisant pour un jeu, pas pour de la cryptographie.
function generateurAGraine(graine) {
let a = graine >>> 0;
return function () {
a = (a + 0x6D2B79F5) >>> 0;
let t = a;
t = Math.imul(t ^ (t >>> 15), t | 1);
t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
Tu l'utilises ainsi : placerMines(p, interdites, generateurAGraine(20261008)). Pour un défi quotidien, une graine dérivée de la date fait l'affaire.
Calculer les chiffres
Une fois les mines posées, chaque case sans mine reçoit le nombre de mines parmi ses voisines. Comme mine contient des 0 et des 1, il suffit d'additionner :
// Le chiffre d'une case sans mine = nombre de mines parmi ses voisines.
function calculerChiffres(p) {
for (let i = 0; i < p.mine.length; i++) {
if (p.mine[i]) continue;
let n = 0;
for (const v of voisines(p, i)) n += p.mine[v];
p.chiffre[i] = n;
}
}
Une variante part de chaque mine et ajoute 1 à ses voisines : moins de travail sur une grille peu dense, même résultat. Sur le chiffre lui-même, la règle est simple : il ne peut pas dépasser le nombre de voisines, ce qui explique pourquoi les 6, 7 et 8 sont si rares.
Révéler une case et déclencher la cascade
Ouvrir une case qui affiche un chiffre, c'est juste changer son état. Ouvrir un 0, en revanche, déclenche la cascade : un 0 n'a aucune mine autour de lui, donc toutes ses voisines peuvent être ouvertes sans risque, et si l'une d'elles est aussi un 0, on recommence à partir d'elle. Le résultat est une zone vide bordée de chiffres. Côté théorie, c'est un parcours de graphe, détaillé dans l'article sur le Démineur et la théorie des graphes ; ici, on s'intéresse à la manière de le programmer.
La version récursive et son piège
La définition elle-même est récursive, et la traduction est tentante :
// Version récursive : courte, lisible... et dangereuse sur une grande grille.
function ouvrirZoneRecursive(p, i) {
if (p.etat[i] !== FERMEE) return;
p.etat[i] = OUVERTE;
p.ouvertes++;
if (p.chiffre[i] === 0) {
for (const v of voisines(p, i)) ouvrirZoneRecursive(p, v);
}
}
Elle est juste. Sur une grille Expert, elle ne posera jamais de problème : la profondeur des appels ne peut pas dépasser le nombre de cases sans mine, quelques centaines. Le piège apparaît sur les grandes grilles personnalisées. Chaque appel imbriqué occupe une place sur la pile d'appels, et cette pile a une taille limitée, fixée par le moteur JavaScript. Sur une grande zone vide, la récursion s'enfonce de voisine en voisine, presque sans jamais remonter, et la profondeur grimpe avec la taille de la zone. Nous l'avons vérifié : dans Node.js, avec les réglages par défaut, cette fonction lance RangeError: Maximum call stack size exceeded sur une grille vide de 1000×1000. Le seuil exact dépend du moteur et de la taille de chaque appel, mais ne compte pas sur une pile assez profonde pour un million d'appels imbriqués. Et un plantage au milieu de la cascade laisse la grille à moitié ouverte.
Une pile explicite, sans limite de profondeur
La solution est de gérer soi-même la liste des cases à traiter, dans un tableau ordinaire. Ce tableau vit dans la mémoire normale du programme, qui se compte en centaines de mégaoctets, et non dans la pile d'appels :
// Ouvre la case depart (sans mine) et, si c'est un 0, toute sa zone.
// Une pile explicite remplace la récursion : aucune limite de profondeur.
function ouvrirZone(p, depart) {
const pile = [depart];
while (pile.length > 0) {
const i = pile.pop();
if (p.etat[i] !== FERMEE) continue; // déjà ouverte, ou sous un drapeau
p.etat[i] = OUVERTE;
p.ouvertes++;
if (p.chiffre[i] === 0) {
for (const v of voisines(p, i)) {
if (p.etat[v] === FERMEE) pile.push(v);
}
}
}
}
Trois remarques. Une même case peut être empilée plusieurs fois par des 0 différents avant d'être traitée : le test p.etat[i] !== FERMEE à la sortie de la pile la rend inoffensive la deuxième fois. Ensuite, la cascade ne rencontre jamais de mine : elle n'avance qu'à travers des 0, dont les voisines sont toutes sûres. Enfin, une case sous un drapeau n'est pas ouverte, même si elle est sûre : c'est le comportement attendu, le drapeau protège la case de tout clic, cascade comprise.
Pile ou file ? Avec pop(), on prend la dernière case ajoutée : la zone s'ouvre en profondeur, dans un ordre un peu chaotique. Avec une file, on prend la plus ancienne : la zone s'ouvre en cercles concentriques autour du clic, ce qui donne une jolie animation de vague si tu dévoiles les cases une par une. Le résultat final est identique. Avec une file, évite shift(), qui décale tout le tableau à chaque appel : garde plutôt un index de lecture.
Protéger le premier clic
Perdre dès le premier clic n'a aucun intérêt, et un premier clic qui ouvre un simple chiffre n'est guère mieux : le joueur doit deviner à nouveau. On a deux niveaux de protection possibles. La protection minimale garantit que la case cliquée n'est pas une mine. La protection forte garantit qu'elle et ses huit voisines sont sans mine : la case cliquée vaut alors forcément 0, et le premier clic déclenche toujours une cascade. Le point de vue du joueur sur cette règle est développé dans l'article sur le premier clic au Démineur.
Côté code, la manière la plus propre est de ne pas générer la grille avant le premier clic. La partie démarre sans mines ; au premier clic, on connaît la case, donc on sait quelles cases interdire, et on tire les mines ailleurs. C'est exactement à ça que sert le paramètre interdites de placerMines.
// Premier clic : la case cliquée et ses voisines restent sans mine, ce qui
// garantit un 0, donc une ouverture. Grille trop chargée pour ça ? On ne
// protège plus que la case cliquée.
function premierClic(p, i, hasard = Math.random) {
const zone = [i, ...voisines(p, i)];
const assezDePlace = p.nbMines <= p.mine.length - zone.length;
placerMines(p, assezDePlace ? zone : [i], hasard);
calculerChiffres(p);
}
L'autre approche, générer d'abord puis déplacer la mine si le joueur clique dessus, oblige à choisir où la déplacer et à recalculer les chiffres touchés. La génération différée règle tout ça d'un coup, et reste uniforme : chaque placement qui respecte la zone protégée a la même chance de sortir. Le repli sur la seule case cliquée ne sert qu'aux grilles personnalisées très chargées.
Le clic du joueur
On a maintenant toutes les briques pour écrire l'action principale. Un clic sur une case fermée déclenche la génération si c'est le premier, démarre le chronomètre, puis ouvre la case. Si c'est une mine, la partie est perdue ; sinon on ouvre la zone et on vérifie la victoire.
// Clic gauche sur une case.
function cliquer(p, i, hasard = Math.random) {
if (p.fin || p.etat[i] !== FERMEE) return;
if (!p.minesPosees) premierClic(p, i, hasard);
if (p.debut === null) p.debut = performance.now();
if (p.mine[i]) {
p.etat[i] = OUVERTE; // la mine fatale sera affichée
terminer(p, 'perdu');
return;
}
ouvrirZone(p, i);
verifierVictoire(p);
}
La première ligne fait beaucoup pour la robustesse : un clic sur une case ouverte, sur un drapeau ou après la fin ne fait rien. Toutes les fonctions qui modifient la partie commencent par une garde de ce genre, et l'interface n'a plus à se demander si un clic est autorisé.
Drapeaux et compteur de mines
Le drapeau est une simple bascule sur une case fermée. Il ne change rien à la grille : c'est un aide-mémoire du joueur, que le jeu se contente de respecter (une case sous drapeau ne s'ouvre pas).
// Clic droit : pose ou retire un drapeau sur une case fermée.
function basculerDrapeau(p, i) {
if (p.fin || p.etat[i] === OUVERTE) return;
if (p.etat[i] === DRAPEAU) {
p.etat[i] = FERMEE;
p.drapeaux--;
} else {
p.etat[i] = DRAPEAU;
p.drapeaux++;
}
}
// Le compteur affiché : il peut devenir négatif, c'est voulu.
function minesRestantes(p) {
return p.nbMines - p.drapeaux;
}
Le compteur affiche le nombre de mines moins le nombre de drapeaux, pas le nombre de mines réellement restantes. S'il ne comptait que les drapeaux bien placés, il trahirait les faux. On autorise donc plus de drapeaux que de mines, et le compteur négatif devient un signal utile : « tu as forcément un drapeau de trop ».
Le chord, ou double clic
Le chord est le geste qui fait gagner le plus de temps aux bons joueurs. Sur un chiffre déjà ouvert, si le joueur a posé autour de lui exactement autant de drapeaux que le chiffre l'indique, toutes les autres voisines fermées sont forcément sûres : on les ouvre d'un coup. Selon les jeux, il se déclenche par un double clic, un clic des deux boutons ou un clic du milieu ; nous utiliserons le double clic.
// Chord (double clic sur un chiffre ouvert) : si le chiffre est entouré
// d'autant de drapeaux qu'il annonce de mines, on ouvre toutes ses autres
// voisines fermées. Un drapeau mal placé fait donc sauter une vraie mine.
function chord(p, i) {
if (p.fin || p.etat[i] !== OUVERTE || p.chiffre[i] === 0) return;
const autour = voisines(p, i);
const drapeaux = autour.filter(v => p.etat[v] === DRAPEAU).length;
if (drapeaux !== p.chiffre[i]) return;
for (const v of autour) {
if (p.etat[v] !== FERMEE) continue;
if (p.mine[v]) {
p.etat[v] = OUVERTE;
terminer(p, 'perdu');
return;
}
ouvrirZone(p, v);
}
verifierVictoire(p);
}
Le chord fait confiance aux drapeaux du joueur, et c'est le comportement attendu : s'il en a posé un au mauvais endroit, le chord ouvre la vraie mine voisine et la partie est perdue. Note aussi qu'il réutilise ouvrirZone : si une des voisines ouvertes est un 0, la cascade part de là, exactement comme pour un clic normal.
Victoire et défaite
La défaite est déjà gérée : elle survient dès qu'une mine est ouverte, par un clic ou par un chord. La victoire mérite plus d'attention, car il y a une mauvaise manière de la détecter : vérifier que toutes les mines portent un drapeau. Le joueur pourrait alors gagner en couvrant la grille de drapeaux, et un joueur qui ne pose jamais de drapeau, ce que font beaucoup de bons joueurs, ne pourrait jamais gagner. La bonne règle est : la partie est gagnée quand toutes les cases sans mine sont ouvertes. Grâce au compteur ouvertes tenu par ouvrirZone, c'est une simple comparaison.
// Gagné quand toutes les cases sans mine sont ouvertes. Les drapeaux
// ne comptent pas : on peut gagner sans en avoir posé un seul.
function verifierVictoire(p) {
if (p.ouvertes === p.mine.length - p.nbMines) terminer(p, 'gagne');
}
function terminer(p, resultat) {
p.fin = resultat;
p.duree = performance.now() - p.debut;
if (resultat === 'gagne') {
// Les mines encore nues reçoivent un drapeau : le compteur tombe à 0.
for (let i = 0; i < p.mine.length; i++) {
if (p.mine[i] && p.etat[i] !== DRAPEAU) {
p.etat[i] = DRAPEAU;
p.drapeaux++;
}
}
}
}
Subtilité : au moment de la victoire, aucun drapeau ne peut être faux, puisqu'une case sous drapeau n'est jamais ouverte. Un joueur qui a planté un drapeau sur une case sûre devra l'enlever et l'ouvrir pour gagner.
Le chronomètre et l'affichage des compteurs
Un piège courant consiste à incrémenter une variable « secondes » dans un setInterval d'une seconde. Les minuteries du navigateur ne sont pas ponctuelles : elles sont retardées quand le processeur est occupé, et fortement ralenties dans un onglet en arrière-plan. Le temps affiché dériverait. La bonne méthode est de mémoriser l'instant du départ et de recalculer la différence à chaque affichage.
// Temps écoulé en secondes. performance.now() est monotone : il ne saute pas
// si l'horloge de l'ordinateur est remise à l'heure en pleine partie.
function tempsEcoule(p) {
if (p.debut === null) return 0;
return (p.fin ? p.duree : performance.now() - p.debut) / 1000;
}
// Rafraîchit compteur et chronomètre quatre fois par seconde. Le temps est
// recalculé depuis l'instant de départ, jamais additionné seconde par seconde.
function demarrerAffichage(p) {
const compteur = document.getElementById('compteur');
const chrono = document.getElementById('chrono');
const minuterie = setInterval(() => {
compteur.textContent = minesRestantes(p);
chrono.textContent = Math.floor(tempsEcoule(p));
if (p.fin) clearInterval(minuterie);
}, 250);
}
Le chronomètre démarre au premier clic, pas au chargement de la page. À la fin, la durée est figée dans p.duree et la minuterie s'arrête d'elle-même. Rafraîchir quatre fois par seconde évite d'afficher un changement de seconde avec presque une seconde de retard.
Brancher l'affichage et la souris
Reste à montrer la grille. Le plus simple est une grille CSS de boutons, un par case, chacun portant son indice dans un attribut data-i. Côté HTML, il te suffit d'un conteneur <div id="plateau"> en display: grid, et de deux éléments pour le compteur et le chronomètre.
// Une case = un <button data-i="indice">. On reconstruit tout le plateau à
// chaque coup : c'est simple, et bien assez rapide pour 480 cases.
function dessiner(p, plateau) {
plateau.style.gridTemplateColumns = 'repeat(' + p.largeur + ', 1fr)';
const html = [];
for (let i = 0; i < p.mine.length; i++) {
let texte = '', classe = 'case';
if (p.etat[i] === DRAPEAU) {
texte = '🚩';
} else if (p.etat[i] === OUVERTE) {
classe += ' ouverte';
if (p.mine[i]) texte = '💣';
else if (p.chiffre[i] > 0) { texte = p.chiffre[i]; classe += ' n' + texte; }
} else if (p.fin === 'perdu' && p.mine[i]) {
texte = '💣'; // partie perdue : on dévoile les autres mines
}
html.push('<button class="' + classe + '" data-i="' + i + '">' + texte + '</button>');
}
plateau.innerHTML = html.join('');
}
Les classes n1 à n8 te laissent colorer chaque chiffre dans ta feuille de style. Pour la souris, plutôt que d'attacher trois écouteurs à chacune des cases, on en pose trois en tout sur le plateau et on lit l'indice de la case visée : c'est la délégation d'événements, qui survit sans effort à la reconstruction du plateau.
// Un seul écouteur par type d'événement, posé sur le plateau entier.
function brancherSouris(p, plateau) {
const relayer = action => e => {
if (e.type === 'contextmenu') e.preventDefault(); // pas de menu du navigateur
const i = Number(e.target.dataset.i);
if (!Number.isInteger(i)) return; // clic entre deux cases
action(p, i);
dessiner(p, plateau);
};
plateau.addEventListener('click', relayer(cliquer));
plateau.addEventListener('contextmenu', relayer(basculerDrapeau));
plateau.addEventListener('dblclick', relayer(chord));
}
Pour lancer une partie Expert : const p = creerPartie(30, 16, 99), puis dessiner(p, plateau), brancherSouris(p, plateau) et demarrerAffichage(p). Ton démineur est jouable. Un double clic envoie aussi deux événements click avant le dblclick, mais ce n'est pas gênant : un clic sur une case ouverte ne fait rien, grâce aux gardes. Ce qui manque encore, à toi de jouer : l'appui long pour poser un drapeau sur mobile, la navigation au clavier pour l'accessibilité, et un bouton pour recommencer.
Pour aller plus loin : des grilles sans devinette
Ton démineur fonctionne, mais il hérite d'un défaut du jeu classique : certaines grilles obligent à deviner. Deux cases, une mine, et aucun chiffre pour les départager. Pourquoi ces situations existent et comment les vivre côté joueur, c'est le sujet de l'article sur les grilles impossibles du Démineur. Côté programmeur, la parade la plus simple tient en une idée : générer, puis faire jouer la grille par un solveur, et recommencer tant qu'il bloque.
Le solveur joue comme un joueur prudent qui ne prend aucun risque. Il ouvre la zone du premier clic, puis applique en boucle deux règles sur chaque chiffre ouvert. Règle 1 : si le chiffre a déjà autant de mines marquées autour de lui qu'il en annonce, ses autres voisines fermées sont sûres. Règle 2 : s'il lui manque exactement autant de mines qu'il a de voisines fermées, elles sont toutes minées. Quand plus aucune règle ne s'applique, soit tout est ouvert et la grille est jouable sans deviner, soit il reste des cases et on la rejette.
// Joue la grille comme un joueur prudent qui ne connaît que deux règles.
// Renvoie true s'il ouvre toutes les cases sans mine sans jamais deviner.
function resolubleSansDeviner(p, premier) {
const essai = { ...p, etat: new Uint8Array(p.mine.length), ouvertes: 0 };
ouvrirZone(essai, premier);
let progres = true;
while (progres) {
progres = false;
for (let i = 0; i < essai.etat.length; i++) {
if (essai.etat[i] !== OUVERTE || essai.chiffre[i] === 0) continue;
const autour = voisines(essai, i);
const fermees = autour.filter(v => essai.etat[v] === FERMEE);
if (fermees.length === 0) continue;
const marquees = autour.filter(v => essai.etat[v] === DRAPEAU).length;
if (marquees === essai.chiffre[i]) {
// Règle 1 : toutes ses mines sont trouvées, le reste est sûr.
for (const v of fermees) ouvrirZone(essai, v);
progres = true;
} else if (marquees + fermees.length === essai.chiffre[i]) {
// Règle 2 : il manque autant de mines que de cases fermées.
for (const v of fermees) essai.etat[v] = DRAPEAU;
progres = true;
}
}
}
return essai.ouvertes === essai.etat.length - essai.nbMines;
}
Le solveur travaille sur une copie de l'état (essai) : la vraie partie reste intacte, toute fermée, prête pour le joueur. Il partage en revanche les tableaux mine et chiffre, qu'il ne fait que lire. Le générateur, lui, n'est qu'une boucle :
// Tire des grilles jusqu'à en trouver une que le solveur termine seul.
function genererSansDevinette(largeur, hauteur, nbMines, premier,
hasard = Math.random, maxEssais = 1000) {
for (let essai = 0; essai < maxEssais; essai++) {
const p = creerPartie(largeur, hauteur, nbMines);
premierClic(p, premier, hasard);
if (resolubleSansDeviner(p, premier)) return p;
}
return null; // rien trouvé : grille trop dense pour ce solveur
}
Comme pour les mines, cette génération a lieu au premier clic : on appelle genererSansDevinette avec la case cliquée, on remplace la partie vide par celle qu'elle renvoie, puis on joue le clic normalement. Sur nos tests, avec ces deux seules règles et un premier clic au hasard, un peu plus d'une grille tirée sur deux est acceptée en Débutant, à peu près une sur quatre en Intermédiaire, mais seulement de l'ordre d'une sur mille en Expert. En Débutant et en Intermédiaire, la boucle trouve donc en quelques essais. En Expert, avec un taux pareil, la limite de 1 000 essais est dépassée environ une fois sur trois et la fonction renvoie null : ces deux règles, trop simples, rejettent quantité de grilles qu'un bon joueur résoudrait sans deviner.
Un vrai solveur ajoute donc des raisonnements plus fins : la comparaison de deux chiffres voisins (si les cases inconnues de l'un sont incluses dans celles de l'autre, la différence des chiffres compte les mines des cases en plus, c'est le principe des patterns avancés comme le 1-2-1), puis le compteur de mines global, indispensable en fin de partie. Au-delà, on peut énumérer les répartitions de mines compatibles avec la bordure, mais le coût grimpe vite. Un solveur qui combine règles locales, comparaisons et comptage accepte une bien plus grande part des grilles, ce qui rend la génération rapide même en Expert.
Ce qu'il faut retenir
- Sépare la vérité de la grille (mines, chiffres) de la vue du joueur, et garde la logique indépendante du DOM.
- Place les mines par Fisher-Yates partiel : un tirage par mine, uniforme, sans boucle infinie possible.
- Pour la cascade, remplace la récursion par une pile ou une file explicite : une grande zone vide fait déborder la pile d'appels, pas un tableau.
- Génère la grille au premier clic, en interdisant la case cliquée et ses voisines.
- La victoire, c'est toutes les cases sans mine ouvertes, jamais tous les drapeaux posés.
- Le chronomètre se calcule depuis l'instant de départ, il ne s'additionne pas.
- Pour des grilles sans devinette, fais jouer chaque grille par un solveur et rejette celles où il bloque.
Une fois ton démineur terminé, compare-le à celui du site : la sensation d'une bonne cascade et la réactivité du chord se jouent à quelques détails près.