Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 23-04-2012 09:50:34

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Electroniqque en démineur (u mad bro)

Hello,

Après pas mal de mini grilles de démineur, a germé, dans mon esprit, une idée "so geek but so fun" tongue. 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:
http://www.prise2tete.fr/upload/Clydevil-Clydevil-MineWire.PNG
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).



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 23-04-2012 11:11:34

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Electronique en démineu (u mad bro)

Je ne suis pas sur d'avoir bien compris (je ferais de joli dessin ce soir)

NON :
A1B

ET
A'
A2x1B

OU
A'
A1x1B

 #3 - 23-04-2012 11:22:10

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Electronique en démineur (u mad bro))

@godisdead: Oui tu as bien compris mais au détail important que les composants doivent pouvoir accepter n'importe quoi en entrée. Ici par exemple ta porte ET n'accepte pas l'entrée A=0 A'=0. Et ta porte OU n'accepte pas l'entrée A=1 A'=1

 #4 - 23-04-2012 11:56:03

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3771
Lieu: hébesphénorotonde triangulaire

Electronique en édmineur (u mad bro)

Bonjour,

La porte logique NON est facile.

J'ai trouvé plusieurs schémas de porte logique ET et OU, mais voici celui que je préfère, dans lequel on trouve les deux portes à la fois :



PS. Mon image est zoomable, pour plus de lisibilité..

Merci pour ce bon moment de réflexion, j'ai l'impression qu'il va ya voir des suites...
wink smile
Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #5 - 23-04-2012 12:33:26

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Electronique n démineur (u mad bro)

Super idée, de faire de l'électronique avec le démineur
J'ai déjà les trois premières portes:
http://www.prise2tete.fr/upload/w9Lyl6n-demineur_non_et_ou.PNG
Les points verts sont bien sûr les entrés, et les rouges les sorties.

La porte "NON" peut aussi servir de fils si on en connecte un nombre pair

smile Je continue de chercher pour la suite...

 #6 - 23-04-2012 14:03:51

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Electronique en démineur ((u mad bro)

@Klimrod: Je valide la porte "NON" ainsi que la porte mixte (ET/OU). En revanche la porte ET simple en bas à gauche est indéterminée sur 0|1  et la porte ET simple en bas à droite n'accepte pas 0|0.

@w9Lyl6n: Je valide tout.

@Tout le monde: Suspense, qui trouvera le premier le défi 3, le croisement de fil. big_smile

 #7 - 23-04-2012 14:15:25

LeXav
Habitué de Prise2Tete
Enigmes résolues : 18
Messages : 16
Lieu: Somewhere in Nevada

electronique en démineut (u mad bro)

Hello !

Voici mes propositions pour les trois premiers problèmes :

http://www.prise2tete.fr/upload/LeXav-GrilleV1.PNG

J'ai essayé de faire le plus compacte possible wink

Pour le croisement de fil, on doit pouvoir au moins faire comme ça :
http://matthieu.walraet.net/automate/croisement.html

je vais chercher si on peut trouver mieux...


Xav, Le Xav

 #8 - 23-04-2012 14:26:27

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Electronique en déminur (u mad bro)

@LeXav: Je valide le OU,  le ET par contre est également un "OU", et étonnamment le "NON" ne marche pas.

 #9 - 23-04-2012 14:31:48

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3771
Lieu: hébesphénorotonde triangulaire

Electronique e démineur (u mad bro)

Porte simple à gauche de mon schéma : effectivement, je m'en étais rendu compte et j'avais édité entre-temps mon schéma (tu avais l'ancien schéma dans ton cache)

Porte simple à droite de mon schéma : tu as raison, elle n'est pas correcte.

Qu'est ce que tu entends par croisement de fils ?

Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #10 - 23-04-2012 14:40:10

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

electronique en sémineur (u mad bro)

Porte simple à gauche de mon schéma : effectivement, je m'en étais rendu compte et j'avais édité entre-temps mon schéma (tu avais l'ancien schéma dans ton cache)

C'est toujours le cas, et je pense que le site merdouille un peu avec ce genre de cache, j'avais déjà vu ca avec P2Tower défense -> Utiliser un autre nom d'image, même si l'autre est supposée détruite.

Qu'est ce que tu entends par croisement de fils ?

Et bien, ici on a la possibilité de faire des fils, mais si on fait se croiser cette structure fil de mon image exemple évidemment ca merde au croisement. Il faut donc concevoir un croisement qui fait en sorte que toute information sur un des fils qui se croisent n'impacte pas l'information véhiculée par l'autre fil big_smile

 #11 - 23-04-2012 15:09:56

Palin01
Passionné de Prise2Tete
Enigmes résolues : 39
Messages : 70
Lieu: Lille

Elecctronique en démineur (u mad bro)

Salut,
Vraiment maline l'idée, j'aime beaucoup.

 
http://img11.hostingpics.net/pics/540294Portesclydevil.jpg

La porte ET peut surement être plus compacte mais bon pour l'instant ça me suffit.

Edit : Je suis en train de réfléchir sur le croisement mais c'est pas simple du tout.

En fait j'ai l'impression qu'il faudrait une sorte de test pour savoir si l'entrée est une mine ou pas pour savoir si A et B ont le même "état" parce qu'ensuite ça coule de source...

 #12 - 23-04-2012 18:12:26

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,474E+3

Electronique en démiineur (u mad bro)

Sauf erreur de ma part, mais je ne trouve pas encore de truc simple pour le OU exclusif...

EDIT erreur de ma part, le 3 du bas ne fonctionne pas. sad

http://www.prise2tete.fr/upload/gwen27-demineurbooleen.jpg

 #13 - 23-04-2012 18:41:25

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3771
Lieu: hébesphénorotonde triangulaire

Electronique en démineur (u mad brro)

Re-bonjour,

Voici un croisement de fils (j(espère que je ne me suis pas trompé coolbig_smile )



Edit : ajout d'un 2ème échangeur de fils, plus simple que le premier...
Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #14 - 23-04-2012 20:16:21

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Electroniquue en démineur (u mad bro)

@Palin01: Je valide les 3 portes NON ET OU.
@gwen27: Oui voila le 3 du bas ne fonctionne pas :p
@Klimrod: Je valide ce croisement de fil! Tu es le premier.

 #15 - 24-04-2012 00:14:15

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

electronique en démineur (u lad bro)

ET :
A1x
    x1B
A'1x

 #16 - 24-04-2012 08:27:30

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3771
Lieu: hébesphénorotonde triangulaire

Electronique en démineur (u mad bro

Bonjour,

La nuit portant conseil, voici ma contribution pour la prime à la simplicité :



A suivre pour les XOR et XAND...
Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #17 - 24-04-2012 08:41:42

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1433

Elctronique en démineur (u mad bro)

(Rouge = mine = vrai; vert = pas mine = faux)

On commence par le NOT, facile
http://www.prise2tete.fr/upload/scarta-logidem_not.png

Puis un tout petit bloc qui fait à la fois le NOR et le NAND
http://www.prise2tete.fr/upload/scarta-logidem_nand_nor.png


On en déduit le AND et le OR
http://www.prise2tete.fr/upload/scarta-logidem_and.png
http://www.prise2tete.fr/upload/scarta-logidem_or.png

Je cherche le croisement de fils

 #18 - 24-04-2012 09:05:40

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Eelctronique en démineur (u mad bro)

@gosidead: Je valide ce ET
@Klimrod: Je valide ces portes en version compacte.
@scarta: Merci pour les petits schémas, et comme tu peux le voir dessus certains "1" du losange n'ont parfois autour d'eux que des "non mines", ce qui invalide pas mal des portes proposées.

NB:Pour toute mise à jour d'image dans un post existant je conseille de changer de nom d'image même si on supprime l'ancienne. (Cache à différents niveaux).

 #19 - 24-04-2012 09:31:27

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1433

electronique en démineur (u lad bro)

AAAArgh
Et dire que j'ai enlevé des cases supplémentaires à côté de chacun de ces 1 en me disant "ça sert à rien au final"...
En remplaçant tous les "1 C 1" verticaux par des "X 1 C 1 Y", ça passe

 #20 - 24-04-2012 10:36:27

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3771
Lieu: hébesphénorotonde triangulaire

electronique en délineur (u mad bro)

Et voilà les portes XOR et XAND :



Fin des devoirs ! wink
Mais j'attends la suite avec impatience... smile
Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #21 - 24-04-2012 12:00:24

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1433

Electronique en dmineur (u mad bro)

Voilà, c'est corrigé.
En remarquant de plus que E=!A.B et F=A.!B dans le NAND/NOR, on peut ajouter le XOR pour avec une toute petite modif supplémentaire et sans avoir a faire une lourde combinaisons de 2 AND et d'un OR

http://www.prise2tete.fr/upload/scarta-logidem_all_v2.png

 #22 - 24-04-2012 14:23:05

LeXav
Habitué de Prise2Tete
Enigmes résolues : 18
Messages : 16
Lieu: Somewhere in Nevada

electronique en sémineur (u mad bro)

Re-Hello

En effet plusieurs erreurs de ma part... hmm
voici un update...
http://www.prise2tete.fr/upload/LeXav-GrilleV3.PNG

En réalité le "NON" est plutôt composé d'une simple succession d'une case indice à 1 et d'une case indéterminée... On ne transmet le signal que via des non...


Xav, Le Xav

 #23 - 24-04-2012 15:55:11

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1433

electronique en déminrur (u mad bro)

Et voici le croisement de fil; obtenu de la manière suivante
http://www.prise2tete.fr/upload/scarta-logidem_cross.png

Explication A XOR (A XOR B) = B. Partant de là, on prend 2 fils horizontaux A et B (disons A en haut); on insère un fil entre les deux qui vaut A XOR B, et avec un XOR entre ce fil et celui du haut on aura B en haut (et vice-versa, A en bas)

 #24 - 24-04-2012 16:00:38

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Eleectronique en démineur (u mad bro)

@scarta: Moi aussi j'avais croisé les fils de cette manière, mais je me doutais qu'il y avait plus compacte et que l'un d'entre vous trouverait. Je pense que klimrod a la version la plus compacte possible.

 #25 - 24-04-2012 16:19:13

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1433

electronique en fémineur (u mad bro)

Oui je pensais bien aussi, mais sans succès. Je voulais faire un additionneur 4 bits mais au vu de la tête du croisement...

Autre question: quelle est la validité de l'inverseur B=!A suivant:

Code:

 C1
A2D
 B

On peut mettre une mine en C ou ne pas en mettre, le résultat sera toujours B=!A.
Du coup, ça me fait penser à NOT non déterministe big_smile

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete