Voir la source de Démineur (genre de jeu vidéo)

{{Voir homonymes|Démineur}}
{{Infobox Logiciel
 | image                    = Minesperfect windowsxp.png
 | légende                  = Mines-Perfect, un clone du Démineur fonctionnant sous [[Ubuntu (système d'exploitation)|Ubuntu]].
 | type                     = [[Jeu vidéo de réflexion|réflexion]]
}}

Le '''Démineur''' (Minesweeper) est un [[jeu vidéo]] de [[Jeu vidéo de réflexion|réflexion]] dont le but est de localiser des [[Mine terrestre|mines]] cachées dans une grille représentant un [[champ de mines]] virtuel, avec pour seule indication le nombre de mines dans les zones adjacentes.

De nombreuses versions gratuites du Démineur existent, mais {{référence souhaitée|la plus connue est}} celle fournie par défaut avec {{lequel|le [[système d'exploitation]] [[Microsoft Windows]]}}. Cette version particulière, sans avoir inventé le concept, l'a popularisé, et {{référence souhaitée|la désignation « Démineur » identifie souvent cette version précise et non le principe général du jeu.}}

Par défaut, le jeu se joue avec la [[Souris (informatique)|souris]] d'ordinateur, mais peut également aujourd'hui se jouer sur un [[écran tactile]].

== Variante de windows ==

Les [[graphismes]] du jeu sous Windows n'ont guère évolué entre la version sur [[Windows 3.0]] jusqu’à [[Windows XP]] ; néanmoins, on constate que sous [[Microsoft Windows Vista|Windows Vista]] et [[Windows 7]], les graphismes ont été améliorés.

À partir de [[Windows 8]], le Démineur n'est plus fourni avec Windows. Il passe sous la forme d'une [[Application (informatique)|application]] [[Xbox (console)|Xbox]] appelée « Microsoft Minesweeper » [[téléchargeable]] sur le [[Windows Store]]. Le jeu acquiert dès lors de nouveaux graphismes (un mode moderne et un autre mode « jardin »), un mode aventure et des récompenses à gagner avec un compte [[Xbox Live]].


== Histoire ==
Le démineur trouve son origine dans les années 1960 et 1970 en tant que l'un des premiers jeux sur ordinateur à une époque ou les ordinateurs se trouvaient dans des laboratoires ou dans de grandes entreprises. Le démineur s'inspire notamment du jeu de Jerimac Ratltiff "Cube"<ref name=":0">{{Lien web |langue=fr |titre=Histoire du démineur |url=https://www.demineur-ligne.com/histoire |site=demineur-ligne.com |consulté le=2021-07-31}}</ref>.

Le démineur ainsi que son genre deviendra populaire durant les années 1980 avec les titres [[Mined-Out]] ou Yomp<ref name=":0" />.

== Système de jeu ==
[[Fichier:Gnome Mines.png|vignette|Champ de mines en deux dimensions (2D)]]

=== Généralités ===
Le champ de mines du Démineur est représenté par une grille, qui peut avoir différentes formes : deux ou trois dimensions, pavage rectangulaire ou non{{etc.}}

Chaque case de la grille peut soit cacher une mine, soit être vide. Le but du jeu est de découvrir toutes les cases libres sans faire [[Explosion|exploser]] les mines, c'est-à-dire sans [[Clic (informatique)|cliquer]] sur les cases qui les dissimulent.

Lorsque le joueur clique sur une case libre comportant au moins une mine dans l'une de ses cases [[Voisinage de Moore|avoisinantes]], un chiffre apparaît, indiquant ce nombre de mines. Si en revanche toutes les cases adjacentes sont vides, une case vide est affichée et la même opération est répétée sur ces cases, et ce jusqu'à ce que la zone vide soit entièrement délimitée par des chiffres. En comparant les différentes informations récoltées, le joueur peut ainsi progresser dans le déminage du terrain. S'il se trompe et clique sur une mine, il a perdu.

On peut signaler les cases contenant des mines présumées par un [[drapeau]] en cliquant sur le bouton droit de la souris — mais ce n'est aucunement obligatoire. Il faut faire attention à ne pas signaler une case saine par un drapeau, car cela peut induire en erreur ; ce n'est toutefois pas aussi pénalisant que de découvrir une mine.

Dans le démineur de Windows, il est possible de cliquer simultanément avec les boutons gauche et droit de la souris sur une case. Cette manipulation est à faire sur une case ayant un numéro (donc avec une ou plusieurs mines à proximité) et lorsque le joueur a préalablement déminé le nombre requis de mines alentour. Dans ce cas là, toutes les autres cases adjacentes dépourvues de drapeau seront découvertes, permettant ainsi de gagner du temps.

Le jeu est chronométré, ce qui permet de conserver les meilleurs [[Score (nombre de points)|scores]].

Jusqu'à Windows XP, le démineur de Windows contenait également un ''[[smiley]]'' prenant différentes humeurs selon la situation : souriant en temps normal, triste lorsque le joueur a perdu, portant des lunettes de soleil lorsqu'il a gagné et nerveux lorsque le bouton de la souris est enfoncé. Un clic sur ce ''smiley'' permettait de commencer une nouvelle partie<ref>{{Article|lang=en|auteur=Lissa Wiebers|titre=Navigating Minesweeper|journal=SmartComputing|date=mars 1996|vol=4|no=3}}.</ref>.

=== Logique ou hasard ? ===
Si le jeu du Démineur est un [[problème NP-complet]]<ref>{{en}} Chris Studholme, [http://www.cs.toronto.edu/~cvs/minesweeper/minesweeper.pdf « {{Langue|en|Minesweeper as a Constraint Satisfaction Problem}} »] {{pdf}}, université de Toronto (informatique).</ref>, il invite cependant le joueur à combiner plusieurs tactiques, selon le degré de [[probabilité]]. On peut avoir des certitudes absolues selon le nombre d'informations qui s'entrecoupent ; mais on peut aussi n'en avoir absolument aucune, notamment lors des premiers coups où l'on est obligé de procéder à l'aveuglette ; enfin, on peut, sans avoir de certitude absolue, calculer de fortes probabilités. Il s'agit donc alternativement d'un [[jeu de hasard]] et d'un [[casse-tête]].

Certaines variantes cherchent à diminuer la part du hasard. Les plus simples offrent une option dans laquelle certaines cases connues du joueur, typiquement les coins, sont toujours sûres. Les plus sophistiquées jouent elles-mêmes en cas de situation où l'on ne peut pas trancher. Une variante particulière{{Laquelle}} a poussé ce dernier procédé dans ses limites : en demandant au joueur de jouer une case ou bien de déclarer explicitement qu'il croit ne pas pouvoir décider, elle rend chaque coup possible dans un espace mathématique étendu !

=== Mesure de difficulté ===
La difficulté d'une grille de Démineur peut être mesurée avec un indice : le 3BV (abréviation de [[Bechtel's Board Benchmark Value]]).

== Variantes ==
Le Démineur existait avant [[Microsoft Windows|Windows]], et a été exploité une fois bien connu du grand public sur de nombreuses [[Système d'exploitation|plateformes]] ([[Macintosh]], [[Linux]]…). Il existe également comme [[Extension (Mozilla)|extension]] des [[navigateur web|navigateurs]] de la famille [[Mozilla (chronique)|Mozilla]]. Dans la version Mozilla, il existe également un pavage [[Hexagone|hexagonal]] :

Des variantes plus exotiques existent qui proposent des variations de la structure du jeu avec par exemple des plateaux de jeu non plans, plusieurs mines par case, l'intégration d'une levée des indécidables ou bien du déroulement du jeu avec par exemple des parties en temps limité. Certains programmes offrent aussi des facilités pour le jeu à plusieurs joueurs, comme la certification des résultats en vue de l'établissement de classements, et des statistiques sur de nombreux aspects du jeu, comme sa difficulté théorique compte tenu de la distribution des mines.

<gallery>
Fichier:Cube Minesweeper 3D.png|Jeu de Démineur en 3D.
Fichier:Minesweeper games2relaxnet.png|Clone du Démineur non rectangulaire.
Fichier:Firefox Hexagon Minesweeper - fr.png|Clone du Démineur fonctionnant sur le navigateur [[Mozilla Firefox|Firefox]] (version hexagonale).
Fichier:Xbomb triangles.png|Clone triangulaire du Démineur.
Fichier:Freesweep.png|Clone du Démineur sur [[console système]] sous [[Ubuntu (système d'exploitation)|Ubuntu]].
</gallery>
<gallery>
Fichier:Mines Simon Tatham's.png|Le joueur ne doit jamais deviner dans « Mines », une version libre de [[Simon Tatham]] sur Ubuntu/[[Linux]].
Fichier:Firefox Multiple mines.png|Variante avec plusieurs mines dans certaines cellules, sous Firefox.
Fichier:Emoji Minesweeper.png|Variété de démineur utilisant emoji.
</gallery>

== Algorithmes ==
Dans cette section, nous allons considérer un tableau de démineur de largeur <math>m</math>, de hauteur <math>n</math>, et comportant <math>x</math> mines.

=== Calcul du nombre de mines de chaque case ===
Il existe deux grands [[algorithmes]] (au sens où ce sont les plus utilisés) permettant le calcul des nombres des différentes cases du Démineur.

==== Par case ====
Le premier algorithme est dit ''naïf'' : c'est la méthode la plus évidente à comprendre et à mettre en place, mais ce n'est pas la plus optimisée.

Après le placement des mines, l'algorithme parcourt le tableau en entier, case par case. Pour chacune d'entre elles, il compte le nombre de mines dans le voisinage direct, et lui assigne ce nombre.
Voici une implémentation simplifiée en [[pseudo-code]] :

 '''explorer''' ''tableau'' '''par''' ''case''
     '''si''' ''case'' '''est''' vide
         ''nombre'' := compter_mines(''case''.voisinage)
         ''case''.valeur = ''nombre''

Nous aurons donc une complexité algorithmique de <math>O( m \times n )</math>.

==== Par mine ====
Alors que le premier algorithme s'effectue dans un deuxième temps, celui-ci s'applique au moment-même du placement des mines sur le tableau.

L'algorithme fonctionne en considérant les mines et leur voisinage comme des ensembles. Lorsqu'une mine est incluse dans un de ses ensembles, le nombre qui lui est associé est incrémenté de un.
Ainsi, en pseudo-code :

 ''// Placement de la mine''
 
 '''explorer''' ''mine''.voisinage '''par''' ''case''
     '''si''' ''case'' '''est''' vide
         '''incrémenter''' ''case''.valeur

Cette approche du problème permet de réunir deux étapes en une seule. En termes de complexité algorithmique, cet algorithme est plus performant : <math>O( x )</math>, sachant que <math>x < (m \times n)- 1</math>, car le tableau ne peut ni être recouvert de mines, ni contenir plus de mines que de cases (exception faite des variantes avec plusieurs mines par case).

== Records ==
Le record du monde de vitesse de résolution du Démineur, dans les trois catégories de jeu (débutant, intermédiaire et expert) cumulées, serait détenu par le polonais Kamil Murański avec les temps suivants :

* Cumulé : 38,653 secondes
* Débutant : 0,49 secondes
* Intermédiaire : 7,03 secondes
* Expert : 31,133 secondes<ref>{{Lien web|langue=en|nom1=Kamil Murański Official|titre=Minesweeper Guinness World Record (23 July 2014)|url=https://www.youtube.com/watch?v=_Memsj4gCKw|date=2018-02-06}}</ref>

== Bugs ==
Dans la version [[Microsoft Windows|Windows]] du Démineur, en tapant durant le jeu le [[mot-clé]] « xyzzy », puis en appuyant sur la touche « [[Touche d'entrée|Entrée]] » et « [[Touche majuscule|Majuscule]] », le [[pixel]] du coin supérieur gauche de l'écran (écran Windows, et non pas la fenêtre de jeu) devient noir lorsque le curseur passe sur une mine, et blanc lorsqu'il passe sur une case libre.

== Postérité ==
La version [[Microsoft Windows|Windows]] du Démineur est l'une des entrées de l'ouvrage ''[[Les 1001 jeux vidéo auxquels il faut avoir joué dans sa vie]]''<ref>{{Ouvrage |langue originale=en|prénom1=Tony|nom1=Mott|titre=Les 1001 jeux vidéo auxquels il faut avoir joué dans sa vie|éditeur=Flammarion|lieu=Paris|année=2011|pages totales=960|isbn=978-2-08-126217-1}}.</ref>.

Dans un livre de 2023, Kyle Orland, [[journaliste]] spécialisé dans l'informatique, a révélé que [[Bill Gates]], patron de Microsoft, était "devenu accro" au jeu et que son équipe avait dû le retirer de son ordinateur<ref>{{Lien web |langue=fr |titre="Il est devenu accro”: obsédé par les records, Bill Gates a tellement joué au démineur que le jeu lui a été retiré |url=https://www.bfmtv.com/tech/microsoft/il-est-devenu-accro-obsede-par-les-records-bill-gates-a-tellement-joue-au-demineur-que-le-jeu-lui-a-ete-retire_AV-202303070244.html |site=BFMTV |consulté le=2023-09-19}}</ref>.

Le jeu est [[Parodie|parodié]] par l'équipe de {{lien|CollegeHumor}}, dans un sketch prenant la forme d'une fausse [[bande-annonce]] pour un film intitulé ''{{lang|en|Minesweeper: The Movie}}''<ref>{{en}} {{vid}} [http://www.collegehumor.com/video:1770138 ''{{lang|en|Minesweeper: The Movie}}''], sur ''collegehumor.com'', 6 août 2007.</ref>.

== Notes et références ==
{{Références}}

== Voir aussi ==
{{Autres projets | commons=Category:Minesweeper | commons titre=Démineur}}

=== Liens externes ===
* {{en}} [http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm Les mathématiques du Démineur, lien avec le problème P=NP], sur ''mat.bham.ac.uk''
* [https://demineur.nhtdev.com/ Démineur en ligne], l'une des nombreuses adaptations du démineur disponible sur le web.

{{Palette|Composant Windows|Genres de jeux vidéo}}
{{Portail|logiciel|jeu vidéo|Microsoft}}

{{CLEDETRI:Demineur}}
[[Catégorie:Genre de jeux vidéo]]
[[Catégorie:Jeu vidéo de réflexion|*]]
[[Catégorie:Jeu NP-complet]]