Enigme Echecs 18 1/2 @ Prise2Tete

Vasimolo · #1

En ce moment j'ai un peu tendance à délaisser mes gâteaux pour mes grilles

Deux joueurs s'affrontent sur un échiquier 11X11 . Ils placent tour à tour un jeton blanc sur une des cases . Le premier qui arrive à former un rectangle parallèle au quadrillage avec les jetons posés gagne la partie .

Ici le joueur qui a joué en deuxième a gagné .

Mais quelle est la stratégie gagnante ?

Vasimolo

golgot59 · #2

Bon, allez, je vais oser m'attaquer à un de tes problèmes Vasimolo...

Je vais chercher, je te poste mes résultats dès que j'en ai (si j'en ai)

Vasimolo · #3

Vas-y sans complexe , la solution ne nécessite rien d'autre qu'un peu de logique et beaucoup d'astuce .

Pour tous , la solution est très abordable

Vasimolo

titoufred · #4

Le premier joueur J1 possède une stratégie gagnante en procédant de la sorte :

Il joue son premier coup n'importe où, puis après un coup de J2 :

Stratégie gagnante de J1 :

-si J2 joue sur une case perdante (j'appelle case perdante une case qui donne immédiatement la victoire à l'autre joueur au coup suivant) : conclure.

-si J2 joue sur une case dont la ligne et la colonne sont vides (coup de type 1) : Jouer sur une case similaire.

-si J2 joue sur une case dont la ligne(resp. colonne) a déjà été jouée (coup de type 2): Jouer sur la même ligne(resp. colonne) que J2, dans une colonne(resp. ligne) vierge.

Un exemple de début de partie sur un échiquier 7x7 :

*00**00
*00**00
**7****
**6****
**3****
*2***00
1**4500

Les cases perdantes sont en *, les non perdantes en 0

Pour expliquer pourquoi ça marche :

Quitte à réarranger les lignes/colonnes lors des coups de type 1, on peut former une diagonale avec les coups de type 1. Ceci définit le carré interdit (sur l'exemple, le carré 3x3 des coups 1,2,3). A l'opposé de ce carré, il y a le carré vierge (sur l'exemple le carré 4x4 où aucun coup n'a été joué), là où seront joués les prochains coups de type 1. Sur les côtés, il y a 2 rectangles où seront joués les coups de type 2 : Le rectangle des lignes (sur l'exemple le rectangle 4x3 des coups 4,5) où J1 joue sur la même ligne que J2, et le rectangle des colonnes (sur l'exemple le rectangle 3x4 des coups 6,7) où J1 joue sur la même colonne que J2.

Toutes les cases du carré interdit sont perdantes. Dans le rectangle des lignes(resp colonnes), les cases jouées définissent des colonnes(resp lignes) entières de cases perdantes, y compris en dehors du rectangle. Par exemple le coup 4 définit deux colonnes de cases perdantes : celle du coup 4 et celle du coup 1. Toutes les autres cases sont non perdantes.

On vérifie par récurrence que :

*Après un coup de J1 :

le carré interdit est de côté impair, le rectangle des lignes a un nombre pair de colonnes vierges, le rectangle des colonnes a un nombre pair de lignes vierges.

*Après un coup de J2 :

-si c'est un coup de type 1 : le carré interdit est de côté pair, le rectangle des lignes a un nombre impair de colonnes vierges, le rectangle des colonnes a un nombre impair de lignes vierges. Ceci assure que J1 pourra rétorquer un coup de type 1, car il reste au moins une case non perdante dans le carré vierge.

-si c'est un coup de type 2 : le carré interdit est de côté impair. Si J2 a joué dans le rectangle des lignes, celui-ci a un nombre impair de colonnes vierges. Ceci assure qu'il reste au moins 1 colonne vierge dans le rectangle des lignes, et donc que J1 pourra rétorquer un coup non perdant dans le rectangle des lignes. Idem pour le rectangle des colonnes.

gwen27 · #5

Je pars du principe que j'ai deux cases voisines de ma couleur et que les autres dans le carré de 3x3 sont vides au moment où c'est à moi de jouer...
(ce sont les cases marquées 0 )

Mon coup 1 amène au coup 1 des jaunes, idem pour le coup 2 et le coup 3 est gagnant.

Bon, il me faut donc 2 coups d'avance.

Au début du jeu, si le second joueur me "bloque" ce réseau, il suffit de reporter la stratégie sur un pavage de maille double en vertical et j'ai donc bien les deux cases 0
Si au second coup, il me bloque encore, je recommence à chercher un pavage plus large pour le coup 1 en horizontal. et là c'est imparable.

nodgim · #6

Oui c'est assez facile.
Si on fait le décompte de l'occupation des lignes et des colonnes à chaque pose de jeton, donc à (11,11) au départ, le 1er qui joue s'arrangera pour renvoyer toujours un couple de pairs à l'adversaire.
(11,11) --->(10,10) après jeton de A.
Si B joue (10,9), donc son jeton aligné avec le 1er, on répondra (10,8) donc aligné aussi.
Si B joue (9,9) A répondra par (8,8)
Etc...

Vasimolo · #7

Que des bonnes réponses

Il y a une façon très simple d'expliquer la stratégie gagnante avec un argument de parité , ce qu'a bien vu Nodgim .

Vasimolo

golgot59 · #8

J'ai du mal à expliquer, mais je dirais qu'il faut jouer "comme l'adversaire" :

Si il se place sur une ligne et colonne vierge, alors il faut faire pareil, et de même si il ne se met que sur une ligne vierge mais une colonne occupé, ou inversement.

titoufred · #9

J'ai un peu de mal avec la stratégie de nodgim : "le premier s'arrange pour renvoyer un (pair, pair)". Déjà telle qu'énoncée, la stratégie n'est pas suffisante, si on se contente de faire ça on peut perdre. Il faut rajouter qu'à la première occasion de gagner, il faut conclure. Et puis,

1) Est-ce si évident qu'on peut toujours renvoyer un (pair, pair) ?

2) Et même si on le fait, l'adversaire ne peut-il pas gagner ?

Vasimolo · #10

Les coups possibles pour le joueur 2 .

1°) Il joue sur une ligne et une colonne jamais utilisée .
2°) Il joue sur une ligne déjà utilisée mais pas la colonne
3°) Il joue sur une colonne déjà utilisée mais pas la ligne .
4°) Il joue sur une ligne et une colonne déjà utilisée .

Réponses du joueur 1 :

1°) Il fait exactement pareil .
2°) Il joue sur la même ligne sur une colonne jamais utilisée .
3°) Il joue sur la même colonne et sur une ligne jamais utilisée .
4°) Il fait exactement pareil et gagne .

On voit bien comment fonctionne la parité sur les lignes et les colonnes .

Vasimolo

titoufred · #11

Ok, mais quand il fait un coup de type 4°), ne peut-il pas remporter la victoire avec ce coup ?

Comment prouve-t-on que cette stratégie mène à la victoire ?

Vasimolo · #12

Tu remarqueras que le joueur 1 ne prend jamais l'initiative de jouer sur une ligne et une colonne déjà jouées or pour gagner il faut que deux joueurs exactement l'aient fait .

Vasimolo

titoufred · #13

Je ne suis pas d'accord avec ta phrase.

Un rectangle peut se faire comme ça :

12
34

Ici le premier coup du type 4°) remporte la victoire.

Vasimolo · #14

Tu ne respectes pas la stratégie du joueur 1 , il ne doit pas jouer le coup 3 .

Vasimolo

titoufred · #15

123
56
4

Je sais bien que J1 aurait pu jouer 5 ailleurs pour gagner, mais je dis que ta phrase "pour gagner il faut que deux joueurs exactement aient joué un coup de type 4°)" n'est pas vraie en général. Et d'ailleurs, ce n'est pas à moi de prouver que J2 peut gagner, mais à toi de prouver que J1 va gagner. Pour l'instant, je ne comprends sincèrement pas pourquoi.

Vasimolo · #16

Bon j'ai voulu aller trop vite mais il est clair que l'argument de parité suffit pour conclure , je vais essayer de détailler un peu plus .

J1 joue n'importe où puis :

1°) J2 joue sur la même ligne ou la même colonne que J1 alors toute case de ces colonnes ou lignes ( attention à l'inversion ) deviennent inutilisables sous peine de défaite immédiate on peut donc retirer ces colonnes ou lignes du jeu .

2°) J2 joue sur une nouvelle ligne et une nouvelle colonne alors J1 fait de même .

Il est clair que J1 ne peut pas perdre avec cette stratégie alors J2 va devoir jouer sur une case interdite .

Vasimolo

titoufred · #17

Vasimolo a écrit:
1°) J2 joue sur la même ligne ou la même colonne que J1 alors toute case de cette colonne ou ligne ( attention à l'inversion ) devient inutilisable sous peine de défaite immédiate on peut donc les retirer du jeu .

"cette colonne" se réfère à la colonne du coup où vient de jouer J2 ?

Vasimolo · #18

En fait c'est les deux , je corrige !

Vasimolo

titoufred · #19

Bon finalement, ce n'était pas si simple que ça, on en revient un peu à mon message non ?

Vasimolo · #20

En effet

L'idée est assez intuitive mais la justification un peu laborieuse !

Vasimolo

nodgim · #21

Je ne comprends pas trop le problème de Titoufred, l'argument de parité que j'avais avancé serait il mis en défaut ?

titoufred · #22

Quel argument de parité ?

Qu'est-ce que tu affirmes au juste ?

La question initiale est "Quelle est la stratégie gagnante ?". Quelle stratégie proposes-tu, clairement et de façon complète ?

nodgim · #23

nodgim a écrit:
Oui c'est assez facile.
Si on fait le décompte de l'occupation des lignes et des colonnes à chaque pose de jeton, donc à (11,11) au départ, le 1er qui joue s'arrangera pour renvoyer toujours un couple de pairs à l'adversaire.
(11,11) --->(10,10) après jeton de A.
Si B joue (10,9), donc son jeton aligné avec le 1er, on répondra (10,8) donc aligné aussi.
Si B joue (9,9) A répondra par (8,8)
Etc...

ça me semble clair pourtant.
Peut être aurais je dû ajouter la conclusion: si B joue sans faire tourner le compteur, il perd car il joue sur 1 ligne et 1 colonne occupée, A n'a plus qu'à jouer pour terminer le rectangle.

titoufred · #24

Oui, tu aurais dû ajouter ça.
Mais pas que.
Là tu donnes le deuxième coup de A.
Mais qu'en est-il de suivants ?
Quelle stratégie proposes-tu, clairement et de façon complète ?

nodgim · #25

La réponse de A est toujours de renvoyer un couple de pairs: Si B propose un couple de pairs, A joue derrière une case à colonne et ligne vide. Si B renvoie un couple à une ligne ou une colonne impaire, A joue dans une ligne ou une colonne déja occupée pour rétablir la parité.

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 - 19-10-2012 18:58:46

echexs 18

#0 Pub

#2 - 20-10-2012 19:37:45

Ecehcs 18

#3 - 20-10-2012 20:20:23

Echesc 18

#4 - 20-10-2012 23:10:15

EEchecs 18

#5 - 21-10-2012 09:22:37

Echecs 188

#6 - 21-10-2012 09:41:10

echzcs 18

#7 - 21-10-2012 11:47:16

checs 18

#8 - 21-10-2012 12:59:37

Ecchecs 18

#9 - 12-11-2012 03:47:56

ecjecs 18

#10 - 12-11-2012 12:39:49

Echecs 118

#11 - 12-11-2012 13:24:57

Echeccs 18

#12 - 12-11-2012 15:43:02

Echhecs 18

#13 - 12-11-2012 16:31:02

Echeecs 18

#14 - 12-11-2012 17:32:43

evhecs 18

#15 - 12-11-2012 17:48:02

echecq 18

#16 - 12-11-2012 23:01:10

cEhecs 18

#17 - 12-11-2012 23:10:34

Eches 18

Vasimolo a écrit:

#18 - 12-11-2012 23:14:16

checs 18

#19 - 13-11-2012 00:18:45

Echhecs 18

#20 - 13-11-2012 17:51:10

Echeecs 18

#21 - 13-11-2012 18:30:33

zchecs 18

#22 - 13-11-2012 21:17:00

Echhecs 18

#23 - 14-11-2012 18:26:27

Echecs 81

nodgim a écrit:

#24 - 14-11-2012 18:34:44

Echecs 188

#25 - 14-11-2012 19:04:49

Echec 18

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums