Un démineur où deviner n'est jamais nécessaire

Nous avons passé une journée à supprimer le hasard d'un démineur. L'algorithme final tient en trois cents lignes et se raconte en deux paragraphes. La mesure, elle, a démenti trois de nos certitudes en chemin, et c'est cette partie de l'histoire qui sert au-delà d'un jeu.

Vingt minutes d'attention, puis un tirage au sort

Tout joueur régulier connaît la situation. En fin de partie, il reste deux cases masquées, une mine et une case sûre, et rien dans la grille ne permet de choisir. Une partie menée proprement pendant vingt minutes se termine à la pièce. Ce n'est pas une difficulté, c'est une loterie posée au pire moment, et aucun talent n'y change quoi que ce soit.

Le défaut vient de la façon de fabriquer la grille. Les mines sont tirées au hasard, une fois pour toutes, et personne ne vérifie que la partie qui en découle reste jouable par le raisonnement. Notre démonstrateur en ligne posait déjà les mines après le premier clic, en épargnant la case jouée et ses huit voisines, ce qui évite de perdre au premier coup. Le reste de la partie, lui, restait livré au tirage.

Tirer, vérifier, recommencer

Le principe retenu tient en une phrase. Les mines ne sont plus seulement tirées, elles sont vérifiées : un solveur qui ne sait que déduire rejoue la partie depuis le premier coup, et le tirage est jeté dès qu'une devinette devient nécessaire. On recommence jusqu'à obtenir une grille qui se termine par déduction seule. Le cinquante-cinquante disparaît donc parce qu'une grille qui en contient un n'est jamais servie, pas parce qu'on le corrige au moment où il apparaît.

Cette méthode s'appelle la génération par rejet, et sa partie intéressante n'est pas le tirage. Tirer une grille au hasard demande dix lignes. Décider qu'on la garde suppose de savoir résoudre, et décider qu'on la jette suppose de savoir démontrer qu'il n'y a plus rien à déduire, ce qui est un problème d'une autre nature.

Le niveau qui ne sert presque jamais, et qu'on ne peut pas retirer

Le solveur travaille à trois niveaux, du moins coûteux au plus coûteux. Les règles locales d'abord : un chiffre dont toutes les mines sont déjà connues libère ses voisines masquées, un chiffre dont le compte manquant égale le nombre de voisines masquées les marque toutes. La soustraction ensuite, quand les cases vues par un chiffre sont toutes comprises dans celles vues par un autre : la différence porte alors un nombre de mines connu, ce qui suffit souvent à trancher. L'énumération enfin, qui parcourt toutes les répartitions de mines compatibles avec la frontière ouverte et retient les cases qui portent une mine dans toutes, ou dans aucune.

Nous avons mesuré l'usage réel de ces trois niveaux en jouant 600 parties entièrement à l'indice, sur les cinq formes de grille du démonstrateur. Sur 42 915 coups donnés, 41 579 viennent des règles locales, 1 256 de la soustraction, et 80 de l'énumération. Le troisième niveau tranche donc deux à trois fois sur mille, et il représente à lui seul la moitié du code du solveur.

Le retirer serait pourtant une erreur, et pour une raison qui n'a rien à voir avec ces 80 coups. Un moteur qui sait seulement trouver ne peut pas décider un rejet : tant qu'il n'a rien trouvé, il ne sait pas s'il n'y a rien à trouver ou s'il n'a pas assez cherché. L'énumération est le seul niveau capable de répondre à cette question, donc le seul qui autorise à jeter une grille. Sans elle, le générateur rejetterait des grilles parfaitement loyales, et surtout il n'aurait aucun titre à garantir les autres.

La démonstration, à manipuler

Le mécanisme décrit ici tourne en production sur notre page de démineur, et il se vérifie mieux en jouant qu'en lisant. Jouez normalement, et quand une position vous bloque, utilisez le bouton Indice sous la grille. Il désigne une case dont la valeur est certaine, sans l'ouvrir, et il nomme la règle qui la donne. C'est la garantie rendue visible : à tout moment d'une partie, il existe une déduction, et le jeu vous dit laquelle.

Ce que la mesure a démenti

Avant d'écrire une ligne, nous avons construit un prototype pour mesurer le coût de cette génération. Les chiffres ci-dessous viennent du code réellement en ligne, relevés dans Firefox sur un poste de bureau le 29 juillet 2026, mille générations par forme de grille.

Notre première certitude était qu'il faudrait sortir la génération du gestionnaire de clic, la faire tourner en tâche de fond et montrer une attente au joueur. Un dixième de milliseconde plus tard, cette journée de travail n'avait plus lieu d'être. Un raisonnement juste sur le mécanisme, une génération qui recommence peut coûter cher, était faux sur l'effet réel aux densités que nous servons.

