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 - 06-04-2012 22:28:09

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

le démineir

Cela fait un moment que je joue au démineur, et à force de faire des parties je me suis aperçu que toutes les parties ne peuvent être finis, sauf avec de la chance.

J'ai pris un exemple simple que voici :

http://img15.hostingpics.net/pics/394685Dmineur1.png

J'aimerai savoir si il existe une manière de démontrer ou non la conjecture suivante :

Certaines partie de démineur, doivent faire appel à la chance pour être gagnées.

Personnellement je trouve plus judicieux de commencer par les angles, soit je peux avancer la partie parce que j'ai des indices suffisants pour avancer dans le jeu, soit je clique sur un autre parce que je suis bloqué dès le départ.
Mais parfois dans certaine partie, surtout en mode expert, les fins de partie sont insolvables pour une ou deux mines, et seule la chance compte.

Se raisonnement est-il suffisant pour démontrer la conjecture ?
Ou doit-on définir toutes les possibilités de jeu pour savoir ?

Je ne sais ni comment la prouvée, ni comment l'infirmer, ni même savoir si c'est indécidable.
Alors si vous pensez pouvoir éclairer ma logique laconique, je vous en remercie d'avance.


Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
  • |
  • Répondre

#0 Pub

 #2 - 06-04-2012 22:48:26

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 203

Le démmineur

Le jeu fait appel en partie à la chance.

Par exemple, si tu commences par un coin et que tu obtiens le nombre 3 sur ce coin, alors tu sais que le coin est entouré de 3 mines. Mais on n'en sait pas plus, ensuite, c'est forcément de la chance.


Par contre pour l'exemple que tu donnes, il reste encore des choses à faire avant d'y aller au hasard.


Voilà un exemple de fin de partie où il faut avoir de la chance:

http://www.prise2tete.fr/upload/irmo322-demineur_insoluble.jpg

Dans le coin en haut à droite, il doit y avoir 2 mines. Deux configurations peuvent être correctes mais pas moyen de savoir laquelle. Du coup on est obligé de prendre un risque en faisant un clic gauche sur une de ces quatre cases.

 #3 - 06-04-2012 23:00:20

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

Le démieur

Gödel jouait-il au démineur ? lol

 #4 - 07-04-2012 13:09:31

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

Le démienur

Au premier coup il faut bien ne pas tomber sur une mine, donc je dirais plutôt

Toutes les parties de démineur font appel à la chance.

Non ?

 #5 - 07-04-2012 13:47:03

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

le déminrur

Le premier c'est trivial, mais à partir du deuxième ?


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #6 - 07-04-2012 14:46:59

Memento
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 176

le démineut

Si je ne me trompe pas, il est impossible de tomber sur une mine lors du premier coup. tongue

 #7 - 07-04-2012 16:16:07

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3073
Lieu: Au sud du Nord

Le démiineur

Si ça ne t'ai jamais arrivé, c'est que tu as beaucoup de chance


Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)

 #8 - 07-04-2012 16:53:56

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

Le édmineur

Memento a écrit:

Si je ne me trompe pas, il est impossible de tomber sur une mine lors du premier coup. tongue

C'est ce que je crois aussi...

Mais si tu tombes au premier coup sur une case avec un 1 ou un 2, la suite repose forcément sur la chance....


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.

 #9 - 07-04-2012 17:04:22

SHTF47
Imprnnçbl de Prs2Tt
Enigmes résolues : 39
Messages : 1629
Lieu: Autre nom du colin

le démineyr

Pour le métier de démineur, c'est pareil : il y a une part de risque dûe essentiellement au hasard, peu importe les connaissances initiales.

Et je ne ferai pas d'humour noir sur les mines anti-personnel... hmm


La musique est une mathématique sonore, la mathématique une musique silencieuse. [Edouard HERRIOT]

 #10 - 08-04-2012 10:14:37

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

le démineue

Memento a écrit:

Si je ne me trompe pas, il est impossible de tomber sur une mine lors du premier coup. tongue

Si me me souviens bien c'est exact. Au temps ou je jouais a ca sur une machine windows, il y a avait une option de choisir combien de mines et la taille du la grille. En choisssant 99 mines sur une grille 10*10, le premier coup tombait toujours sur la case sans mine.

Ca se programme facilement. Dans le cas normal, le programme gVnere une grille quelconque, et si le premier coup tombe sur une mine, la mine est Vchangée avec une case sans mine.


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

 #11 - 09-04-2012 18:18:35

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

lr démineur

Memento a écrit:

Si je ne me trompe pas, il est impossible de tomber sur une mine lors du premier coup. tongue

