Le Démineur est connu comme le petit jeu livré avec l’ordinateur, mais il a aussi fait parler de lui dans la recherche en mathématiques et en informatique. Le mot clé est « NP-complet ».
Le Démineur est NP-complet
Vers l’an 2000, le mathématicien Richard Kaye aurait montré que le problème suivant, lié au Démineur, fait partie de la famille des problèmes difficiles dits « NP-complets ».
Étant donné une grille de chiffres, existe-t-il au moins une disposition de mines qui ne contredise aucun de ces chiffres ?
La question que l’on se pose en jouant, « cette case est-elle sûre ? », est étroitement liée à ce problème.
Qu’est-ce que NP-complet ?
Pour faire simple, un problème NP-complet a les propriétés suivantes.
- Vérifier une réponse est facile : si l’on vous montre une disposition de mines, vous voyez tout de suite si elle est compatible avec tous les chiffres.
- Trouver une réponse est difficile (on le pense) : quand la grille grandit, le nombre de dispositions possibles explose. Parmi les méthodes connues, aucune ne trouve vite la réponse pour n’importe quelle grille.
On sait aussi que les problèmes NP-complets se ramènent les uns aux autres. Si l’on trouvait pour un seul d’entre eux une méthode rapide dans tous les cas, tous les autres NP-complets deviendraient rapides aussi. Savoir s’il existe une telle méthode, c’est la célèbre conjecture « P ≠ NP », un problème non résolu qui fait partie de ceux dotés d’un prix d’un million de dollars.
Le nombre de dispositions grandit vite
Examiner les dispositions est lourd parce que le nombre de candidats devient énorme.
- Placer 8 mines dans une grille 9×7, c’est choisir 8 cases parmi 63, soit environ 3,9 milliards de façons.
- Placer 75 mines dans une grille 26×15, c’est choisir 75 cases parmi 390, un nombre de plus de 80 chiffres.
Bien sûr, en jouant, il n’est pas nécessaire de tout examiner. Les cases qui ne touchent aucun chiffre se traitent ensemble, et dans beaucoup de situations, un ou deux chiffres suffisent. Pourtant, quand les chiffres s’entremêlent, il peut devenir difficile de conclure avec certitude.
L’application ne retient que les grilles résolubles par déduction humaine
Quand elle fabrique une grille, l’application « Démineur » vérifie qu’on peut la résoudre du début à la fin avec les trois règles suivantes, que les humains utilisent.
- Ce que l’on déduit d’un seul chiffre
- Ce que l’on déduit en combinant deux chiffres
- Ce que l’on déduit du nombre de mines restantes dans toute la grille
Chaque règle porte sur un petit périmètre et se vérifie vite. Une grille que ces trois règles ne résolvent pas est refaite en déplaçant des mines. Ainsi, le joueur peut toujours aller jusqu’au bout sans devoir passer par le raisonnement lourd qui examine toutes les dispositions.
Les grilles jouables dans les articles de ce site sont fabriquées de la même façon. En mesurant la fabrication d’une grille de la taille du ★5 sur un ordinateur, il fallait en moyenne quelques millisecondes par grille.
Casse-têtes et mathématiques
On sait que beaucoup d’autres casse-têtes sur papier, comme le Sudoku, sont aussi NP-complets dans leur forme générale à grande échelle. Les casse-têtes qui plaisent aux humains sont souvent conçus pour qu’on puisse les résoudre en raisonnant, sans tout examiner. Les grilles sans hasard de l’application « Démineur » en sont un exemple.
Le calcul des probabilités est présenté dans Les probabilités au Démineur.
