Enigme Solitaire en ligne 1/2 @ Prise2Tete

titoufred · #1

Vous connaissez tous le jeu du solitaire, où le but du jeu est de ne laisser qu'une seule bille à la fin. Je vous en propose une version où toutes les billes sont alignées.

Parmi les 10 configurations suivantes, lesquelles permettent de ne laisser qu'une seule bille à la fin en jouant bien (configurations gagnantes) et lesquelles ne le permettent pas, quelle que soit la stratégie employée (configurations perdantes) ?

Une bille est représentée par un O et un emplacement vide entre deux billes par un X. Il y a autant d'emplacements vides que voulus à gauche et à droite des billes extrémales.

1) OOOOOOXXXOOOOOO

2) OOOOOOOOOOOXXO

3) OOOOOOOOOOOO

4) OXOOOOOOOOOOXO

5) OOOOOOOOOOXXOO

6) OOOOXXOOOOXXOOOO

7) OOOXOOOXOOOXOOO

8) OOOOOOXOOOOXOO

9) OOOOXOOXOOOOOO

10) OOOOXOOOOOOXOO

Pour les configurations perdantes, il faudrait trouver un argument démontrant que c'est impossible de ne laisser qu'une seule bille à la fin, quelle que soit la stratégie employée.

De façon générale, sauriez-vous trouver un critère simple permettant de savoir très rapidement si une configuration est gagnante ou perdante ?

nodgim · #2

Je voudrais bien comprendre de problème, mais je ne sais pas quelles règles il faut appliquer pour ôter les billes...
Peux tu préciser ?

titoufred · #3

Ce sont les règles classiques du solitaire : une bille saute par dessus une autre pour l'éliminer du jeu.

Par exemple, de OOXO, on peut passer à XXOO (la bille à gauche passe par-dessus sa voisine, que l'on retire du jeu), puis à XOXX et on a gagné.

On notera plus simplement OOXO => OO => O

Vasimolo · #4

J'avais lu les règles du jeu un peu vite , il n'aurait pas été plus judicieux de noter les billes "O" et les vides "X" ?

J'ai déjà plein de critères gagnant perdant mais rien de simple

Vasimolo

titoufred · #5

Oui, Vasimolo, je me suis dit ça pour les notations après avoir posté.

Donne donc tes conditions nécessaires et tes conditions suffisantes, pour voir sur quoi tu es parti.

Vasimolo · #6

Disons que c'est un peu le bazar , il faudra que j'y réfléchisse un peu plus . L'idée principale : il ne faut pas de trous de plus de 2 cases sinon on obtient des jeux indépendants perdants .

La position gagnante type est 1=OOXO...XOXOX ou 1'=XOXO...XOXOO le pion finissant sa course sur le dernier X .

Les positions OXP ou OOOOXI sont gagnantes si P et I sont des nombres pairs et impairs de pions conjoints . Après les choses se compliquent car on peut très bien remplacer O à gauche par 1 , I par P+1' ou P par I+1' , ...

Vasimolo

PS : désolé , mes O sont des X et réciproquement

titoufred · #7

Aurais-tu une démonstration Vasimolo ?

Allez, j'adopte ta notation.

Nombrilist · #8

Déjà, si deux groupes de pions sont éloignés de 3 cases ou plus, ils ne peuvent pas se rejoindre. Par ailleurs, si l'un des deux groupes ne contient qu'un seul pion, si ils sont éloignés par 2 cases ou plus, ils ne peuvent pas se rejoindre.

titoufred · #9

Oui, Nombrilist, cela donne des conditions nécessaires pour les configurations gagnantes. Du coup, lesquelles des configurations 1 à 10 sont perdantes à coup sûr ? Et pour les autres, que peux-tu dire ?

Vasimolo · #10

Je n'ai pas vraiment de démonstration et avant de suivre plus loin dans cette voie , il semblerait que seules les positions 5 et 10 soit gagnantes , vrai ?

Vasimolo

titoufred · #11

@nodgim : par configs possibles, tu entends gagnantes ? Peux-tu présenter tes solutions pour les configs annoncées gagnantes ?

@Vasimolo : Il faudrait une démonstration pour être sûr...

Vasimolo · #12

Je n'ai aucune démonstration , ce ne sont que des spéculations après quelques essais à la main .

Il n'y aurait que 3 positions gagnantes :

A=OOXOXOX...OX
B=OXP
C=OOOOXI=4XI

et leurs symétriques A' , B' et C' .

Avec l'enchaînement C->B->A->O ( O<-A'<-B'<-C' ) .

donc si R désigne le reste de la suite AR->OR , BR->OXR et CR->OXR ( même chose pour les ' que je ne détaille plus ) . Après on réduit en partant des 2 extrémités de la chaîne en respectant les priorités A puis B puis C , si on aboutit à "O" on a gagné .

La méthode est sûrement facile à programmer mais permet-elle de détecter toutes les positions gagnantes ? Rien n'est moins sûr

Vasimolo

nodgim · #13

Ce que j'ai présenté est insuffisant.
Je revois ça.

Nombrilist · #14

Les 1, 2 et 7 sont perdantes à coup sur. La 3 est injouable.

titoufred · #15

@Nombrilist : Ok pour la 1 et la 2.

Pour la 3, tu as des espaces de part et d'autre des billes, en fait c'est

3) XXXXOOOOOOOOOOOOXXXX

Pour la 7 peux-tu préciser ?

@Vasimolo : Penses-tu qu'il est possible de gagner en enchainant plusieurs configurations B ou C ?

Vasimolo · #16

Non , on ne peut pas vraiment enchaîner les configurations car il faut bien suivre à chaque réduction où atterrit le pion "rescapé" . J'essaierai de joindre un dessin dans la journée mais je répète que je ne suis pas du tout convaincu d'avoir toutes les solutions

Vasimolo

Vasimolo · #17

Une illustration :

On voit par exemple qu'on peut remplacer le pion gauche de B ou de C par "A=OOXOXOXOX" ou le pion droit par "A'=XOXOXOXOXOO" , il y a pas mal de variantes je n'ai pas réussi à synthétiser tout ça . Ca a l'air un peu compliqué mais je n'ai pas de contre-exemple à la réduction que j'ai donnée .

Vasimolo

titoufred · #18

Du coup, comment reconnaitre assez rapidement une configuration gagnante ?

Et pour dissiper les derniers doutes, je pense qu'une petite démonstration s'impose non ?

nodgim · #19

La 1ère partie de la question semble peu accessible si au préalable on n'établit pas d'abord les configurations possibles à partir du pion unique, c'est à dire de réaliser l'opération inverse de suppression des pions.

Le mécanisme inverse revient à cette simple opération élémentaire:
100 ----->011.
Un pion en créé 2 voisins tandis que lui disparait.

Créons 4 pions en exemple à partir d'un 1er:
1
011
01011
110011
111101

On est assez vité amené à se rendre compte qu'on peut créer des pions en 4 endroits seulement que l'on nommera 1,2,3,4.
Le 1 à gauche du segment, le 4 à droite du segment.
1: 0011---->1101
4: 1100---->1011
et lorsqu'il existe un espace de 2 vides à l'intérieur d'un segment:
2: 110011---->101111
3: 110011---->111101

On peut avec ces notations recréer un segment simplement par la suite des nombres 1 à 4 écrits dans l'ordre.
Par exemple 11142:
11
1101
110101
11010011
11001111

On ne peut bien sûr pas écrire une suite dans n'importe quel ordre, il y a des contraintes:
-Avant d'écrire un 2 ou un 3, il est obligatoire d'avoir au moins 3 nombres 1 ou 4 , dont au moins 1 de chaque.
-On ne peut écrire une suite de 2 ou 3 supérieure respectivement aux 1 ou 4 moins une unité.
-Quand on a écrit un ou plusieurs 2, on ne peut écrire qu'un seul 3, et vice versa.

Compte tenu de ces contraintes les configurations possibles sont assez limitées, elles sont listées ci après:
Po1
Ioo2
Io4
2oPoo2
2ooIo2
1oIo2
4oPo2
2o3oIo2

P est une suite ininterrompue paire de pion, I une suite impaire, o est un vide, et un chiffre représente le nombre de pions consécutifs.
A cela, un chiffre 2 d'extrémité peut être allongé par une suite alternée de 1
2.....------>2o1o1o1o..... ou ......2----->.....o1o1o1o12.

Toutes les configurations qui n'entrent pas dans cette liste ne sont pas issues d'un pion unique, on ne peut aboutir à un résultat gagnant.

titoufred · #20

@nodgim : Bonne idée au départ, mais la liste des configurations gagnantes que tu donnes n'est pas la bonne. Par ailleurs, il serait intéressant d'apporter des preuves à ce que tu avances.

Nombrilist · #21

Pour la 7, dès que l'on a joué un coup, il se trouve forcément un pion isolé par deux cases d'un autre groupe de pions. Donc, on ne peut pas gagner.

titoufred · #22

@Nombrilist : Oui mais ce n'est pas forcément un pion isolé extérieur comme dans la 2. Il peut encore "recevoir du renfort" de l'autre côté par un 3ème groupe.
Par exemple sur OOXXOXOO, on arrive à gagner.

Vasimolo · #23

@Nodgim : il est clair qu'il y a plein de configurations gagnantes par répétitions des formules à gauche et à droite symétriquement . On doit pouvoir réduire tout ça à quelques formules élémentaires éventuellement répétées mais tout ça ne nous dit pas comment reconnaître facilement une position gagnante .

Je trouve Titou un peu en retrait sur ce coup

Vasimolo

nodgim · #24

Oui en fait il y a bien des configs fausses, Titoufred a raison.

On peut se contenter de 2 configs types, qu'on doit pouvoir retrouver facilement depuis n'importe quelle config présentée: Po1 et Io4.

Pour les exemples de l'énoncé:

1) OOOOOOXXXOOOOOO
6ooo6 : il est impossible de créer un espace de 3 vides consécutifs.

2) OOOOOOOOOOOXXO
Ioo2: l'intervalle a une longueur impaire, c'est impossible.

3) OOOOOOOOOOOO
Pas d'intervalle, c'est impossible

4) OXOOOOOOOOOOXO
1oPo1: impossible d'obtenir Po1, et ne vient pas de Po1. Ou encore il est impossible d'être encadré par 2 jetons isolés.

5) OOOOOOOOOOXXOO
Poo2 vient de Po1 donc OK

6) OOOOXXOOOOXXOOOO
il y a 2 intervalles de 2 vides, impossible, 1 seul max.

7) OOOXOOOXOOOXOOO
3o3o3o3: longueur impaire, impossible.

8) OOOOOOXOOOOXOO
Po4o2 vient de Po5, on ne peut avoir 2 intervalles de jetons >4.

9) OOOOXOOXOOOOOO
4o2oP vient de 5oooP, intervalle 3 vides donc impossible.

10) OOOOXOOOOOOXOO
4oPo2 vient de 4oI donc OK.

Les façons d'éliminer les configs non conformes sont donc assez diverses....

Vasimolo · #25

Je crois que j'ai réussi à lister toutes les configurations gagnantes ( à vérifier ) :

[latex]A ,AA' ,AXIA' , AOOOXPA' , APXOOOO , AXP , AOOOXI , OXP[/latex] et [latex]OOOOXI[/latex] ainsi que leur "inverses" ce qui donne 17 configurations possibles .

Je note toujours :

[latex]A=OOXOXOX...OX[/latex] , [latex]A'=XO...XOXOXOO[/latex] , [latex]P[/latex] et [latex]I[/latex] une succession paire ou impaire de pions .

Vasimolo

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 - 25-04-2014 12:14:36

Soltaire en ligne

#0 Pub

#2 - 25-04-2014 18:22:04

solitaire en logne

#3 - 25-04-2014 19:14:47

soliraire en ligne

#4 - 25-04-2014 19:18:49

Solitaire enn ligne

#5 - 25-04-2014 19:40:18

dolitaire en ligne

#6 - 26-04-2014 11:42:06

solitaire en ligbe

#7 - 26-04-2014 13:26:06

solotaire en ligne

#8 - 26-04-2014 15:24:27

Solitaire en lige

#9 - 26-04-2014 15:34:09

qolitaire en ligne

#10 - 26-04-2014 18:25:40

Soitaire en ligne

#11 - 26-04-2014 18:47:45

solitaire eb ligne

#12 - 26-04-2014 19:18:19

solitaire en lifne

#13 - 26-04-2014 19:28:15

Solitairee en ligne

#14 - 27-04-2014 22:41:34

solitaire zn ligne

#15 - 28-04-2014 00:14:26

oSlitaire en ligne

#16 - 28-04-2014 11:43:32

solitzire en ligne

#17 - 28-04-2014 19:12:15

Soliitaire en ligne

#18 - 28-04-2014 21:05:21

solitzire en ligne

#19 - 29-04-2014 18:10:44

qolitaire en ligne

#20 - 29-04-2014 23:30:58

Solitairee en ligne

#21 - 30-04-2014 08:08:24

Solitair en ligne

#22 - 30-04-2014 15:19:03

Solitaier en ligne

#23 - 30-04-2014 18:44:08

Solitarie en ligne

#24 - 01-05-2014 08:47:55

solitaire en logne

#25 - 01-05-2014 11:00:09

Solitare en ligne

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums