Recherche al�atoire de solutions

Il existe certains jeux pour lesquels il n'est pas possible d'utiliser une strat�gie. Le jeu du "Compte est bon" en est une bonne illustration.

Il n'existe pas, (du moins je ne connais pas) d'algorithme permettant de trouver rapidement une solution. De plus, comme il existe quelques millions de possibilit�s, il n'est pas possible de les examiner toutes exhaustivement.

Pour r�soudre ce probl�me, le plus simple est de rechercher al�atoirement des solutions et de ne garder que celle qui se rapproche le plus du r�sutat demand�. L'applet suivante est une impl�mentation du jeu du "Compte est bon" :

L'essentiel du programme est constitu� par la recherche al�atoire de solutions. Cette recherche s'effectue par un objet "Solution" d�crit ci-dessous :

class Solution {
	int sol = 0;
	int valeur = 0;
	int[] chif_trav = new int[26];
	int[] utilise = new int[26];
	int nb_resultats_indermediaires = 0;
	String[] etapes = new String[20];
	int nb_etapes = 0;

	Solution(int [] chiffres, int s) {
	  	int temp = 0;
	  	sol = s;
	  	for (int i=0;i<26;i++) {
	  		chif_trav[i] = 0;
	  	}
	  	for (int i=0;i<26;i++) {
	  		utilise[i] = 0;
	  	}
	  	// On r�parti les 6 chiffres d'une mani�re al�atoire
	  	for (int i=0;i<6;i++) {
	  		do {
				temp =(int)Math.round((Math.random()*6));
				if (temp==6) temp=0;
	  		}
	  		while (chif_trav[temp] != 0);
	  		chif_trav[temp] = chiffres[i];
	  	}
	  	calcule();
	  }

	public void calcule() {

	int n1 = 0; int n2 = 0;
	int nb1 = 0; int nb2 = 0;
	int res = 0;int cpt = 0;
	int op = 0;boolean ok = true;
	int j=0;
	while ((res != sol) && (cpt < 20) && (ok)) {
		ok = false;
		while (! ok) {
			ok = true;
			n1 = (int)Math.round((Math.random()*(6+ nb_resultats_indermediaires)));
			if (n1>=6+nb_resultats_indermediaires) ok=false;
			if (utilise[n1]==1) ok = false;
		}
		if (ok) utilise[n1]=1;
		ok = false;
		while (! ok) {
			ok = true;
			n2 = (int)Math.round((Math.random()*(6+ nb_resultats_indermediaires)));
			if (n2>=6+nb_resultats_indermediaires) ok=false;
			if (utilise[n2]==1) ok = false;
		}
		if (ok) utilise[n2]=1;
		op = 0;
		while (op == 0) {
			nb1 = chif_trav[n1];
			nb2 = chif_trav[n2];
			op = (int)Math.round((Math.random()*4));
			op = op + 1; // 1 = +, 2 = -, 3 = *, 4 = /

			if (op>4) op=0; else
			if ((op==4) && (nb2>nb1)) op=0; else
			if ((op == 4) && ((nb1 % nb2) != 0)) op=0; else
			if ( ((nb1==1) || (nb2==1)) && ((op==3) || (op==4))) op=0; else
			if ( (nb2>=nb1) && (op==2)) op=0;

			if (op != 0) {
				String s = " "+nb1;
				switch (op) {
					case 1 : res = nb1 + nb2;s=s+" + ";break;
					case 2 : res = nb1 - nb2;s=s+" - ";break;
					case 3 : res = nb1 * nb2;s=s+" * ";break;
					case 4 : res = nb1 / nb2;s=s+" / ";
				}
				if (res > 0) {
					s=s+nb2+" = "+res;
					etapes[cpt]=s;
					cpt++;
					chif_trav[6+nb_resultats_indermediaires]=res;
					utilise[6+nb_resultats_indermediaires]=0;
					nb_resultats_indermediaires++;
					if ((valeur==0) || (get_diff() > Math.abs(res-sol))) {
						valeur = res;
						nb_etapes=cpt;
					}
				}
			}
		}
		j=0;
		ok=false;
		for (int i=0;i<6+nb_resultats_indermediaires;i++)
		if (utilise[i]==0) j++;
		if (j>1) ok=true;
	}
	}

	  public int get_valeur() { return valeur;}

	  public int get_diff() { return Math.abs(valeur-sol
	  );}

LOEWENGUTH Pascal - http://lwh.free.fr -