Le démineur et la logique, réduction et équivalence

Piste bleue Le 6 septembre 2018  - Ecrit par  Arthur Milchior Voir les commentaires (5)

Que signifie que deux problèmes sont « équivalents » ? Comment montre-t-on qu’un problème mathématique est plus dur qu’un autre ? Je tente une introduction à cette question, en mélangeant le célèbre jeu du démineur, et la logique propositionnelle.

Cet article est majoritairement en piste bleue avec quelques parties, notamment les blocs déroulants, en piste rouge.

J’ai souvent entendu la blague suivante quand j’apprenais à
programmer.

Vous donnez à un robot [1] un paquet de pâtes, une casserole, une plaque chauffante, et un robinet d’eau. Puis vous lui apprenez comment faire des pâtes. Quelques jours plus tard, vous demandez au robot de faire des pâtes, en lui disant qu’il y a de l’eau bouillante dans la casserole. Vous voyez alors le robot vider la casserole dans l’évier. Quand vous lui demandez pourquoi, il vous répond que, pour faire des pâtes, on lui a dit qu’il fallait commencer avec une casserole vide. Totalement logique, le robot commence par vider la casserole.

Une introduction à la notion de réduction

Un informaticien parlerait de réduction. Le robot a
réduit le problème « Faire des pâtes à partir d’une casserole pleine d’eau » au problème « faire des pâtes à partir d’une casserole vide ».

Intuitivement, effectuer une réduction signifie que, à partir de la
première situation, vous pouvez atteindre la seconde facilement. Dans
l’exemple fictif ci-dessus, la réduction ne présente aucun intérêt
pour un humain. L’humain omettra les premières étapes de la recette,
et commencera à l’étape de la recette où l’eau bout.

Peut-être que le robot ne sait pas comment ignorer des
étapes. L’utilisateur du robot devra alors choisir entre deux
solutions : apprendre au robot à faire des pâtes à partir d’une
casserole pleine, ou laisser le robot effectuer la réduction.
Avec la réduction, on utilise plus de temps de robot pour la cuisson. Mais on utilise moins de temps de développeur pour programmer le robot. Avec la réduction, les pâtes prendront une dizaine de minutes de plus à être prêtes, chaque fois qu’on lancera le robot alors que la casserole aura déjà de l’eau chaude. Sans la réduction, la première fois il faut attendre que le développeur ait fini de reprogrammer le robot ; c’est probablement long, mais il ne faudra le faire qu’une seule fois. Les pâtes seront prêtes plus rapidement les autres jours.

L’intérêt des réductions

Jusqu’à présent, la réduction n’était pas passionnante. Pour la rendre un peu plus intéressante, on va se placer dans un cadre encore plus fictif. On va imaginer qu’on ne sait pas comment faire cuire des pâtes. Ni à partir d’une casserole pleine, ni à partir d’une casserole vide.

Naïvement, on pourrait imaginer que cette réduction ne présente plus d’intérêt. Après tout, on a réduit un problème qu’on ne sait pas résoudre à un autre problème qu’on ne sait pas résoudre. On n’est pas vraiment plus avancé.

Puisque mon paragraphe précédent commençait par « naïvement », vous vous doutez certainement qu’il était faux. Mon but ici est de vous présenter la raison pour laquelle ces réductions sont extrêmement importantes ! En effet, la réduction ci-dessus a permis de montrer que cuire des pâtes à partir d’une casserole pleine n’est pas beaucoup plus compliqué que de cuire des pâtes à partir d’une casserole vide.

Pour dire ça autrement, le jour où l’on saura cuire des pâtes à partir d’une
casserole vide, on aura aussi appris à cuire des pâtes à partir d’une
casserole pleine. Notre réduction aura donc fait gagner du temps aux
futurs chercheurs en cuisson de pâtes. Elle leur permettra d’étudier un seul problème au lieu d’en étudier deux.

Imaginons qu’un laboratoire de recherche se spécialise dans la question de la cuisson des pâtes à partir d’une casserole vide, et qu’un autre se spécialise dans la question de la cuisson des pâtes à partir d’une casserole pleine. Notre réduction aura permis de rapprocher les deux laboratoires. Les résultats partiels du laboratoire de cuisson des pâtes à partir d’une casserole vide pourront être automatiquement utilisés par les chercheurs de laboratoire de cuisson des pâtes à partir d’une casserole pleine.

Cet exemple permet aussi de noter que la notion de « réduction » présentée dans cet article est assez éloignée des notions de réduction plus usuelles. Ainsi, « réduire un polynôme » correspond à une action précise. Et le résultat de la réduction est plus simple que le polynôme de départ. Dans cet article, on pourra parler de réduction dès qu’une question est transformée dans une autre question. Au lieu de réduire pour « simplifier » un problème, ici, il faudra considérer que réduire permettra de « considérer différemment » un problème. Ce type de réduction est d’autant plus important qu’en pratique, il n’est pas toujours évident de savoir quel problème est « plus simple » qu’un autre.

La notion d’équivalence

Retournons à nos casseroles : remarquons qu’en remplissant la casserole, on obtient
une casserole pleine ! On a alors réduit le problème « faire des pâtes
à partir d’une casserole vide » à « faire des pâtes à partir d’une casserole pleine ». Puisqu’on a réduit chaque problème à l’autre, on voit que ces problèmes sont équivalents.

Pour reprendre nos laboratoires, on a ainsi montré que chacun des deux laboratoires peut utiliser les résultats de l’autre laboratoire. Le travail de l’un profite à l’autre. Mais en même temps, le travail de l’autre profite à l’un.

Il y a plusieurs branches de la recherche en informatique étudiant les réductions et les équivalences entre différentes questions, le cadre le plus général étant la théorie de la calculabilité. Plus précisément, cette théorie s’intéresse au problème extrêmement complexe de montrer que certaines réductions ne peuvent pas exister. Une seconde branche est la théorie
de la complexité
 [2]. Cette théorie s’intéresse non seulement à prouver que certaines réductions existent, mais aussi que ces réductions sont (relativement) simples à effectuer.

Un vrai exemple d’équivalence

Il n’est pas très surprenant que les deux problèmes mentionnés plus haut soient équivalents, puisque ces problèmes sont extrêmement similaires. Là où cette notion devient plus intéressante, c’est lorsque l’on montre l’équivalence de deux problèmes qui n’ont, à première vue, rien à voir. C’est donc ce que je vais faire, et, comme annoncé dans le titre, ces problèmes sont celui du démineur, et celui de la logique propositionnelle. Avant de vous montrer la réduction, je vous explique quels problèmes je considère précisément.

La définition des problèmes considérés

Le démineur

Le premier problème qui va m’intéresser est le jeu du
démineur. Au cas où vous n’ayez pas joué au démineur depuis longtemps,
voir jamais joué au démineur, je me permets un petit rappel du problème.

Un plateau de démineur consiste en un grand tableau rectangulaire. Certaines cases de ce tableau contiennent une bombe cachée. Les cases sans bombe
cachée peuvent contenir un nombre entre 0 et 8 qui indique le
nombre de bombes cachées dans l’ensemble des 8 cases adjacentes. La question est donc la suivante : on vous donne un tableau de démineur, et on vous montre une case, en position $(n,m)$. Pouvez vous affirmer : « la case
$(n,m)$ contient nécessairement une bombe cachée » [3] ? Un joueur aura besoin de
savoir répondre à cette question pour décider s’il peut cliquer
sur la case afin de révéler le nombre et avancer dans le jeu, ou
si cette case est dangereuse et doit être évitée autant que possible.

Dans le jeu classique, le 0 n’est jamais écrit. À la place, une case
vide enfoncée est montrée, et tous ses voisins sont automatiquement révélés. Un compteur indique le nombre de bombes cachées sur le plateau. De plus, le joueur peut placer des drapeaux pour indiquer les bombes qu’il a repérées avec certitude. Pour simplifier cet article, on ignorera tout cela, sauf dans les illustrations.