La deuxième certitude portait sur la mesure elle-même. Notre premier relevé chronométrait chaque génération et rendait des zéros. Firefox et Safari arrondissent l'horloge à la milliseconde pour empêcher le pistage par mesure de temps, donc tout ce qui passe sous ce seuil disparaît. Le harnais corrigé chronomètre le lot entier et en déduit le coût unitaire, et il relève surtout le nombre de tirages, qui est un entier exact et ne dépend pas de l'appareil : quatre à onze au maximum selon la forme, la même valeur dans le navigateur et en ligne de commande.

La troisième nous a coûté deux avertissements inutiles sur l'habillage. Nous avions annoncé un problème de contraste sur deux fonds opposés et un conflit de priorité entre règles CSS. Aucun des deux n'existait, et la lecture du fichier concerné, cinq minutes, l'aurait montré avant l'annonce. C'est la même leçon que la première, appliquée à un détail : lire le mécanisme ne remplace pas vérifier son effet.

Le même moteur, hors du jeu

Un démineur est un moteur de règles avec un habillage, et c'est ce qui en fait une bonne démonstration : la logique est visible à l'écran. Les applications que nous développons posent la même question sous d'autres noms. Un moteur d'éligibilité doit dire si un dossier passe, un moteur de tarification doit produire un prix pour une configuration donnée, un contrôle de conformité doit établir qu'un lot de documents tient debout. Dans les trois cas, trouver la règle applicable est la partie facile.

La partie qui a de la valeur est la même que dans notre solveur. Que fait le moteur quand aucune règle ne s'applique ? Un système qui ne sait pas répondre à cette question retombe sur une valeur par défaut, silencieusement, et c'est ainsi qu'un devis sort à un prix que personne n'a décidé, ou qu'un dossier passe parce qu'aucun contrôle ne l'a explicitement refusé. Un moteur qui sait démontrer l'absence de règle applicable refuse, et il dit pourquoi.

Le bouton Indice est exactement cette capacité, sous une forme ludique. Il ne se contente pas de désigner une case, il nomme la règle qui la prouve. C'est ce qu'un contrôleur réclame en audit, et ce qu'un utilisateur attend quand le système vient de lui dire non. Notre approche du développement sur mesure tient largement à cet écart, entre un outil qui produit un résultat et un outil qui produit un résultat justifiable. Le configurateur de studio de jardin répond au même besoin dans le bâtiment, et les autres démonstrateurs sont regroupés dans la section jeux.

Ce que la garantie ne dit pas

Aucune position n'oblige à deviner, ce qui ne signifie pas qu'on ne peut plus perdre. Ouvrir une case dont rien ne prouvait qu'elle était sûre reste perdant, et un drapeau mal placé suivi d'un clic sur un chiffre l'est aussi. La garantie porte sur l'existence d'une déduction, pas sur le fait que le joueur la trouve.

Le solveur ignore volontairement le compteur de mines restantes, alors qu'il pourrait s'en servir pour accepter davantage de grilles. Avec le compteur, la garantie ne vaudrait que pour un joueur qui compte, et il faudrait l'écrire en note de bas de page. Nous avons préféré perdre une dizaine de points de grilles acceptées au niveau difficile et pouvoir écrire la phrase sans réserve.

Enfin, la recherche est bornée par un budget de 250 millisecondes. Au-delà, la partie se joue sur une grille ordinaire et la page l'affiche, sous la grille. Ce repli ne s'est produit sur aucune des cinq mille grilles de notre campagne de mesure, et il reste dans le code pour le jour où un niveau plus dense sera ajouté. Les durées citées ici valent pour un poste de bureau, nous n'avons pas relevé de mesure sur téléphone et nous n'en publions donc pas.

Questions fréquentes

Comment garantir qu'une grille de démineur ne demande aucune devinette ?

En tirant la grille puis en la vérifiant. Un solveur qui ne fait que déduire rejoue la partie depuis le premier coup, et le tirage est jeté dès qu'une devinette devient nécessaire. La partie coûteuse est la vérification, pas le tirage, parce que décider un rejet suppose de démontrer qu'aucune déduction n'existe.

La génération par rejet est-elle assez rapide pour un navigateur ?

Sur les densités de ce démonstrateur, une à deux grilles suffisent et la génération demande de l'ordre du dixième de milliseconde sur un poste de bureau. Le coût monte avec la proportion de mines, donc un budget en temps borne la recherche et rend le pire cas prévisible, ce qui vaut mieux qu'un nombre de tentatives fixé au hasard.

À quoi sert ce type de moteur en dehors d'un jeu ?

Aux décisions qui doivent être justifiées : éligibilité, tarification, conformité. Un moteur qui trouve la règle applicable rend un résultat, un moteur qui sait aussi démontrer qu'aucune règle ne s'applique peut refuser en expliquant pourquoi, et c'est cette seconde capacité qui évite les valeurs par défaut silencieuses.