Hello,

Après pas mal de mini grilles de démineur, a germé, dans mon esprit, une idée "so geek but so fun" . Cette fois-ci il s'agit de défi de construction! Et c'est exactement ce que le titre dit que c'est: on va faire de l'électronique en démineur.

Considérons l'image suivante:

La première remarque que l'on va faire concerne une équivalence. Dans une vraie grille de démineur la structure du bas ne peut pas exister, car les cases libres autour devraient indiquer le nombre de mines voisines. Cependant, en tant que constructeur du problème, si on ne désire pas donner trop d'indices on peut simplement coller des mines supplémentaires, ce qui donnerait la structure du haut totalement équivalente.
Dans ce probleme de construction on ne va pas s'embêter à alourdir nos constructions avec des mines inutiles, on a le droit d'écrire comme la structure du bas avec des cases vides ne donnant pas d'information.


Parlons maintenant de choses intéressantes:
Si on regarde la structure du bas, filiforme, on remarque qu'elle n'est pas déterminée. En revanche si on fixe l'état de la case A (mine ou pas mine) le déterminisme se repend dans la structure et fixe l'état de la case B, précisément au même que celui de A. On peut donc interpréter A comme une entrée binaire à deux états et la structure comme un fil électrique.

Les défis:
-Réaliser la porte logique "non" (mise en jambe, ca doit être trivial): c'est à dire une structure ou on a une case d'état inconnue, notre entrée, pour laquelle fixer son état implique l'état d'une certaine case, notre sortie. La sortie valant toujours l'état opposé de l'entrée (On doit pouvoir brancher un fil du genre évoqué sur entrées et sorties)

-Réaliser les portes logiques "et, ou": c'est à dire une structure ou on a deux cases d'états inconnues, nos entrées, pour lesquelles fixer leur état implique l'état d'une certaine case, notre sortie. Pour la porte logique "et" cette sortie doit valoir "mine" si et seulement si les deux entrées valent "mine". Pour la porte logique "ou" cette sortie doit valoir "mine" si et seulement si au moins une des deux entrées vaut "mine" (On doit pouvoir brancher un fil du genre évoqué sur entrées et sorties)

-Réaliser un croisement de fil. (Le plus fun)

-Subsidiaire: Toute réalisation d'autre porte logique, "xor", "ou" multi-entrées etc... est la bien venue du moment qu'elle n'est pas un assemblage des portes et ou existantes, ie des versions plus compactes donc intéressantes.

Vos composants doivent être compatibles avec n'importe quel signal en entré. (ie: avoir au moins une solution valide).

Je donnerais des mentions spéciales aux composants les plus compactes/utilisables etc...

Bonne chance!

Solution:
Spoiler : [Afficher le message]
Voici une compilation des portes logiques les plus utiles dans leur version la plus compacte.
Remerciement spécial à w9Lyl6n et Klimrod (L'image est zoomable)

(Cliquer pour zoomer)

Chapeau à scarta qui a eut le courage de construire un additionneur 4-bit (en page 2)

Quelques mots en plus:
Avec simplement les portes logiques "et", "non", et le croisement de fil on dispose de suffisamment d'outils pour construire en démineur toute fonction calculable. Vous pouvez faire un additionneur n-bit, une multiplication si ça vous chante etc...

En présentant la chose autrement, on peut aussi remarquer qu'il est possible de construire une grille de démineur dont la résolution est équivalente à la satisfaction d'une formule logique de notre choix. (probleme SAT) ce qui démontre assez élégamment la NP-Completude du problème. (et comme ce n'est pas tous les jours qu'on démontre la NP-Completude d'un truc autant le remarquer lorsqu'on le fait).