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 - 10-04-2012 20:38:43

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

Classification des patterns indéciadbles du démineur

Hello,

Suite au post sur le démineur ICI et à ma remarque annexe j'avais envie de commencer à classifier tous les patterns indécidables du démineurs :p

Histoire de poser les choses quelques mots réservés:

Indécidable: un pattern est indécidable lorsque, sans l'information du nombre de mines qui le composent, il y a plusieurs configurations possibles des mines satisfaisant les indices.

Irréductibles: un pattern est irréductible lorsqu'aucune des cases de type "non découverte" ne peut être déduite être une mine ou ne pas en être une.

Connexe: un pattern est connexe lorsqu'on peut aller de n'importe quelle case de type "non découverte" à n'importe quelle autre case de même type en ne passant que par des cases de même type une à une voisine par un bord.

Dégénéré: un pattern est dégénéré lorsqu'il nécessite une taille particulière de grille.

Voici si je ne fais pas erreur tous les patterns connexes irréductibles non dégénérés faisant intervenir 1 et 2 cases mine déjà identifiées:

http://www.prise2tete.fr/upload/Clydevil-MinePatterns2-3.png

Code couleur:

Vert = on ne sait pas.
Rouge = mine.
Noir = ne fait pas partie de la grille (bord)
Gris = indépendant du pattern (ce qui ne veut pas dire "n'importe quoi")

Attention aux pièges:

http://www.prise2tete.fr/upload/Clydevil-MinePatternsInvalid.png
Le pattern ci dessus n'est pas irréductible, on peut déduire certaines cases vertes.

A mon grand étonnement il n'y avait pas de forme "générique", je veux dire que si on prend le seul pattern faisant intervenir une seule case mine (en haut a gauche de la grosse image) on pourrait imaginer que faire varier la taille du rectangle vert puisse en donner d'autres indécidable, et bien non, c'est le seul avec un rectangle. (irréductible connexe et une seule case mine)

Si vous voulez continuer cette classification feel free :p
Le premier qui trouve une famille de patterns irréductibles connexes indécidables a le droit à mon respect smile (ie une forme ou certaines des dimensions sont paramétrables ce qui présenterait l’intérêt de démontrer qu'il n'y a pas un nombre fini de patterns irréductibles indécidables)

Pour faire mumuse avec la même grille et code couleur que moi, un png vierge ici:
http://www.prise2tete.fr/upload/Clydevi … dEmpty.png



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 10-04-2012 20:50:58

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

classification des patterns ibdécidables du démineur

De mon point de vue, le premier n'est pas indécidable déjà et de même pour d'autres car il ne prend pas en compte la connaissance préalable du nombre de mines.

Il le devient s'il est doublé.

 #3 - 10-04-2012 20:54:55

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

Classification des patterns indécidalbes du démineur

Je vais rajouter cette précision dans la définition d’indécidable, c'est une propriété intéressante oui.
On remarquera que même si on dit qu'il reste 2 mines il est indécidable. Mais si on sait qu'il n'en reste qu'une il ne l'est plus C'est plus commode dans un premier temps de ne pas faire intervenir l'indice du nombre de mine restante dans l'indécidabilité. Après on pourra raffiner.

 #4 - 10-04-2012 21:09:34

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

Classification des patterns indécidabbles du démineur

Un autre truc : il peut y rester 3 mines .

 #5 - 10-04-2012 21:19:38

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

Classificatio ndes patterns indécidables du démineur

Ha alors ça souligne que je n'ai pas été clair dans l'intitulé,  lorsque je dis que le pattern fait intervenir une ou deux cases mines je veux dire dans le pattern et non au total. (ie 1 ou 2 cases rouges)  Je vais reformuler. (Il fallait bien commencer la classification sur un critere j'ai arbitrairement choisi celui la)

 #6 - 12-04-2012 02:16:07

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

Classificatio ndes patterns indécidables du démineur

Une situation que je rencontrais souvent quand j'y jouait...:
http://www.prise2tete.fr/upload/dhrm77-mine3.PNG


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #7 - 12-04-2012 02:22:31

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

clzssification des patterns indécidables du démineur

Clydevil a écrit:

Le pattern ci dessus n'est pas irréductible, on peut déduire une des cases vertes.

En fait les quatres cases vertes de gauche sont deduisibles.
Avec un 3 au lieu du 4, par contre, aucune case n'est deduisible.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #8 - 12-04-2012 08:56:02

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

Classification des patterns indécidables ud démineur

@dhrm77: Oui tout a fait d'accord. Avec un 3 au lieu du 4 il est dans mon début de classification juste au dessus. J'ai continué et j'ai trouvé de sacré monstres, j'en ferais sans doute une enigme big_smile

Merci pour l'élément à ajouter dans la classification.

 #9 - 18-04-2012 17:32:05

Christian91
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 89
Lieu: 91

clasqification des patterns indécidables du démineur

Il faut de la chance pour terminer cette grille. Je ne trouve pas à quel pattern elle correspond.
http://www.prise2tete.fr/upload/Christian91-Capture2.PNG
Un nouveau ?

 #10 - 18-04-2012 17:41:37

FRiZMOUT
Verbicruciste binairien
Enigmes résolues : 49
Messages : 2211

classification des pztterns indécidables du démineur

Non, il n'y a qu'une seule solution possible. Pas besoin de chance, juste de la réflexion lol

 #11 - 18-04-2012 18:08:11

Christian91
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 89
Lieu: 91

Classification des patteerns indécidables du démineur

Je trouve 2 solutions (chacune correspondant au choix de la 4e mine autour du 4).
Na !

 #12 - 18-04-2012 18:10:02

medihv
Professionnel de Prise2Tete
Enigmes résolues : 47
Messages : 123

classification des patterns indécidables du démibeur

Non, non, Friz a raison. N'oublie pas de prendre en compte le nombre de mines qu'il te reste à placer wink

 #13 - 18-04-2012 18:21:24

Christian91
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 89
Lieu: 91

Classification des patterns indécidables du déminneur

Damned ! Quel ballot je suis !

 #14 - 18-04-2012 18:25:38

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

classification des patterns insécidables du démineur

Salut, oui la forme fait partie de la suite de la classification (qui ne tient pas compte du nombre de mines restantes, mais c'est vrai que dans ton cas tu peux finir) car ta forme de coin demande au moins 3 mines visible autour du rectangle et je n'ai classifier que les cas à 2 mines visibles.

 #15 - 18-04-2012 19:51:42

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

Classification des pattersn indécidables du démineur

On peut aussi en imaginer au centre de la grille, là, en partant de l'exemple de dhrm77

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

 #16 - 18-04-2012 23:22:05

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

Classification des patterns indécidables du déémineur

Oui tout à fait.
J'ai découvert tout un tas de truc d'une geekerie rare, je vous réserve cela en énigme dans le forum maths. D'abord de simples grilles à remplir et bientôt des défis de construction 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 : 

Dans une course, vous doublez le 31ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
P2T
Le démineur par shadock
06-04-2012 Blabla
P2T
La fOOOlle journée ! par maïtou22
11-04-2009 Blabla
30-01-2016 Blabla
05-09-2008 Blabla
P2T
30 ans déjà ... par Arrakis
08-12-2010 Blabla
14-05-2012 Blabla
P2T
Merci pour ces énigmes par zecalamar
05-10-2010 Blabla
22-05-2014 Blabla
P2T
05-04-2008 Blabla

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