Cela signifie t-il que la grille est générée après le premier coup joué ?

 #12 - 09-04-2012 18:21:57

Promath-
Elite de Prise2Tete
Enigmes résolues : 18
Messages : 1416
Lieu: Au fond de l'univers

Le déimneur

Oui, mais elle est juste modifiée un peu (pas toujours)


Un promath- actif dans un forum actif

 #13 - 09-04-2012 18:55:57

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

le démuneur

@Franky :

dhrm77 a écrit:

Ca se programme facilement. Dans le cas normal, le programme génere une grille quelconque, et si le premier coup tombe sur une mine, la mine est échangée avec une case sans mine.


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #14 - 09-04-2012 21:11:13

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

le démineut

Vous allez me prendre pour un fou, mais je vais calculer le nombre de partie total sur un démineur en mode facile pour commencer et essayer de trouver le nombre de partie ou un minimum de chance s'impose.
Je pense qu'il est possible de trouver une méthode qui évite le cas par cas.

Shadock

PS : Pour le nombre de chemins d'un de mes anciennes énigmes, je n'y connais rien en matrice alors peut être que le résultat sera faux, d'autant plus qu'il y a plusieurs (peut-être) trop de paramètre qui entre en jeu.


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #15 - 09-04-2012 21:12:45

Promath-
Elite de Prise2Tete
Enigmes résolues : 18
Messages : 1416
Lieu: Au fond de l'univers

le fémineur

Bonne chance! smile
Surtout courage! wink


Un promath- actif dans un forum actif

 #16 - 10-04-2012 09:00:19

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

Le déminuer

Salut,

J'aimerai savoir si il existe une manière de démontrer ou non la conjecture suivante :
Certaines partie de démineur, doivent faire appel à la chance pour être gagnées.

He bien pour demontrer ce genre de resultat, c'est facile car il s'agit de donner un exemple (alors que si on avait voulu montrer un resultat dans l'autre sens ca aurait ete beaucoup plus dur).
1) On construit un exemple 2) On montre qu'il y a plusieurs répartitions des mines possibles avec l'exemple 3) On montre qu'aucune mine n'est commune à toutes ses répartitions. 4) On conclut donc que les indices ne sont pas suffisants et qu'il faut tenter au hasard pour trancher.

Ps: l'exemple de irmo322 marche très bien.

 #17 - 10-04-2012 09:36:28

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Le démineu

shadock a écrit:

Vous allez me prendre pour un fou, mais je vais calculer le nombre de partie total sur un démineur en mode facile pour commencer et essayer de trouver le nombre de partie ou un minimum de chance s'impose.
Je pense qu'il est possible de trouver une méthode qui évite le cas par cas.

T'as pas fini de te galérer.

Pour le nombre de grilles possibles, c'est de la combinatoire basique, en divisant par 4 (si tu considères que les grilles sont identiques à une rotation près) ou par 8 (si tu considères aussi les symétries).

Pour le reste, euh... Soit tu trouves LA méthode qui déchire, soit tu demandes à un code de faire le sale boulot (ce qui n'est pas forcément simple non plus).


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #18 - 10-04-2012 11:33:21

SHTF47
Imprnnçbl de Prs2Tt
Enigmes résolues : 39
Messages : 1629
Lieu: Autre nom du colin

L edémineur

Il va sans doute falloir programmer un algorithme récursif...

Un peu à la manière d'un code qui recherche la sortie d'un labyrinthe : j'avance dans une direction, je regarde jusqu'où je peux aller, je reviens en arrière si je bloque, etc...


La musique est une mathématique sonore, la mathématique une musique silencieuse. [Edouard HERRIOT]

 #19 - 10-04-2012 16:39:05

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

Le démineu

En fait je remarque que ca pose une question très intéressante:

Peut-on classifier tous les ilots ou le pifomètre est nécessaire?

Il est tout a fait possible qu'il existe un nombre fini de cas locaux faisant intervenir la necessité d'y aller au pif. Un ilot ne serait pas solvable sans pifometre s'il contient un de ces cas locaux "premiers"

Et si cet ensemble de cas locaux n'est pas fini il est peut être facilement énumérable.

Ça c'est une question très intéressante!

Donc je lance la course à la classification pour les courageux:

Trouver tous les types d'ilots de deux cases (avec uniquement 2 cases inconnues) ou le hasard doit intervenir.


Trouver tous les types d'ilots de trois cases (avec uniquement 3 cases inconnues)  ou le hasard doit intervenir.


En fait les cas sont encore plus rare que je ne pensais, donc n'importe quel exemple que vous aurez qui ne soit pas celui déja donné est le bien venu.

Et après on verra si on peut conjecturer.

Pour ne pas polluer ce thread j'ai fait ma classification dans un autre:
Classification des patterns indécidables du démineur :p

 #20 - 10-04-2012 19:13:31

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Le démmineur

FRiZMOUT a écrit:

Au premier coup il faut bien ne pas tomber sur une mine, donc je dirais plutôt

Toutes les parties de démineur font appel à la chance.

Non ?

Je reformule la question différemment :
On prendra si on le souhait la probabilité de tomber sur une case minée du premier coup, plus tard. Notons sans trop de difficulté que celle-ci vaut : [latex]P=\frac{\text{Nombre de mines}}{L*l-1}[/latex]


La question est :
Quelle est la probabilité de finir une partie complète de démineur, de l'étape 2 à l'étape N, sans faire appel à la chance ?

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #21 - 10-04-2012 20:44:43

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

le démineir

Pour ne pas polluer ce thread j'ai fait ma classification dans un autre:
Classification des patterns indécidables du démineur :p

 #22 - 18-04-2012 16:44:59

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

lr démineur

shadock a écrit:

[latex]P=\frac{\text{Nombre de mines}}{L*l-1}[/latex]

Pourquoi -1 ?
(si 100 mines sur grille 10x10 P=1)

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

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

LLe démineur

Parce que le cas d'une grille entièrement remplie avec des mines n'est pas intéressant (on a perdu d'avance), et que si on exclut ce cas-là, alors le premier coup du joueur est toujours sur une case sans mine, ce qui laisse [latex]L*l - 1[/latex] cases restantes...


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.

 #24 - 18-04-2012 19:44:14

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

le démineut

Cela suppose que la grille est (re)générée après le 1er coup. Ce que l'expérience réfute
http://www.prise2tete.fr/upload/Christian91-Capture3.PNG

 #25 - 18-04-2012 20:04:51

Memento
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 176

e démineur

C'est une partie que tu as recommencé ? Car dans ce cas, il est effectivement possible de tomber sur une mine au premier coup. Sinon, cela m'étonne.

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 : 

Si il y a 88 pommes et que vous en prenez 44, combien vous en avez ?

Sujets similaires

Sujet Date Forum
10-04-2012 Blabla
P2T
Difficile mais unique par Clydevil
18-10-2017 Blabla
P2T
05-03-2012 Blabla
P2T
Grand multiple par Franky1103
08-11-2017 Blabla
07-12-2012 Blabla
P2T
Bonne année 2010 par EfCeBa
01-01-2010 Blabla
P2T
Euphorie !! par mitsuidewi
10-02-2011 Blabla
P2T
Un p'tit nouveau... par Barteulbi
01-12-2011 Blabla
P2T
Devine-nombre par Promath-
10-06-2012 Blabla

Mots clés des moteurs de recherche

Mot clé (occurences)
Demineur chance (11) — Demineur impossible (10) — Le demineur (8) — Demineur (8) — Astuce demineur (6) — Jeux coicie java (5) — Demineur 10x10 (4) — Explication algo demineur (4) — Demineur simple (3) — Astuce demineur expert (3) — Demineur expert bloque (3) — Demineur une chance sur deux (3) — Demineur hasard (3) — Demineur part de chance (2) — Astuce pour gagner au demineur (2) — Jouer au demineur (2) — Temps moyen pour finir un demineur expert (2) — Comment gagner jeu demineur expert (2) — Algorithme recursif demineur (2) — Case demineur (2) — Raisonnements possibles dans le jeu le demineur (2) — Demineur insoluble (2) — Qui a gagne au demineur avance (2) — Finir un demineur 99 (2) — 100 mines au jeux demineur difficile (2) — Solution demineur (2) — Algorithme resolution demineur (2) — Bloque demineur (2) — Que faire lorsqu on bloque a demineur (2) — Comme se jou le demineur (2) — Probabilite gagner demineur expert (2) — Etre bloque demineur? (1) — Demineur expert chance ou logique (1) — Jeu demineur pb de hasard (1) — Demineur bloquer (1) — Algorithme demineur (1) — Le hasard dans demineur (1) — Jeu demineur chance (1) — Resolution demineur (1) — Demineur une part d chance (1) — Astuces jeu demineur (1) — Demineur parti impossible (1) — Bloquage situation demineur (1) — Demineur astuces (1) — Que signifie tomber sur une mine (1) — Parties de demineur impossible a finir logiquement (1) — Programme java du demineur simple (1) — Astuces demineur (1) — Demineur insolvable (1) — Langage c demineur avec plusieurs difficult (1) — Astuce demineur moyen (1) — Parfois du hasard au demineur? (1) — Peut ton etre bloque au demineur (1) — Demineur cas insolvable (1) — Probabilites au demineur (1) — Comment faire lorsqu on est bloque au demineur (1) — Grand demineur expert (1) — Demineur cas impossibles (1) — Comment gagner au demineur (1) — Quel algorithme pour le demineur (1) — Demineur expert impossible (1) — Le code source de jeux demineur sur java 2 me (1) — Eviter la chance au demineur (1) — Finir demineur 100 mines (1) — Code jeux demineur java (1) — Code demineur exemple (1) — Exercice probabilite sur le jeu du demineur (1) — Demineur commencer coins (1) — Humour noir demineur (1) — Coup impossible demineur (1) — Java code source demineur simple (1) — Code comment reussir une partie de demineur (1) — Eviter hasard demineur (1) — Bloque demineur expert (1) — Coice demineur (1) — Demineur bloque comment choisir deux cases (1) — Comment trouver une mine dans le jeux demineur (1) — Technique demineur expert (1) — Logiciel de cryptage de case demineur (1) — Demineur partie expert (1) — Revient a trouver un nombre plus petit et un nombre plus grand d un nombre donne math (1) — Finir demineur (1) — Jeu demineur chance hasard (1) — Demineur algorithme (1) — Astuces pour jouer au demineur (1) — Demineur sans hasard (1) — Finir demineur expert (1) — Coder en java le demineur (1) — Demineur en java comment faire (1) — Jeux windows demineur expert hasard ou pas (1) — Comment savoir y un mine dimineur (1) — Impossible demineur expert (1) — Demineur fini (1) — Demineur algorithme matrice (1) — Quelquin a til fini le jeu demineur (1) — Etre bloquer demineur (1) — Jeu demineur bloque (1) — Le demineur raisonnements possible (1) — Finir jeu demineur (1) — Formules pour demineur (1) — Enigme le metademineur (1) — Deemineur (1) — Java demineur fonction calculer le nb de mines autour (1) — Demineur explication logique (1) — Demineur fin de partie (1) — Jeux demineur chance (1) — Demineur 99 mines impossible (1) — Jeu demineur sans hasard (1) — Demineur bloque (1) — Y a t il du hasard au demineur (1) — Ou jouer demineur sans hasard (1) — Demineur en java (1) — Demineur niveau expert forcement une part de chance ? (1) — Solution demineur toutes les parties (1) — Qui a finis le demineur (avance) (1) — Finir demineur expert requiert de la chance ? (1) — Y a til une part de chance au demineur (1) — Comment ne pas etre coince au demineur (1) — Probabilite de gagner au demineur 99 mines (1) — Demineur niveau expert chance (1) — Explication simple code demineur (1) — Astuce demineur mode expert (1) — Toujours une seule solution logique demineur (1) — Demineur jeux possible sans reponse logique? (1) — Demineur sans hasaard (1) — Probabilite premier coup demineur (1) — Proba gagner au demineur (1) — Demineur parfois impossible (1) — Excel demineur 10x10 (1) — Demineur 7 (1) — Deminzur (1) — Simple code java jeu demineur (1) — Nombre de clic minimum demineur (1) — Recursivite jeu demineur en c (1) — Comment commencer une partie de demineur (1) — Chance au demineur (1) — Demineur reussir 99 (1) — Un programme en qui compte le nombre de coups possibles au demineur (1) — Demineur sans chance (1) — Je n arrive pas a tricher au demineur (1) — Formules jeu demineur (1) — Demineur excel (1) — Comment finir rapidement demineur (1) — Demineur solution (1) — Comment savoir trouver les mines demineur modes expert (1) — Resolution demineur comment faire quand hazard (1) — Le hasard et le demineur (1) — Demineur une chance sur 2 (1) — Exemple de demineur (1) — Astuce pour demineur (1) — Demineur expert chance (1) — Demineur mode expert (1) — Demineur que signifie le 0 (1) — Pourquoi je n arrive pas a jouer au demineur (1) — Comment terminer le demineur sans hasard (1) — Bloque au demineur (1) — Solution demineur en fin de partie (1) — Demineur 1 chance sur 2 (1) — Choisir sa partie au demineur (1) — Les probabilites du demineur (1) — Comment fini le jeu de demineur (1) — Deminuer la taille d un pdf small (1) — Demuneur (1) —

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