Classification des patterns indécidables du démineur @ Prise2Tete

Clydevil · #1

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:

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:

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 (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

gwen27 · #2

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é.

Clydevil · #3

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.

gwen27 · #4

Un autre truc : il peut y rester 3 mines .

Clydevil · #5

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)

dhrm77 · #6

Une situation que je rencontrais souvent quand j'y jouait...:

dhrm77 · #7

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.

Clydevil · #8

@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

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

Christian91 · #9

Il faut de la chance pour terminer cette grille. Je ne trouve pas à quel pattern elle correspond.

Un nouveau ?

FRiZMOUT · #10

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

Christian91 · #11

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

medihv · #12

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

Christian91 · #13

Damned ! Quel ballot je suis !

Clydevil · #14

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.

gwen27 · #15

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

Clydevil · #16

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

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 10-04-2012 20:38:43

Classification des patterns indécidable sdu démineur

#0 Pub

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

Classification des pattterns indécidables du démineur

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

Classifciation des patterns indécidables du démineur

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

Classiification des patterns indécidables du démineur

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

Classification des ptterns indécidables du démineur

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

Classification ds patterns indécidables du démineur

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

Classification des pattern sindécidables du démineur

Clydevil a écrit:

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

classificatiin des patterns indécidables du démineur

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

Cllassification des patterns indécidables du démineur

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

Classification des patterns indécidables du déminur

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

Classification des patterns indécidabbles du démineur

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

Classification des patterns indéciadbles du démineur

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

Classification des ppatterns indécidables du démineur

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

Classification des patterns indéidables du démineur

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

Classification des patterns ndécidables du démineur

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

Classification des patterns indécidables du démiineur

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums