[Java] Algorithme de recherche de solutions pour jeu "le compte est bon"
Bonjour à tous,
Je suis en train de développer une version java du jeu des "chiffres" issu de l'émission tv "des chiffres et des lettres".
Je rappelle brièvement les règles: - un résultat aléatoire est demandé entre 101 et 999
- il faut retrouver ce résultat grâce à 6 opérandes, les entiers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 en deux exemplaires chacun et les entiers 25, 50, 75, 100 en un seul exemplaire
- grâce à ces opérandes on peut effectuer les 4 opérations de base: +, -, *, / (division entière)
Le jeu fonctionne bien, le joueur propose ses étapes jusqu'à ce qu'il arrive au résultat, se trompe, où n'est plus d'opérandes dans sa liste. Ensuite un score lui est donné.
Maintenant l'étape où je bloque c'est l'étape de la recherche de toutes les solutions possibles pour ce résultat aléatoire donnée et ses opérandes donnés. Le joueur pourrait ainsi toutes les consulter à la fin de la partie.
J'ai commencé en recherchant pour le début uniquement les solutions utilisant tout les opérandes, soit en 5 étapes (= 5 opérations). J'ai basé ma réflexion sur un algorithme en arbre dont la racine serait le premier opérande de la liste et chaque nœud additionne, soustrait, multiplie et divise (si possible) cette racine par l'opérande suivant. Et ainsi de suite... On devrait ainsi parvenir à toutes les résultats possibles en 5 étapes. J'ai donc pensé à une méthode récursive. Cette méthode s'appelle 4 fois, une fois pour chaque opérations. Seulement j'ai ce premier problème pourtant basique je pense qui est que je ne passe que dans une seule branche à chaque appelle. Je ne fais qu'additionner tout les opérandes.
Un peu de code pour vous laisser apprécier (Plaque.java)
Code:
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
| public class Plaque {
/**
* <p>La borne infèrieure où la solution va être générée</p>
*/
private static int BORNE_INF = 0;
/**
* <p>La borne supèrieure où la solution va être générée</p>
*/
private static int BORNE_SUP = 0;
/**
* <p>Une liste contenant 5 entiers entre 1 et 10 pouvant être en 2
* exemplaire et 1 entier (soit 25, 50, 75 ou 100) en un seul
* exemplaire</p>
* <p>La liste des opérandes à la disposition du joueur.
* Au début cette liste sera la même que celle générée aléatoirement
* par la classe Plaque, puis les opérandes seront enlevés et ceux
* calculés seront rajoutés au fur et à mesure.</p>
*/
private LinkedList<Integer> operandeSource;
/**
* <p>Un entier généré aléatoirement à trouver entre 101 et 999</p>
*/
private static int nbATrouver;
/**
* <p>Le nombre de solution possible compte tenu du résultat et des
* opérandes disponibles</p>
*/
private int nbSolution;
/**
* <p>Une liste de toutes les solutions possibles compte tenu du
* résultat et des opérandes disponibles</p>
*/
private LinkedList<String> solution;
/**
* <p>Le constructeur par défaut va initialiser aléatoirement
* la liste d'opérandes, et une solution entre 101 et 999</p>
*/
Plaque(int borneinf, int bornesup) {
BORNE_INF = borneinf;
BORNE_SUP = bornesup;
operandeSource = new LinkedList<Integer>();
InitOperandeSource();
InitNbATrouver();
nbSolution = 0;
}
public void chercherSolutions(LinkedList<Integer> copyOperandeSource,
int resultatEnCours,
int compteur) {
if (resultatEnCours != nbATrouver && compteur < 10) {
System.out.println(resultatEnCours);
compteur++;
resultatEnCours += copyOperandeSource.get(compteur);
chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
if (resultatEnCours > copyOperandeSource.get(compteur)) {
resultatEnCours -= copyOperandeSource.get(compteur);
}
chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
resultatEnCours *= copyOperandeSource.get(compteur);
chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
if (resultatEnCours % copyOperandeSource.get(compteur) == 0) {
resultatEnCours /= copyOperandeSource.get(compteur);
chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
} else if (copyOperandeSource.get(compteur) % resultatEnCours == 0) {
resultatEnCours = copyOperandeSource.get(compteur)/resultatEnCours;
chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
}
} else {
System.out.println("fin des traitements");
}
}
} |
testRechercheSolutions.java
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static void main(String[] args) {
Partie testPartie = new Partie(101, 999);
System.out.println("Liste d'opérandes restants: "+
testPartie.getOperande());
System.out.println("Résultat à trouver: "+
testPartie.getResultat());
LinkedList<Integer> copyOperandeSource = new LinkedList<Integer>();
copyOperandeSource = testPartie.getOperande();
int compteur = 0;
int resultatEnCours = copyOperandeSource.get(0);
testPartie.getTirage().chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
} |
en console j'obtiens par exemple:
Liste d'opérandes restants: [5, 10, 5, 9, 3, 25]
Résultat à trouver: 787
5
15
20
29
32
57
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 6, Size: 6
at java.util.LinkedList.entry(Unknown Source)
at java.util.LinkedList.get(Unknown Source)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:174)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.test.testRechercheSolution.main(testRechercheSolution.java:35)
Et une belle erreur! La ligne 174 étant:
Code:
resultatEnCours += copyOperandeSource.get(compteur);
Si je n'est pas été clair sur un point n'hésitez pas ^^. Après je ne suis pas franchement sur que cette solution soit très appropriée. Je vous laisse me dire ce que vous en pensez. Surtout que je suis obligé pour lancer la recherche de solution de passer par mon programme de test.