La logique propositionnelle

Le second problème qui m’intéresse s’appelle « satisfiabilité de la
logique propositionnelle ». Intuitivement, on vous dit « je veux ça,
ça, ça et ça, à la fois. », et vous devez trouver s’il est possible de
satisfaire cette demande.

Un exemple des plus standard est le suivant : vous voulez prendre un bain et regarder la télé, sachant que :

  • la baignoire est dans la salle de bain,
  • la télé est dans le salon,
  • vous ne pouvez pas être dans plus d’une seule pièce à la fois.

Rajoutons un peu de formalisme mathématique. Indiquer que le bain est
dans la salle de bain se dirait ($P_{\text{bain}}$ implique
$P_{\text{salle de bain}}$). Similairement, indiquer que la télé est
dans le salon se dirait ($P_{\text{télé}}$ implique
$P_{\text{salon}}$). Enfin, indiquer qu’on ne peut pas être dans deux
pièce à la fois se dirait (non ($P_{\text{salle de bain}}$ et
$P_{\text{salon}}$)).

Une fois qu’on a utilisé ce formalisme, on peut
remplacer « bain » par 1, « salle de bain » par 2, « salon » par 3 et « télé »
par 4. Cela donne le problème :

  • ($P_1$ implique $P_2$)
  • ($P_4$ implique $P_3$)
  • (non ($P_2$ et $P_3$))
  • ($P_1$ et $P_4$).

Notre problème initial et cette variante avec des $P_i$ sont strictement équivalents, mais la seconde version sera bien plus simple à passer à un logiciel.
Ce logiciel vous répondra rapidement qu’il n’y a aucune
solution. Cette formule n’est pas satisfiable. Vous pouvez interpréter cette réponse comme l’affirmation : je ne peux pas regarder la télé et prendre mon bain en même temps.

Réduisons un problème à l’autre

Maintenant que l’on sait précisément de quoi l’on va parler, on peut commencer à créer des réductions. Pour rappel, dans l’introduction, la réduction consistait à « vider l’eau de la casserole ».

En généralisant, on voit que « réduire » signifie simplement « donner un procédé pour transformer un problème en un autre problème ». Un informaticien dirait qu’une réduction est un algorithme, un programme, une procédure, une méthode.

Nous allons donc donner ici une méthode pour transformer un plateau de démineur en une formule logique. La formule sera satisfiable si et seulement si il y a une bombe en case $(n,m)$ du plateau. C’est cette dernière propriété qui donne à cette méthode le nom de « réduction ».

Ensuite, on donnera une méthode pour transformer une formule en un plateau de démineur et l’on montrera que cette méthode est aussi une réduction.

Réduction du démineur vers la logique propositionnelle

Je vais maintenant reprendre l’exemple du démineur, et montrer comment le réduire à la logique propositionnelle. Un
informaticien voulant faire une réelle réduction devrait considérer
énormément de détails, tels que les bords du plateau [4]. Puisque l’on est
dans un article de vulgarisation, l’idée sera simplement esquissée.

Notre formule logique aura une proposition par case $(i,j)$. Et chaque
proposition sera simplement l’affirmation « il y a une bombe en case
$(i,j)$ ». On rajoutera ensuite les hypothèses suivantes.

  • Toutes les cases $(i,j)$ qui contiennent un nombre ne contiennent pas de bombe.
  • Si une case affiche le nombre 5, par exemple, alors elle possède très exactement 5 voisins avec une bombe.

Pour rappel, on a fixé au début du problème une case $(n,m)$, c’est la case sur
laquelle on aimerait être sûr qu’il n’y a pas de bombe. On va donc passer au programme de logique propositionnelle les hypothèses ci-dessus, avec en plus l’affirmation « La case $(n,m)$ contient une bombe ».

Si le programme de logique propositionnelle nous indique « tout
cela peut être satisfait », alors vous savez qu’il peut y avoir une bombe
en case $(n,m)$. Donc vous devriez éviter de cliquer sur cette case si
vous voulez éviter de perdre. Par contre, si le programme vous répond
que tout cela n’est pas satisfiable, cela signifie qu’il est
impossible qu’il y ait une bombe dans cette case, donc vous pouvez
cliquer dessus sans aucun risque. [5]

En pratique, quelqu’un qui voudrait créer un programme qui joue au
démineur aura intérêt à utiliser cette réduction, au lieu de
programmer « à la main » un algorithme pour le démineur. Cela lui
permettra de réutiliser les programmes de logique
propositionnelle. D’une part, ces logiciels sont extrêmement efficaces [6].
D’autre part, cette réduction est très rapide à faire, alors que
devoir réécrire à la main toutes les règles pour décider si la case
$(n,m)$ peut contenir une bombe ou non – ce qui est potentiellement
influencé par des nombres situés sur des cases très éloignées de la case $(n,m)$- risque d’être fort compliqué.

Réduction de la logique propositionnelle au démineur

Je vais maintenant tenter de vous indiquer comment on peut utiliser le
démineur pour résoudre des questions de logique.

Propositions

En logique classique, les propositions sont soit fausses, soit vraies. On ne considère pas les cas où une propriété serait « un peu vraie » ou bien « aurait $p$ pour cent de chances d’être vraie ».

Prenons une proposition $P$, on va
choisir une case $(n_P,m_P)$ du démineur, et on va décider que « il y a une bombe en case $(n_P,m_P)$ » représente l’affirmation « $P$ est vrai », tandis que « il n’y a pas de bombe en case $(n_P,m_P)$ » représente l’affirmation « $P$ est faux ». On fera de même pour toutes les autres propositions.

Considérons la figure ci-dessus, et plus précisément les trois bombes indiquées par des boules noires. On remarque que les deux cases à gauche de la bombe du milieu ne contiennent ni nombre ni drapeau. On ne sait rien de la case de gauche de cette paire, et on ne sait rien de la case de droite de cette paire. Chacune de ces cases peut avoir une bombe. Il est vrai aussi que chacune de ces cases peut ne pas en avoir. Dans le reste de l’article, on dira qu’une telle case est une case inconnue. Effectivement, on ne connait rien du contenu de cette case.

Notez cependant que si l’on ignore tout des cases, prise séparément, on a une information forte sur la paire de cases : on sait qu’elle ne contient qu’une unique bombe. Autrement dit, si la case gauche de cette paire de case contient une bombe, alors celle de droite n’en contient pas, et réciproquement.

Dans tout le reste de l’article, quand on parlera d’une « paire », il s’agit d’une paire similaire à celle décrite ci-dessus. Deux cases, côte-à-côte (ou l’une sur l’autre), telles qu’aucune ne contienne de bombe ou de nombre, et que pourtant, les voisins immédiats nous apprennent qu’une seule d’entre elles contient une bombe.

Si l’on s’intéresse à ces paires, c’est qu’on va décider de donner un sens au fait de mettre une bombe à gauche ou à droite de la paire de cases. Pour être précis, on peut démontrer que [7], avoir la bombe à gauche est équivalent au fait que la proposition est vraie.

Fil

Le démineur ne contient que des contraintes « locales ». Chaque nombre
influence les 8 cases autour de lui et rien d’autre. On a expliqué au-dessus comment encoder les propositions. Mais cela ne servirait à rien
si ces propositions n’influençaient qu’un endroit précis du plateau. On
va donc créer des sortes de « fils électriques » en démineur, qui vont
permettre de copier la valeur « vraie » ou « fausse » depuis l’entrée, une extrémité du fil, jusqu’à l’autre.

Si un joueur de démineur analyse le plateau ci-dessus, il pourra remarquer le fait suivant : « si dans une paire , la case de droite a une bombe, alors la case de droite de toutes les paires a une bombe. » Ce fait est illustré par l’image ci-dessous.

Il en est de même si la bombe est sur la case de gauche de la paire de cases inconnues.

Intuitivement, ce fonctionnement peut rappeler le fonctionnement des circuits électriques. Mais au lieu de tout encoder à l’aide de 0 et de 1, tout est encodé en mettant des bombes ou des cases vides à certaines positions précises et régulièrement espacées de 3 cases.

Opérations

En logique propositionnelle, l’opération la plus basique s’appelle « non ». Elle transforme « Vrai » en « Faux » et réciproquement. On peut l’encoder comme ceci :

On peut découper ce plateau en trois parties, selon la colonne contenant deux bombes. Si l’on reste dans la métaphore du fil électrique transmettant une information, on peut considérer que le plateau contient deux fils, un à gauche, un à droite, et que ces deux fils sont reliés par une porte (le centre du plateau, qui fait trois colonnes de large). Il ne devrait pas être très difficile de vérifier que ce plateau encode un « non » ; c’est à dire que cette porte inverse le contenu du fil. Autrement dit, si dans la paire de cases inconnues qui se trouve à gauche de la porte, l’unique bombe est dans la case de gauche, alors dans la paire de cases inconnues à droite de la porte, l’unique bombe est à droite.

L’exemple ci-dessous illustre l’effet qui vient d’être décrit.

Le plateau suivant encode un « et ».

Je crois que le morceau de plateau ci-dessus mérite plus d’explications que les précédents. Dans ce grand plateau, si « Vrai » arrive en haut et en bas, alors « Vrai » apparaît aussi à droite. Dans les autres cas, « Faux » apparaît à droite. Personnellement, j’admire Richard Kaye qui, le premier, a trouvé ce plateau. Heureusement, il n’est pas nécessaire de le comprendre précisément pour suivre l’idée de la preuve. Mais les lecteurs que cela amuse peuvent vérifier que le plateau encode bien un « et » en testant toutes les positions de bombes compatibles avec ce plateau. À noter que, si le plateau encode effectivement la fonction « Et » alors il y a uniquement 4 manières possibles de placer les bombes plateaux. Quand les entrées sont les mêmes, les bombes sont posées de manière à respecter la symétrie horizontale du plateau : une manière de poser les bombes avec les entrées Vrai en haut et Faux en bas ; et un plateau avec l’entrée Faux en haut et Vrai en bas, qui est
obtenu à partir du plateau précédent via une symétrie horizontale dont l’axe est le centre du morceau de plateau.

Explication du tableau encodant la fonction ET

Les deux « fils » qui servent d’entrées sont à gauche. Un fil se trouve en haut et l’autre en bas. J’ai mis deux bombes dans ces fils, le fil du haut est en position vraie, tandis que le fil du bas est en position fausse. Quand il devenait certain qu’une bombe était présente sur une case auparavant inconnue, je l’ai aussi rajoutée en rouge. S’il est certain que la bombe est absente de cette case, j’ai mis un point d’exclamation sur la case.

On voit maintenant qu’on est bloqué. Sur la 7ème colonne, il y a 4 cases où l’on ne peut pas dire, pour l’instant, où se trouvent les bombes. Les « 3 » qui se trouvent en 8ème colonne nous permettent tout au plus de savoir qu’il y a très exactement une bombe sur chacune des paires de cases inconnues. De plus, on ignore s’il y a une bombe ou non sur la case directement à droite du 4. Cette question est très importante, puisque le centre du plateau est similaire au « fil » décrit plus haut. Les deux plateaux ci-dessous montrent effectivement que l’absence ou la présence de la bombe à droite du 4 déterminent la sortie du plateau, c’est à dire que cela détermine le contenu de la case inconnue tout à droite.

On voit donc que, selon l’encodage qu’on s’est choisi, que la sortie est « vraie » si et seulement si il n’y a pas de bombes sur la cases à droite du « 4 ».

Enfin, on va étudier comment la 7ème colonne détermine s’il y a, ou non, une bombe dans la case à droite du « 4 ». Commençons par étudier ce qui se passe quand on ne met pas une bombe sur la case de la 7ème colonne au dessus du « 4 ». (Par symétrie, on n’a pas besoin d’étudier la case en-dessous du « 4 »). Encore une fois, j’ai complété en indiquant les bombes présentes et absentes.

On remarque que, dans ce cas-là, la case à droite du « 4 » ne contient pas de bombe. Pour que le « 4 » ait effectivement 4 voisins, il faut donc que tous ses autres voisins inconnus aient une bombe.

En mettant bout à bout tout ce qui se trouve dans cette note, on peut voir que :

  • si les deux entrées sont sur « vraie », alors on va satisfaire le « 4 » sans mettre de bombe à sa droite (on la mettra en-dessous ou au-dessus), et donc la sortie sera « vraie ».
  • dans tous les autres cas, il n’y a pas assez de bombes à gauche du « 4 », il faudra donc en mettre une à sa droite, et donc la sortie sera « fausse ».

Notons que « A ou B » peut se réécrire en « Non (Non A et Non B) », il n’est donc pas nécessaire de créer un plateau pour encoder l’opération ou.

Fin de la réduction

Une fois que votre formule propositionnelle est totalement encodée dans
un jeu de démineur, vous pouvez vous demander "Est-ce qu’il peut y
avoir une bombe dans la position qui représente Vrai pour la formule
entière". Si oui, alors la formule est satisfiable, sinon la formule
n’est pas satisfiable. Et vous avez réduit le problème de la logique
propositionnelle à la satisfiabilité.

Les autres morceaux de plateau.

Pour des raisons techniques, il faut savoir dupliquer une valeur :

et faire un quart de tour :

Dans ces exemples, les points noirs représentent les bombes dont l’emplacement est certain. Et le 2 entouré représente une correction par rapport à l’image originale.

Les logiciens ont l’habitude de définir « A implique B » comme étant « (Non A) ou B ». Ce qu’on peut réécrire en « Non (A et (Non B)) ». Le plateau ci-dessous montre à quoi ressemble « Non (A et (Non B)) ». On suppose que A est la variable encodée en haut à gauche, et B en bas à gauche. On remarque le plateau du « Non », qui apparaît en haut ainsi que tout à droite, et celui du décalage qui apparaît en bas, ainsi que des quarts de tour (cf. le texte dans le bloc pour les détails).

PNG - 24.1 ko

Intérêt de cette réduction

Bien sûr, quand un logicien voit une formule logique, il n’a pas pour
habitude de la transformer en un plateau de démineur. C’est une
méthode extrêmement inefficace pour attaquer un problème
logique. L’intérêt de cette réduction est tout autre. Cette réduction
montre que quiconque résout le démineur aura aussi résolu les
problèmes de logique propositionnelle. Puisque les problèmes de
logique propositionnelle ont été énormément étudiés depuis des
décennies, et sont connus pour être très durs en théorie, cela montre que le démineur est lui aussi très dur en théorie. Donc qu’il n’est probablement pas utile de s’attaquer à faire un programme qui résout systématiquement n’importe quel plateau de démineur de manière efficace.

Pour dire ça autrement, en théorie, une fois qu’on aura créé un programme qui résout tous les plateaux de démineur,

  • soit on ne pourra pas démontrer qu’il est rapide [8],
  • soit on ne pourra pas prouver qu’il ne fait pas d’erreur,
  • soit on pourra prouver qu’il sera rapide et sans erreurs, auquel cas il aura profondément révolutionné la science informatique.

Plus haut, j’ai écrit le mot « théorie ». En effet, en pratique, on a des programmes, appelés SAT-Solvers, qui proposent rapidement des solutions justes aux questions de logique propositionnelle. Simplement, on n’a pas prouvé qu’ils répondront effectivement rapidement tout le temps. En théorie, on peut donc imaginer qu’il existe une famille infinie de plateaux de démineur (ou de formules logiques, c’est la même chose), sur lesquels le programme va être exceptionnellement lent. Encore que trouver une telle famille peut aussi constituer un problème compliqué.

Bref, on peut considérer qu’en pratique, réduire le démineur vers la logique propositionnelle permet de gagner efficacement le démineur. Il reste cependant envisageable qu’un créateur de jeux décide délibérément de créer des énigmes, sous la forme de plateaux inhabituellement compliqués (cela ne serait probablement pas évident à faire).

Notes

Une note technique pour aller plus loin en complexité.

Plus précisément, le démineur est NP-complet. Je ne tenterai pas d’expliquer la définition ici.

  • La vérification est polynomiale : le témoin est la position de toutes les bombes du plateau.
  • Cet article a présenté la réduction de la logique propositionnelle vers le démineur. La réduction est clairement en temps polynomial.
Post-scriptum :

Je remercie Pierre McKenzie qui a pris le temps de nous montrer ce résultat - magnifique autant que fantaisiste - quand je suivais son cours d’introduction à l’informatique théorique. Mes plateaux sont inspirés de ses slides. Mes plateaux ont été générés à l’aide d’un programme rédigé spécialement pour cet article, Minesweeper txt2svg.

Je remercie aussi Pierre Lescanne, Arnaud Girand et Alejandro Rivera pour leurs relectures attentives ainsi que le lecteur B !gre pour avoir corrigé une erreur après la publication.

Le document original est Minesweeper is NP-complete de Richard Kaye.

Article édité par Marie Lhuissier

Notes

[1la version originale utilise un développeur, voir un ingénieur, un technicien. Ayant une préférence pour rigoler aux dépens des robots plutôt que des humains, je m’octroie une liberté d’adaptation que je vous prie de m’excuser.

[2Notez qu’il existe plusieurs branches mathématiques nommées « complexité », ici, il s’agit de celle dont le nom anglais est Computational Complexity, théorie qui n’a rien à voir avec, par exemple, la complexité de Kolmogoroph

[3Idéalement, il faudrait aussi être capable de répondre à la question « la case $(n,m)$ ne peut pas contenir de une bombe cachée ». En effet, si vous avez obtenu « non » à la première question, vous ne pouvez pas savoir si cela signifie qu’aucune bombe n’est présente, ou bien simplement si aucune réponses ne peut être obtenu. Par mesure de simplicité, je ne traiterai qu’une seule de ces questions.

[4Une case a habituellement 8 voisins. Une case au bord n’a que 5 voisins. Une case de coin a 3 voisins. Il s’ensuit que le chiffre 3 a une signification différence selon où il se trouve. S’il est au milieu du plateau et qu’aucun des voisins sont enfoncés, alors il ne donne pas tellement d’informations sur les cases voisines. Si au contraire le chiffre 3 apparaît dans un coin, il indique sans l’ombre d’un doute que tous les voisins sont des bombes. Il faut que le programme prenne ce genre de fait en compte. Sans que ça ne soit théoriquement complexe, oublier ce genre de détails créerait probablement un bug dans notre programme.

[5Exercice laissé au lecteur : on vient d’expliquer comment savoir s’il y a potentiellement une bombe sur une case $(n,m)$. Comment ferait-on pour savoir s’il y a nécessairement une bombe sur la case $(n,m)$ ? Peut-on réduire une question à l’autre ?

[6En effet, énormément de développeurs ont travaillé à rendre ces programmes les plus efficaces possible. Non pas pour résoudre le démineur, mais pour résoudre d’autres problèmes, moins drôles mais plus utiles, qui se réduisent à la logique propositionnelle de façon similaire.

[7Sous l’hypothèse que la valeur de vérité de la propositions $P$ soit bien encodée dans la case $(n_p,m_p)$ comme expliqué plus haut

[8La notion de rapidité a une définition précise en informatique, que je ne préciserai pas ici

Partager cet article

Pour citer cet article :

Arthur Milchior — «Le démineur et la logique, réduction et équivalence» — Images des Mathématiques, CNRS, 2018

Crédits image :

Image à la une - Démineur par games2relax.net [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • Le démineur et la logique, réduction et équivalence

    le 7 septembre à 10:20, par B !gre

    Merci votre réactivité (et je suis rassuré, je n’avais pas raté un truc ;-)).

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM