Discussion :

[kosted]

Bonjour à tous, je suis entrain de réaliser un jeu de plateau et je fais face à une difficulté que je n'arrive pas à surmonter .

En gros, pour implémenter mon plateau, j'ai un tableau à deux dimensions (voir image) et chaque case contient un nombre de pions (0 à max 32). Lorsqu'on récupère les pions d'une case et qu'on se déplace (suivant le sens contraire des aiguilles d'une montre), on dépose un pion par case suivant : par exemple, si je prends les pions de la 00 (donc 3), je vais déposer un pion en 1-0 (qui devient donc 2), un autre en 1-1 (qui devient donc 1) et ainsi de suite. Le dernier pion que je dépose (donc dans l'exemple précédent en 1-2), si il y a 0 pion en 1-2, alors je ne dépose pas le pion en 1-2 mais en 1-3 et j'incrémente 1-3 (5). Si il y a un pion comme c'est le cas sur le schéma, je dépose en 1-2 (qui devient 2), puis je prends les 2 pions et je continue, je dépose un en 1-3 et le dernier en 1-4 (parce que 1-4 n'est pas vide (sinon j'aurais déposé en 1-6 : je me suis trompé j'ai mis 8 sur le schéma au lieu de 6), et 1-4 devient 5) et je continue.

Ce que je veux faire c'est d'arriver, à avoir un algo qui puisse me permettre d'avoir le dernier pion en 0-5 peu importe le nombre de tour que ça peu prendre. Par exemple je sais que en un coup je peux prendre les pions en 1-7, mettre un en 0-7,un autre en 0-6, et le dernier en 0-5 (et je gagne). Cependant, il peut nécessiter plusieurs déplacement avant d'y arriver et c'est cet algo que je n'arrive pas à faire.

Votre aide me serai d'une grande utilité

[tbc92]

J'ai peut-être raté un truc, mais voici mon approche.
Si j'ai bien compris, on a une situation initiale qu'on subit. (dans l'exemple, tu as 3 pions dans la case (0,0) etc etc)

Si tu choisis de commencer par la case (0,0) par exemple, toute la suite de la partie est déterminée. Et effectivement, la partie peut être très longue.
Et idem, quelle que soit la case départ choisie.

Tu dois donc explorer les 16 scénarios en parallèle.
Pour chacune des 16 cases de départ possibles, quelle est la situation après 1 mouvement, après 2 mouvements, etc etc, jusqu'à ce qu'un des 16 scénarios donne le résultat voulu.

[kosted]

J'ai peut-être raté un truc, mais voici mon approche.
Si j'ai bien compris, on a une situation initiale qu'on subit. (dans l'exemple, tu as 3 pions dans la case (0,0) etc etc)

Si tu choisis de commencer par la case (0,0) par exemple, toute la suite de la partie est déterminée. Et effectivement, la partie peut être très longue.
Et idem, quelle que soit la case départ choisie.

Tu dois donc explorer les 16 scénarios en parallèle.
Pour chacune des 16 cases de départ possibles, quelle est la situation après 1 mouvement, après 2 mouvements, etc etc, jusqu'à ce qu'un des 16 scénarios donne le résultat voulu.

Oui mais le problème qui se pose, est que je ne sais pas comment calculer ces déplacements. En gros, je n'arrive pas à imaginer, un algo qui puisse me permettre de me déplacer en faisant ce que j'ai décrit oralement et que tu as dis.

[picodev]

Bonjour,

Je pars du principe qu'il y a 32 pions sur le plateau.
Dans un premier temps je te propose de numéroter les cases. Par exemple on peut partir sur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
num(line, col) = |col   , if line=0
                 |15-col, if line=1

Cela te donne comme numérotation :

0	1	2	3	4	5	6	7
15	14	13	12	11	10	9	8

Si les déplacements se font dans le sens antihoraire, la case suivante est donnée par next(n)=(n+15) modulo 16 et la précédente parprev(n)=(n+1) modulo 16. Cette représentation et ces formules sont facilement généralisables pour des plateaux de longueur quelconque.

Il te suffit d'avoir peu de primitives pour construire les algos ensuite.

[Flodelarab]

Bonjour

Reprenons le formalisme de Picodev.

La question est de remplir la case numéro 5 avec le dernier pion.

J'aurais tendance à remonter le courant en partant de la solution.
Si on veut le dernier en 5 c'est qu'il y avait 1 dans 6 ou 2 dans 7 ou 3 dans 8.... etc.
Tu peux construire un arbre qui donne toutes les positions gagnantes.
Et tant que les situations gagnantes trouvées ne correspondent pas à ta situation initiale, l'arbre pousse.

L'algo s'arrête quand il a trouvé ou quand le temps imparti est écoulé.

[tbc92]

Bonjour

Reprenons le formalisme de Picodev.

La question est de remplir la case numéro 5 avec le dernier pion.

J'aurais tendance à remonter le courant en partant de la solution.
Si on veut le dernier en 5 c'est qu'il y avait 1 dans 6 ou 2 dans 7 ou 3 dans 8.... etc.
Tu peux construire un arbre qui donne toutes les positions gagnantes.
Et tant que les situations gagnantes trouvées ne correspondent pas à ta situation initiale, l'arbre pousse.

L'algo s'arrête quand il a trouvé ou quand le temps imparti est écoulé.

Ca marche, mais c'est inapplicable.
Si on parcours l'arbre 'dans le sens chronologique de déroulement de la partie', on a 16 arbres à parcourir, et chaque arbre a une seule branche ( c'est essentiel comme information)
Et kosted nous demande de l'aide pour cet exercice que je considère comme très simple.

Si on déroule l'arbre dans l'autre sens, comme tu le proposes, en partant de la situation finale, alors on a un arbre qui est exponentiel, avec tout ce que ça sous-entend en difficulté d'implémentation.

[picodev]

Ce que propose FloDelArab permet néanmoins un check rapide si une solution en un coup existe (il faut juste penser au cas des cases à 0). On peut ensuite embrayer sur une recherche récursive d'autres solutions.

[kosted]

Je me suis basé sur ce que vous avez dis, et j'ai fais cet algo que je dois répéter pour chaque case (0,0), (1,0),(0,1)...jusqu'à trouver la case qui permet de réussir. Dans l'algo j'ai limité le nombre de tour à 3, mais bon, on peut le modifier à 10 ou N.
Vous en pensez quoi ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
Algorithme :
 
	Soit cd = case de départ choisi pour lancer l'algo (On peut tester avec 0,0)
		 ct = case temporaire
		 cg = case où doit tomber le dernier pour gagner le jeu
 
		 trouver <- false; nbTour <- 0; //le nombre de tour est quand on fait un tour complet sans réussir
		 tableauTemp[8][8] <- tableauPlateau[8][8]; //on copie le tableau initial pour ne pas le modifier
 
		 	indiceLigne <- 0; indiceColonne <- 0;
 
		 //Méthode qui permet de savoir quand on arrive au dernier trou de passer sur la ligne d'en haut ou celle d'en bas ou d'avancer ou de reculer d'une colonne
		 //Premire ligne = 0 et deuxième ligne = 1.
 
		 changementTrou(indiceLigne, indiceCol)
		 {
 
 
		 	si(indiceCol - 1 < 0)
		 	{
		 		indiceLigne++;
 
		 	}sinon si(indiceCol + 1 > 7)
		 	{
		 		indiceLigne--;
 
		 	}sinon si(indiceLigne = 1 ) 
		 	{
		 		indiceCol++;
		 	}else
		 	{
		 		indiceCol--;
		 	}
 
 
 
		 }
 
		 //Algo principal : l'algo fonctionne pour un trou, donc il faudra le répéter pour N trou pour trouver le trou qui a la bonne combinaison
		 //A noter que le tableau de base n'est pas modifié, le tableau temporaire permet de faire la simulation et déterminer le bon trou
 
		 DEBUT
 
		 TQ (trouver = false et nbTour < 3 et tourTermine = false ) FAIRE
		 {
 
		 	nbPionduTrou <- ct.getNbPion;
		 	indiceL <- ct.getIndiceLigne; indiceC = ct.getIndiceColonne;
 
		 	POUR (cpt de 1 à nbPionTrou) FAIRE
		 	{
		 		changementTrou(indiceL,indiceC);
 
		 		SI (cpt != nbPionTrou) //on est pas encore sur le dernier pion à placer
		 		{
		 			tableauTemp[indiceL][indiceC]++
		 			cpt++;
		 			changementTrou();
 
		 		}SINON SI (cpt = nbpion ) //on doit poser le dernier pion
		 		{
		 				//si c'est le trou qu'on fixait au départ, on a gagné
		 				SI (indiceL = cg.getIndiceLigne et indiceC = cg.getIndiceColonne)
		 				{
		 					trouver <- true;
		 					break; //on sort de la boucle
 
		 				}
 
		 				//si c'est le trou de départ alors c'est qu'on a fait un tour complet
		 				SI (indiceL = ct.getIndiceLigne et indiceC = cg.ct.getIndiceColonne) 
		 				{
		 					nbTour++;
		 				}
 
		 				//sinon on place ce dernier pion
		 				//si le trou est vide, on le place au trou d'après
		 				SI(tableauTemp[indiceL][indiceC]==0)
		 				{
		 					changementTrou();
		 					tableauTemp[indiceL][indiceC]++;
		 					tourTermine <- true;
		 					cpt++;
 
		 				}
 
		 				//si c'est pas le cas des trois si précédents, on doit incrémenter et refaire l'algo.
		 				tableauTemp[indiceL][indiceC]++;
		 				cpt++;
		 		}
 
		 	}FIN POUR
 
		 	if(trouver = false && nbTour<3 && tourTermine = false)
		 	{
		 		 	//on arrive à la fin  et donc on refait l'algo
 
		 		 			ct <- tableauTemp[indiceL][indiceC]; //on récupère les propriétés du dernier trou remplii et on le met dans ct
		 		 			nbPionduTrou <- ct.getNbPion;
		 					indiceL <- ct.getIndiceLigne; indiceC = ct.getIndiceColonne;
		 	}
 
 
		 }Fin TQ
 
		 //A la fin on peut tester si trouver est à true ou false.
		 si trouver est à false, on lance l'algo avec un autre trou de départ.

[picodev]

Si je peux me permettre, je trouve ton algo bien trop détaillé.
Par exemple, pour implémenter un check si il y a une solution en un coup je partirai du principe :

en notant G la case gagnante p(G) la case précédente dans le sens antihoraire
Si G contient 16 ou 32 pions elle est gagnante en 1 coup

si p(G) contient 1 ou 17 pions alors elle est gagnante,
si p(G) contient un nombre non nul de pions alors p(p(G)) devra en contenir 2 ou 18 ou …
si p(G) ne contient aucun pion alors c'est la suivante qui jouera son rôle et p(p(G)) devra en contenir 1 ou 17, ou …
si on en trouve aucune et qu'on revient au point de départ G alors c'est qu'il n'y a aucune solution en 1 coup.

Les … représentent en fait un appel récursif. On voit qu'il y un nombre de pions particulier qui sert d'objectif. On peut imaginer un algorithme plus lisible :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
booléen check_1_coup(G)
Début
  si contenu(G)==16 ou 32 alors
    renvoyer Vrai
  sinon
    renvoyer check_1_coup_objectif(G,p(G),1)
Fin.
 
booléen check_1_coup_objectif(G, courante, objectif)
Début
  si courante=G alors
    renvoyer Faux
  sinon si contenu(courante) modulo 16=objectif alors
    renvoyer Vrai
  sinon si contenu(courante)=0 alors
    renvoyer check_1_coup_objectif(G,p(courante),objectif)
  sinon
    renvoyer check_1_coup_objectif(G,p(courante),objectif+1)
Fin.

À partir du moment où tu arrives à implémenter les primitives contenu et p le tour est joué.

S'il n'y a aucune solution en un coup alors il faut faire une recherche en parcourant tous les coups possibles, en première idée : backtracking.

[kosted]

Si je peux me permettre, je trouve ton algo bien trop détaillé.
Par exemple, pour implémenter un check si il y a une solution en un coup je partirai du principe :

en notant G la case gagnante p(G) la case précédente dans le sens antihoraire
Si G contient 16 ou 32 pions elle est gagnante en 1 coup

si p(G) contient 1 ou 17 pions alors elle est gagnante,
si p(G) contient un nombre non nul de pions alors p(p(G)) devra en contenir 2 ou 18 ou …
si p(G) ne contient aucun pion alors c'est la suivante qui jouera son rôle et p(p(G)) devra en contenir 1 ou 17, ou …
si on en trouve aucune et qu'on revient au point de départ G alors c'est qu'il n'y a aucune solution en 1 coup.

Les … représentent en fait un appel récursif. On voit qu'il y un nombre de pions particulier qui sert d'objectif. On peut imaginer un algorithme plus lisible :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
booléen check_1_coup(G)
Début
  si contenu(G)==16 ou 32 alors
    renvoyer Vrai
  sinon
    renvoyer check_1_coup_objectif(G,p(G),1)
Fin.
 
booléen check_1_coup_objectif(G, courante, objectif)
Début
  si courante=G alors
    renvoyer Faux
  sinon si contenu(courante) modulo 16=objectif alors
    renvoyer Vrai
  sinon si contenu(courante)=0 alors
    renvoyer check_1_coup_objectif(G,p(courante),objectif)
  sinon
    renvoyer check_1_coup_objectif(G,p(courante),objectif+1)
Fin.

À partir du moment où tu arrives à implémenter les primitives contenu et p le tour est joué.

S'il n'y a aucune solution en un coup alors il faut faire une recherche en parcourant tous les coups possibles, en première idée : backtracking.

Désolé, d'avoir trop détaillé. Etant encore étudiant, je suis obligé de bien commenté pour faire plaisir au prof, du coup j'ai pris l'habitude.. Je vais implémenter ça en java et je vous tiens au courant